//Streams II
/*
What is a stream?
- rither null or a pair whose head is of that type and
- tail is a nullary function that returns a stream of that type
*/
//Concept of laziness
//stream_tail is used to defer computation
//Finite stream: fixed number of elements
const s3 = pair(1, ()=> pair(2, ()=> pair(3, null)));
s3;
head(s3);//returns 1
head(tail(s3)());//returns 2
head(tail(tail(s3)())());// returns 3
//Infinite stream: innfinite elements
function ones_stream(){
return pair(1 ,ones_stream);
}
const ones = ones_stream();
// alternative: const ones = pair(1, ()=> ones); (wrapping around)
head(ones);//returns 1
head(tail(ones)());//returns 1
head(tail(tail(ones)())());//returns 1
//stream_tail:
function stream_tail(stream){
return tail(stream)();
}
head(ones);//returns 1
head(stream_tail(ones));//returns 1
head(stream_tail(stream_tail(ones)));//returns 1
//difference: stream_tail uses lazy evaluation
//enum_stream
function enum_stream(low,hi){
return low > hi
? null
: pair(low, () => enum_stream(low + 1, hi));
}
let s = enum_stream(1, 100);
head(s); //returns 1
head(stream_tail(s)); //returns 2
head(stream_tail(stream_tail(s))); //returns 3
//stream_ref
function stream_ref(s, n){
return n === 0
? head(s)
: pair(head(s), () => stream_ref(stream_tail(s), n-1));
}
s = enum_stream(1, 100);
stream_ref(s, 0); //returns 1
stream_ref(s, 10); //returns unevaluated stream
stream_ref(s, 99);//returns unevaluated stream
//stream_map
function stream_map(f, s){
return is_null(s)
? null
: pair(f(head(s)), () => stream_map(f, stream_tail(s)));
}
//stream_filter
function stream_filter(p, s){
return is_null(s)
? null
: p(head(s))
? pair(head(s), () => stream_filter(p, stream_tail(s)))
: stream_filter(p, stream_tail(s));
}
//EXAMPLES:
//1. integers_from
function integers_from(n){
return pair(n, () => integers_from(n+1));
}
const integers = integers_from(1);
stream_ref(integers, 0); //returns 1
stream_ref(integers, 10); //returns unevaluated stream
stream_ref(integers, 99); //returns unevaluated stream
//2. no_fours
function is_divisible(x,y){
return x % y ===0;
}
const no_fours= stream_filter(x => !is_divisible(x,4), integers);
stream_ref(no_fours, 3);
stream_ref(no_fours, 100);
//From Streams to Lists: eval_stream
function eval_stream(s, n){
return n === 0
? null
: pair(head(s), eval_stream(stream_tail(s), n-1));
}
eval_stream(no_fours, 10); //returns [1, [2, [3, [5, [6, [7, [9, [10, [11, [13, null]]]]]]]]]]
//Fibonacci Numbers
function fibgen(a, b){
return pair(a, () => fibgen(b, a + b));
let fibs = fibgen(1,1);
eval_stream(fibs,10);
}
//more_and_more
//wanted: Stream containing 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, ...
function more(a, b){
return (a > b)
? more (1, 1 + b)
: pair (a, () => more(a + 1, b));
}
const more_and_more = more(1,1);
eval_stream(more_and_more, 15);
//returns: [1, [1, [2, [1, [2, [3, [1, [2, [3, [4, [1, [2, [3, [4, [5, null]]]]]]]]]]]]]]]
//Replace
function replace(g, a, b){
return is_null(g)
? null
: pair((head(g) === a) ? b : head(g),
() => replace(stream_tail(g), a, b));
}
const g = replace(more_and_more, 1, 0);
eval_stream(g, 15);
//returns [0, [0, [2, [0, [2, [3, [0, [2, [3, [4, [0, [2, [3, [4, [5, null]]]]]]]]]]]]]]]
//List to Infinite stream
function list_to_inf_stream(xs){
function helper(ys){
return is_null(ys)
? helper(xs) //reset list
: pair(head(ys), () => helper(tail(ys)));
}
return is_null(xs)? null : helper(xs);
}
const z = list_to_inf_stream(list(1,2,3));
eval_stream(z, 10);
//returns: [1, [2, [3, [1, [2, [3, [1, [2, [3, [1, null]]]]]]]]]]
//Alternative:
const rep123 = pair(1, ()=> pair(2, ()=> pair(3, ()=> rep123)));
//Adding Streams
function add_streams(s1, s2){
return is_null(s1)
? s2
: is_null(s2)
? s1
: pair(head(s1) + head(s2), () => add_streams(stream_tail(s1), stream_tail(s2)));
}
//Fibonacci Numbers using add_streams
//const fibs = pair(0, ()=> pair(1, () => add_streams(stream_tail(fibs), fibs)));
//eval_stream(fibs, 10);
//result: [0, [1, [1, [2, [3, [5, [8, [13, [21, [34, null]]]]]]]]]]
///Integers Revisisted using add_streams
const one_s = pair(1, ()=> one_s);
const integer_s = pair(1, () => add_streams(one_s, integer_s));
eval_stream(integer_s, 10);
//returns [1, [2, [3, [4, [5, [6, [7, [8, [9, [10, null]]]]]]]]]]
//Memoization with lazy evaluation
function memo_fun(fun){
let already_run = false; // Tracks if function has been called before
let result = undefined; //Stores result of first call
function mfun(){
if (!already_run){ //If function has not been called yet
result = fun(); // call function and store it
already_run = true; //mark already run as true
return result;
} else { //If function has already been called
return result; //return cached result
}
}
return mfun; //return memoized function
}
//Example 1 vs Example 2
//Example 1:
function ms(m, s){
display(m);
return s;
}
const onesA = pair(1, () => ms("A", onesA));
stream_ref(onesA, 3);
/*
Output:
→stream_ref({display("A"); return onesA;}, 2);
→ stream_ref(onesA, 2);
→ stream_ref({display("A"); return onesA;}, 1);
→ stream_ref(onesA, 1);
→ stream_ref({display("A"); return onesA;}, 0);
→ stream_ref(onesA, 0);
→ head(onesA);
→1
*/
const onesB = pair(1, memo_fun(() => ms("B", onesB)));
stream_ref(onesB, 3);
/*
→ stream_ref({display("B"); memoize onesB; return onesB;}, 2);
→ stream_ref(onesB, 2);
→ stream_ref({return memoized onesB;}, 1);
→ stream_ref(onesB, 1);
→ stream_ref({return memoized onesB;}, 0);
→ stream_ref(onesB, 0);
→ head(onesB);
→1
*/
//Example 2:
function m_integers_from(n){
return pair(n, memo_fun(()=> ms( "M" + stringify(n), m_integers_from( n +1))));
}
const m_integers = m_integers_from(1);
stream_ref(m_integers, 0);
stream_ref(m_integers, 1);
stream_ref(m_integers, 2); //"M: 2"
// next time stream_ref(m_integers, 2); gives 2 straight from memory
//Generating Primes- Sieve of Eratosthenes
//Original:
function is_prime(n){
function is_divisible_by_any(divisor){
if (divisor * divisor > n){
return false;
} else if (n % divisor === 0){
return true;
} else {
return is_divisible_by_any(divisor + 1);
}
}
return n>1 && !is_divisible_by_any(2);
}
const primes = pair(2, () => stream_filter(is_prime, integers_from(3)));
eval_stream(primes, 10);
//returns: [2, [3, [5, [7, [11, [13, [17, [19, [23, [29, null]]]]]]]]]]
//SIEVE METHOD:
function sieve(s){
return pair(head(s), () => sieve(stream_filter( x =>!is_divisible(x, head(s)), stream_tail(s))));
}
const primes2 = sieve(integers_from(2));
//Square Roots by Newton's Method
//Using Streams for Iteration
function average (x,y){
return (x + y)/2;
}
function improve (guess, x){
return average(guess, x /guess);
}
function sqrt_stream(x){
const guesses = pair(1.0, () => stream_map(guess => improve(guess, x), guesses));
return guesses;
}
eval_stream(sqrt_stream(2),6);
/*
returns:
[ 1,
[ 1.5,
[ 1.4166666666666665,
[1.4142156862745097, [1.4142135623746899, [1.414213562373095, null]]]]]]
*/
