使用流的 SML 惰性排序 int 列表

发布于 2024-10-21 22:32:01 字数 1990 浏览 6 评论 0原文

问题

1 流和惰性评估（40 分）
我们知道比较排序至少需要 O(n log n) 次比较，其中对 n 个元素进行排序。假设对于某个函数 f，我们只需要排序列表中的前 f(n) 个元素。如果我们知道 f(n) 渐近小于 log n，那么对整个列表进行排序将是浪费的。我们可以实现一个惰性排序，它返回一个表示排序列表的流。每次访问流以获取排序列表的头部时，都会在列表中找到最小的元素。这需要线性时间。从列表中删除 f(n) 个元素将花费 O(nf(n))。对于这个问题，我们使用以下数据类型定义。还定义了一些辅助函数。
(* 暂停计算 *)
数据类型'astream'=单元暂停-> '一条流

(* 惰性流构建 *)
和'流=空| 'a * 'astream' 的缺点
请注意，这些流不一定是无限的，但它们可以是。
Q1.1（20分）实现函数lazysort：int list -> int 流'。
它接受一个整数列表并返回一个表示排序列表的 int 流。这应该在恒定的时间内完成。每次强制stream'时，它都会给出Empty或Cons(v, s')。在缺点的情况下，v 是排序列表中的最小元素，s' 是表示剩余排序列表的流'。力应该花费线性时间。例如：
- val s = lazysort( [9, 8, 7, 6, 5, 4] );
val s = Susp fn : int 流'
- val Cons(n1, s1) = 力(s);
值 n1 = 4 ：整数
val s1 = Susp fn : int 流'
- val Cons(n2, s2) = 力(s1);
值 n2 = 5 ：整数
val s2 = Susp fn : int 流'
- val Cons(n3, s3) = 力(s2);
值 n3 = 6 ：整数
val s3 = Susp fn : int 流'

我尝试解决方案时

尝试执行以下操作，获取 int 列表并将其转换为 int 流'：

(* lazysort: int list -> int stream' *)
fun lazysort ([]:int list) = empty
| lazysort (h::t) = cons (h, lazysort(t));

但是当调用force时，它不会返回最小元素。我必须搜索最小值，但我不知道如何...我想到像下面这样进行插入排序：

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;

但我必须搜索最小值并且不对列表进行排序，然后将其作为流...

任何帮助将不胜感激。

原文

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.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

债姬 2024-10-28 22:32:01

每次访问流以获取排序列表的头部时，都会在列表中找到最小的元素。

您使用放置函数处于正确的路径上（有点...我不知道为什么您有 real 类型而不是 int，而只有 int 流如果您现在还没有意识到，您的模式将不匹配）。

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

这是你每次都能获得最小物品的内在魔法。
使上述工作有效的一些提示/技巧

您应该只有一个参数，
我认为小于或等于并不重要（只是小于应该工作......还没有真正考虑过这一点）。另外，您必须先到达列表的底部才能知道哪个是最小的，所以这是尾部在前。这样 (* 1 *) 是第一个，然后是 (* 2 *) 的每个内部调用，直到最外面的调用。
这应该是 (* 5 *) 中的 cons(x, insertsort xs) ，因为您使用该函数返回一个 int stream' 。

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.

回复收藏 0 原文

靑春怀旧 2024-10-28 22:32:01

我在你的班上，我认为你的处理方式完全错误。我已经解决了这个问题，但我认为与您完全共享代码对我来说有点不道德。也就是说，这里有一个指针：

您不需要将 int 列表转换为 int 流'。首先，这违反了对惰性排序的初始调用必须在恒定时间内完成的规则。请注意，将其转换为 int 流是在线性时间内完成的。您需要做的是在要返回的挂起流的闭包中提供嵌入的排序函数（使用 let 块）。流的第一个元素将是排序函数的结果（使用挂起的闭包完成）。）流的第二个元素（只是一个 int 流）应该是对您的惰性排序函数的调用，因为它返回一个 int 流。请注意这如何让您避免对其进行转换。排序函数本身非常简单，因为您只需要找到最小的元素并返回列表的其余部分，而无需找到最小的元素。

回复收藏 0 原文

~没有更多了~