How Can Lazysort Be Implemented Using Streams in SML?

[VasyaGamer]

Homework Statement

Here is 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'

Homework Equations

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)

The 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.

 

[KataKoniK]

Hello,

Thank you for posting your question. I can help you with your problem.

Firstly, I would like to clarify that this forum is meant for discussing scientific concepts and ideas, and not for providing solutions to specific homework problems. It is important for you to understand and solve the problem yourself in order to learn and grow as a scientist.

That being said, I can provide some guidance and suggestions to help you solve this problem. The key to implementing the lazysort function is to use the Susp datatype to create a suspended computation that will return the sorted stream when forced.

One approach could be to use a helper function that takes in a list and returns a suspended computation of the sorted stream. This helper function can use the insertion sort algorithm that you have mentioned. Here is an example of how the helper function could be implemented:

fun lazysort_helper (l: int list) =
let
fun insert (x: int, []) = [x]
| insert (x: int, y::ys) =
if x <= y then x::y::ys
else y::insert(x, ys)
fun sort ([]) = empty
| sort (h::t) = cons (h, Susp (fn () => sort (insert (h, t))))
in
sort (l)
end;

This helper function will take in a list and use the insertion sort algorithm to sort the list and create a suspended computation of the sorted stream. The Susp function is used to create a suspended computation which will be forced later when the stream is accessed.

Now, you can use this helper function in the lazysort function to return the suspended computation of the sorted stream. Here is an example of how the lazysort function could be implemented:

fun lazysort (l: int list) =
Susp (fn () => lazysort_helper (l));

This lazysort function takes in a list and returns a suspended computation of the sorted stream using the helper function we defined earlier. When this suspended computation is forced, it will return the sorted stream.

I hope this helps you understand the problem better and guides you towards finding a solution. Remember to always try to understand and solve the problem yourself, as that is the key to becoming a successful scientist. Good luck!