2

问题

1 流和惰性评估（40 分）

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

(* Suspended computation *)
datatype 'a stream' = Susp of unit -> 'a stream

(* Lazy stream construction *)
and 'a stream = Empty | Cons of 'a * 'a stream'

请注意，这些流不一定是无限的，但它们可以是无限的。

Q1.1 (20 分) 实现函数lazysort: int list -> int stream'。

它接受一个整数列表并返回一个表示排序列表的 int 流。这应该在恒定时间内完成。每次强制流'时，它都会给出 Empty 或 Cons(v, s')。在 cons 的情况下，v 是排序列表中的最小元素，s' 是表示剩余排序列表的流'。该力应该花费线性时间。例如：

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

相关定义

以下是作为代码给出的内容：

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

我的解决方案尝试

我尝试执行以下操作来获取 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;

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

任何帮助，将不胜感激。

4

2 回答 2

2

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

  • 您不需要将 int 列表转换为 int 流'。首先，这违反了对惰性排序的初始调用必须在恒定时间内完成的规则​​。请注意，将其转换为 int 流是在线性时间内完成的。您需要做的是在您返回的挂起流的闭包中提供一个嵌入式排序函数（使用 let 块）。流的第一个元素将是排序函数的结果（使用挂起的闭包完成。 ) 流的第二个元素（只是一个 int 流'）应该是对您的 lazysort 函数的调用，因为它返回一个 int 流'。请注意，这如何让您避免必须对其进行转换。排序函数本身很简单，
于 2011-03-16T20:50:49.550 回答
2

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

您使用放置功能走在正确的道路上（有点......我不知道为什么real只有int streams.

   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. 我认为小于或等于（只是小于应该工作......没有真正考虑过）并不重要。此外，您必须先到达列表的底部才能分辨出哪个是最小的，所以这是尾部优先。这样 (* 1 *) 是第一个，然后是 (* 2 *) 的每个内部调用，直到最外面的调用。
  3. 那应该cons(x, insertsort xs)在 (* 5 *) 中，因为您要返回int stream'带有函数的 a 。
于 2011-03-16T10:00:16.293 回答