17

わかりました基本的に、次の場合にオプション1または2のどちらが適用されるかを知るのに問題があります。

naturals = 0 : map (+ 1) naturals

オプションは次
のとおりです。 1.実行はひどいもので、すべてが各ステップで再計算されます。

naturals     = [0]
naturals'    = 0:map (+ 1) [0]          // == [0, 1]
naturals''   = 0:map (+ 1) [0, 1]       // == [0, 1, 2]
naturals'''  = 0:map (+ 1) [0, 1, 2]    // == [0, 1, 2, 3]
naturals'''' = 0:map (+ 1) [0, 1, 2, 3] // == [0, 1, 2, 3, 4]

2.実行はひどいものではありません。リストは常に無限で、map一度だけ適用されます

naturals     = 0:something
                                  |
naturals'    = 0:      map (+ 1) (0:      something)
                                    |
naturals''   = 0:1:    map (+ 1) (0:1:    something')
                                      |
naturals'''  = 0:1:2:  map (+ 1) (0:1:2:  something'')
                                        |
naturals'''' = 0:1:2:3:map (+ 1) (0:1:2:3:something''')

が実行中の場所を|示しmapます。

答えが1つか2つだけかもしれないことは知っていますが、最後の疑問を解消するために、共再帰に関する良い説明へのいくつかの指針をいただければ幸いです:)

4

3 に答える 3

32

あなたが言うように、実行は「ひどい」ことにはなりません。:) ここでは、遅延評価があなたの親友です。怠惰 とはどういう意味ですか?

  1. 結果が本当に必要になる前に物事は評価されません。
  2. 物事は多くても 1 回評価されます。

ここでいう「モノ」とは「サンク」とも呼ばれる「未評価の表現」です。

何が起こるかは次のとおりです。

あなたが定義する

naturals = 0 : map (+1) naturals

単に定義するだけnaturalsでは、それを評価する必要はありません。そのため、最初naturalsは評価されていない式のサンクを指すだけです0 : map (+1) naturals。

naturals = <thunk0>

ある時点で、あなたのプログラムはナチュラルでパターンマッチするかもしれません。(基本的に、Haskell プログラムで評価を強制するのはパターン マッチングだけです。)つまり、プログラムは、naturals が空のリストなのか、先頭要素の後に末尾のリストが続くのかを知る必要があります。これは、定義の右側が評価される場所ですが、 がまたはnaturalsによって構築されているかどうかを確認するために必要な範囲に限られます。[](:)

naturals = 0 : <thunk1>

つまり、Naturals は(:)、head 要素0へのコンストラクターの適用と、まだ評価されていない tail のサンクを指すようになります。(実際には、 head 要素もまだ評価されていないため、実際naturalsには の形式の何かを指し<thunk> : <thunk>ますが、その詳細は省略します。)

テールのサンクが「強制」される、つまり評価されるのは、テールでパターン マッチが行われる可能性のあるプログラムの後半の時点までではありません。これは、式map (+1) naturalsが評価されることを意味します。この式を評価すると、 でmapパターン マッチングが行われます。 がまたはによって構築されnaturalsているかどうかを知る必要があります。この時点で、サンクを指すのではなく、が のアプリケーションをすでに指していることがわかったので、このパターン マッチ によるそれ以上の評価は必要ありません。のアプリケーションは、それ自体のアプリケーションを作成する必要があることを理解するのに十分な をすぐに確認します。naturals[](:)naturals(:)mapmapnaturals(:)map1 : <thunk2>サンクには、フォームの未評価の式が含まれていますmap (+1) <?>。(繰り返しますが、 の代わりに1、実際には のサンクがあり0 + 1ます。) 何を<?>指しているのか? ええと、 の尾部naturals、これはたまたまmap生成していたものです。したがって、私たちは今

naturals = 0 : 1 : <thunk2>

<thunk2>まだ評価されていない式が含まれていますmap (+1) (1 : <thunk2>)。

プログラムのさらに後の時点で、パターン マッチングによって が強制される場合があり<thunk2>ます。

naturals = 0 : 1 : 2 : <thunk3>

<thunk3>まだ評価されていない式が含まれていますmap (+1) (2 : <thunk3>)。などなど。

于 2012-04-21T08:38:11.140 に答える
3

これを理解するのにしばらく時間がかかりましたが、(たとえば) 10 億番目の自然数を見つけたい場合は、

n = nats !! 1000000000

1+ 操作でサンク ビルドアップをヒットします。私は書き直しました（!!）：

nth (x:xs) n = if n==0 then x else x `seq` nth xs (n-1)

nth を書く代わりに、nats の定義を書き直して各要素を強制するいくつかの方法を試しましたが、何もうまくいかないようでした。

于 2012-04-22T18:30:29.403 に答える
1 
map f xs = f (head xs) : map f (tail xs)
p0 = 0 : map (+ 1) p0

-- when p0 is pattern-matched against:
p0 = "0" :Cons: "map (+ 1) {p0}"    
-- when (tail p0) is pattern-matched against:
-- {tail p0} := p1,
p1 = "(+ 1) (head {p0})" :Cons: "map (+ 1) (tail {p0})"       
-- when (tail p1) is pattern-matched against:
-- {tail p1} := p2,
p2 = "(+ 1) (head {p1})" :Cons: "map (+ 1) (tail {p1})"

Haskell のリストは Prolog の制限のないリストによく似ており、リストの再帰はコンスを法とする末尾再帰のようなものです。その logvar をインスタンス化すると (何らかの式からリストのセル値を設定すると)、その値を保持するだけで、元のコンテキストへの参照はなくなります。

naturals( [A|T] ):- T=[B|R], B=A+1, naturals( T ). % "=" sic! ("thunk build-up")

Prolog の厳格さを克服するために、将来のアクセスがプロセスを駆動するようにします。

naturals( nats(0) ).
next( nats(A), A, nats(B) ):- 
  B is A+1.                    % fix the evaluation to be done immediately
take( 0, Next, Z-Z, Next).
take( N, Next, [A|B]-Z, NZ):- N>0, !, next(Next,A,Next1),
  N1 is N-1,                
  take(N1,Next1,B-Z,NZ).

Haskell はこれを難なく処理し、その「ストレージ」は当然怠惰です (つまり、リスト コンストラクターは怠惰であり、言語の性質上、リストの構築はアクセスによってのみ「起こされる」だけです)。

修理

これらを比較してください：

fix f = f (fix f)         
fix f = x where x = f x   -- "co-recursive" fix ?

最初の定義が次のように使用されると、元の懸念が現実になることを確認してください。

g = fix $ (0:) . scanl (+) 1

その経験的な複雑さは、実際には 2 次か、それよりも悪いものです。しかし、2 番目の定義では、線形である必要があります。

于 2012-06-03T22:17:02.733 に答える