//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]]]]]]
*/