(* Lecture 16/17

   Using higher-order functions and data-types to model lazy
   functional programming
*)

(* ---------------------------------------------------- *)
(* Suspended computation : we can suspend computation
   by wrapping it in a closure. *)
datatype 'a susp = Susp of (unit -> 'a)

(* delay: *)
fun delay (f ) = Susp(f)

(* force: *)
fun force (Susp(f)) = f ()

(* ---------------------------------------------------- *)
(* Define an infinite stream *)
datatype 'a stream' = Cons of 'a  * 'a stream
withtype 'a stream = ('a stream') susp

(* ---------------------------------------------------- *)
(* here we create an infinite stream of 1's! *) 
(* val ones' = fn : unit -> int stream'
   val ones  = Susp fn : int stream' susp
*)   
val rec ones' = fn () => Cons(1, delay(ones'));
val ones = delay(ones')

(* Alternatively... 
val onesSeq = fn : unit -> int stream' susp
*)
fun onesSeq () = Susp(fn () => Cons(1, onesSeq ()));


(* Generate natural numbers *)
(* val numsFrom = fn : int -> int stream' susp *)
fun numsFrom n = Susp(fn () => Cons(n, numsFrom(n+1)));

(* val nats = Susp fn : int stream' susp *)
(* nats: int stream *)
val nats = numsFrom 0;


(* ---------------------------------------------------- *)
(* Inspect a stream up to n elements 
   take : int -> 'a stream' susp -> 'a list
   take': int -> 'a stream' -> 'a list
*)
fun take 0 s = []
  | take n (s) = take' n (force s)
and take' 0 s = []
  | take' n (Cons(x,xs)) = x::(take (n-1) xs)

(* printn: ('a stream') susp * int -> 'a list *)
fun printn (s, 0) = print "\n"
  | printn (s, k) = printn' (force s, k)
and printn' (Cons(x,s), k) = (print (Int.toString(x) ^ " "); (printn(s,k-1)))

(* Observe what happens *)
(*
- take 5 (numsFrom 0);
val it = [0,1,2,3,4] : int list
- take 5 (nats);
val it = [0,1,2,3,4] : int list

*)
(* ---------------------------------------------------- *)
(*construct a stream of the fibonacci numbers -- simpler 
  a   b    Fib stream
  0   1     0, ...
  1   1     0, 1 ...
  1   2     0, 1, 1, ...
  2   3     0, 1, 1, 2, ....
  3   5     0, 1, 1, 2, 3, ...
  5   8     0, 1, 1, 2, 3, 5, ...
  8  13     0, 1, 1, 2, 3, 5, 8 ...

*)
(* fibStream: int stream' susp *)
val fibStream = 
 let
    fun fib a b = Cons(a, Susp (fn () => fib b (a+b)))
  in
    Susp(fn () => fib 0 1)
  end

(* ---------------------------------------------------- *)
(* Extract the head and tail of a stream *)
(* shd' : ('a stream) susp -> 'a 
   shd  : 'a stream        -> 'a *)

fun shd (s) = shd' (force s)
and shd'(Cons(x, s)) = x

(* this is equivalent to the following 
   val hd = fn : 'a stream' susp -> 'a
   val hd' = fn : 'a stream' -> 'a
*)
fun hd (Susp(s)) = hd' (s ())
and hd' (Cons(x, s)) = x

(* ---------------------------------------------------- *)
(* Extract the tail of a stream 
   Two possibilities: Do you want a suspended tail?
   or do we want a stream (= not suspended)?
*)

(* Version 1: return a suspended tail *)
(* ltail : ('a stream') susp -> ('a stream') susp 
   ltail'  : 'a stream' -> ('a stream') susp
*)
fun ltail(s) = ltail'(force s) 
and ltail' (Cons(x, s)) = s

(* Version 2: return a tail (not suspended) 
   tail : ('a stream') susp -> ('a stream')
   tail' :    'a stream' -> ('a stream')  
*)
fun tail(Susp(s)) = tail'(s ()) 
and tail' (Cons(x, s)) = force(s)


(* ---------------------------------------------------- *)
(* smap: ('a -> 'b) -> 'a stream' susp -> 'b stream' susp *)
fun smap f s = 
 let
   fun mapStr (s) = mapStr'(force s)
   and mapStr'(Cons(x, s)) = delay(fn () => Cons((f x), mapStr(s)))
 in
   mapStr(s)
 end


(* This would be a little too eager  -- do you see why?   *)
(* smapWRONG: ('a -> 'b) -> 'a stream' susp -> 'b stream' *)
fun smapWRONG f s = 
 let
   fun mapStr (s) = mapStr'(force s)
   and mapStr'(Cons(x, s)) = Cons((f x), delay(fn () => mapStr(s)))
 in
   mapStr(s)
 end

(*
- take 10 (smap (fn x => x+1) nats);
val it = [1,2,3,4,5,6,7,8,9,10] : int list
- 
*)
(* ---------------------------------------------------- *)
(* Adding two streams really lazily )

   addStreams  : int stream' susp * int stream' susp -> int stream' susp
   addStreams' : int stream' * int stream' -> int stream' susp
*)
fun addStreams (s1, s2) = 
  addStreams'(force s1, force s2)
and addStreams'(Cons(x,xs), Cons(y, ys)) = 
   delay(fn () => Cons(x+y, addStreams(xs, ys)))

(*
- 
- take 5 (addStreams(nats, ones));
val it = [1,2,3,4,5] : int list

*)

(* ---------------------------------------------------- *)
(* filter: ('a -> bool) -> 'a stream' susp -> 'a stream' susp
   filter': ('a -> bool) -> 'a stream' -> 'a stream' susp *)
fun filter p s = filter' p (force s)
and filter' p (Cons(x,s)) =  
  (if p x then delay(fn () => Cons(x, filter p s))
    else filter p s)

val evens = filter (fn x => x mod 2 = 0) (ltail(nats))

val odds = filter (fn x => x mod 2 = 1) nats

(*
- take 10 odds;
val it = [1,3,5,7,9,11,13,15,17,19] : int list
- take 10 evens;
val it = [2,4,6,8,10,12,14,16,18,20] : int list
- 
*)