Question

The question

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 

Relevant definitions

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.

Answer 1

Each time the stream is accessed to get the head of the sorted list, the smallest element is found in the list.

You are on the correct path with the placement function (sort of... I don t know why you have real types instead of int when there will only be int streams . Your pattern would not match if you have not realized by now).

   fun insertsort ([]:int list) = empty  
   | insertsort (h::t) =  
    let   
        fun insert (x:real, []) = [x] (* 1 *)
        | insert (x:real, y::ys) =    (* 2 *)
            if x<=y then x::y::ys     (* 3 *)
            else y::insert(x, ys)     (* 4 *)
    in insert(x, insertsort xs)       (* 5 *)

This is your helping inner magic for getting the smallest item each time.
Some hints/tips to make the above work

You should have only one argument
I don t think it matters to have less than or equal to (just less than should work .... have not really thought about that). Also you have to reach the bottom of the list first to tell which is the smallest so this is tail first. so that (* 1 *) is the first then each inside call of (* 2 *) till the outermost one.
That should be cons(x, insertsort xs) in (* 5 *) since you are returning a int stream with the function.

Answer 2

I m in your class and I think you re going about this the totally wrong way. I ve solved the question, but I think it s a bit unethical for me to fully share the code with you. That said, here s a pointer:

you don t need to transform the int list into an int stream . Firstly, this violates the rule that the initial call to lazysort must be done in constant time. Note that transforming it to an int stream is done in linear time. What you need to do is provide an embedded sort function within the closure of the suspended stream you re returning (using a let block.) The first element of the stream would be the result of the sort function (done with the suspended closure.) The second element of the stream (which is just an int stream ) should be a call to your lazysort function, because it returns an int stream . Notice how this lets you avoid having to transform it. The sort function itself is quite simple, because you only need to find the smallest element and return the rest of the list without the element you found to be the smallest.

The question

Relevant definitions

My attempt at a solution

友情链接