(* 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 - *)