1 Streams and lazy evaluation (40 points)
We know that comparison sorting requires at least O(n log n) comparisons where were are sorting n elements. Let’s say we only need the first f(n) elements from the sorted list, for some function f. If we know f(n) is asymptotically less than log n then it would be wasteful to sort the entire list. We can implement a lazy sort that returns a stream representing the sorted list. Each time the stream is accessed to get the head of the sorted list, the smallest element is found in the list. This takes linear time. Removing the f(n) elements from the list will then take O(nf(n)). For this question we use the following datatype definitions. There are also some helper functions defined.
(* Suspended computation *) datatype 'a stream' = Susp of unit -> 'a stream (* Lazy stream construction *) and 'a stream = Empty | Cons of 'a * 'a stream'
Note that these streams are not necessarily infinite, but they can be.
Q1.1 (20 points) Implement the function lazysort: int list -> int stream'.
It takes a list of integers and returns a int stream' representing the sorted list. This should be done in constant time. Each time the stream' is forced, it gives either Empty or a Cons(v, s'). In the case of the cons, v is the smallest element from the sorted list and s' is a stream' representing the remaining sorted list. The force should take linear time. For example:
- val s = lazysort( [9, 8, 7, 6, 5, 4] ); val s = Susp fn : int stream' - val Cons(n1, s1) = force(s); val n1 = 4 : int val s1 = Susp fn : int stream' - val Cons(n2, s2) = force(s1); val n2 = 5 : int val s2 = Susp fn : int stream' - val Cons(n3, s3) = force(s2); val n3 = 6 : int val s3 = Susp fn : int stream'
Here is what is given as code:
(* Suspended computation *) datatype 'a stream' = Susp of unit -> 'a stream (* Lazy stream construction *) and 'a stream = Empty | Cons of 'a * 'a stream' (* Lazy stream construction and exposure *) fun delay (d) = Susp (d) fun force (Susp (d)) = d () (* Eager stream construction *) val empty = Susp (fn () => Empty) fun cons (x, s) = Susp (fn () => Cons (x, s)) (* Inspect a stream up to n elements take : int -> 'a stream' -> '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)
My attempt at a solution
I tried to do the following which get the int list and transforms it to int stream':
(* lazysort: int list -> int stream' *) fun lazysort (:int list) = empty | lazysort (h::t) = cons (h, lazysort(t));
But when calling force it does not return the minimum element. I have to search for the minimum, but I do not know how... I thought of doing insertion sort like following:
fun insertsort  =  | insertsort (x::xs) = let fun insert (x:real, ) = [x] | insert (x:real, y::ys) = if x<=y then x::y::ys else y::insert(x, ys) in insert(x, insertsort xs) end;
But I have to search for the minimum and to not sort the list and then put it as a stream...
Any help would be appreciated.