使用流的SML Lazy排序的int列表
这个问题
1流和懒惰的评价（40分）
我们知道比较排序需要至少O（n log n）比较，其中正在排序n个元素。假设我们只需要排序列表中的第一个f（n）元素，对于某些函数f。如果我们知道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'
- 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)
(* lazysort: int list -> int stream' *)
fun lazysort ([]:int list) = empty
| lazysort (h::t) = cons (h, lazysort(t));
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;
没有找到相关结果
已邀请:
2 个回复
程琶
类型而不是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 *)in（* 5 *），因为你要用函数返回一个。体悉