8

現在、IFPH チャプター 7 の質問に行き詰まっています。

練習問題 7.1.2には次のように書かれています。

「の定義の 1 つsortはsort = foldr insert []、

insert x [] = [x]
insert x (y:ys) = if x <= y then x : y : ys else y : insert x ys

式 の熱心なおよび怠惰な評価削減シーケンスを詳細に示し、sort [3,4,2,1]それらの違いを説明します"

ここで、最初に熱心な評価還元シーケンスから始めました。これは、最も内側の還元であると想定しています。

私にはこれが得られます...

sort [3,4,2,1] 
=> foldr insert [] [3,4,2,1]
=> insert 3 (foldr insert [] [4,2,1])
=> insert 3 (insert 4 (foldr insert [] [2,1]
=> insert 3 (insert 4 (insert 2 (foldr insert [] [1])))
=> insert 3 (insert 4 (insert 2 (insert 1 (foldr [] []))))
=> insert 3 (insert 4 (insert 2 (insert 1 [])))
=> insert 3 (insert 4 (insert 2 [1]))
=> insert 3 (insert 4 (1 : insert 2 []))
=> insert 3 (insert 4 (1 : [2]))
=> insert 3 (1 : insert 4 [2])
=> insert 3 (1 : 2 : insert 4 [])
=> insert 3 (1 : 2 : [4])
=> insert 3 [1,2,4]
=> 1 : insert 3 [2,4]
=> 1 : 2 : insert 2 : [4]
=> 1 : 2 : 3 : [4]
=> [1,2,3,4]

これはソートされたリストです。

遅延評価の場合、私が考えることができる唯一の削減シーケンスは、熱心な評価の場合とまったく同じです。確かに、Haskell は遅延評価のために左端の最も外側の評価を行います。しかし、内部の計算が完了するまで、リストのほとんどを操作できるとは思いません。

この推論は正しいですか？直感は私にノーと言います。

誰かが遅延評価削減シーケンスを実行する方法を指摘できれば、それは素晴らしいことです。

ありがとう

4

1 に答える 1

10

を含む行で

insert 3 (1 : insert 4 [2])

insert次の行を与えて、計算を実行できるように外側への2番目の引数を十分に計算しました

if 3 <= 1 then 3 : 1 : insert 4 [2] else 1 : insert 3 (insert 4 [2])

次の計算を次のように指定して、if ステートメントを実行できるようになりました。

1 : insert 3 (insert 4 [2])     -- (LAZY)

あなたが熱心な評価で持っているものではなく：

insert 3 (1 : 2 : insert 4 [])  -- (EAGER)

遅延評価を使用すると、結果の最初の要素が1リストの残りをソートする前に計算されます。これは、最初の要素が何であるかを見つける前に、リストの末尾のほぼ全体をソートする熱心な評価とは対照的です。

于 2012-05-21T08:25:24.847 に答える