2

質問

1ストリームと遅延評価（40ポイント）

比較ソートには、n個の要素をソートする場合に少なくともO（n log 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-> intstream'を実装します。

整数のリストを受け取り、ソートされたリストを表すintストリームを返します。これは一定時間内に実行する必要があります。ストリーム'が強制されるたびに、EmptyまたはCons（v、s'）のいずれかが与えられます。短所の場合、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リストを取得してそれをintstreamに変換する次のことを試みました'：

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

並べ替えられたリストの先頭を取得するためにストリームにアクセスするたびに、リスト内で最小の要素が検出されます。

realあなたは配置関数で正しい道を進んでいます（一種...だけがあるのに、なぜ int の代わりに型があるのか​​わかりません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. 引数は 1 つだけにする必要があります
  2. 以下であることは問題ではないと思います（動作するはずの値よりも小さいだけです....それについてはあまり考えていません）。また、どれが最小かを判断するには、最初にリストの一番下に到達する必要があるため、これはテールファーストです。(* 1 *) が最初で、次に (* 2 *) の各内部呼び出しが最も外側の呼び出しになるようにします。
  3. cons(x, insertsort xs)関数でa を返すので、それは (* 5 *) にあるはずint stream'です。
于 2011-03-16T10:00:16.293 に答える