9

私は現在、Doets と Van Eijck による「The Haskell Road to Logic, Math, and Programming」という本を読んでいます。私はこの本まで関数型プログラミング言語に触れたことがないので、覚えておいてください。

本のまだ早い段階で、素数性テストの次のコードが提供されます。

ldp :: Integer -> Integer
ldp n = ldpf primes1 n

ldpf :: [Integer] -> Integer -> Integer
ldpf (p:ps) n | rem n p == 0 = p 
              | p^2 > n      = n
              | otherwise    = ldpf ps n

primes1 :: [Integer]
primes1 = 2 : filter prime [3..]

prime :: Integer -> Bool
prime n | n < 1     = error "not a positive integer"
        | n == 1    = False 
        | otherwise = ldp n == n

ldp が primes1 を呼び出し、それが prime を呼び出し、それが ldp を再度呼び出すという、一見循環的なプログラミングが行われています。この本は、プログラムが実行されて終了する理由についての説明としてこれを提供していますが、

ldp は、素数のリストである primes1 を呼び出します。これは「怠惰なリスト」の最初の例です。リストは、さらに処理するために必要なリストの部分のみを計算するため、「レイジー」と呼ばれます。primes1 を定義するには、素数性のテストが必要ですが、そのテスト自体が関数 LD の観点から定義されており、これが primes1 を参照します。輪になって走り回っているようです。この円は、2 の素数性テストを回避することで非悪性にすることができます。2 が素数であることが与えられた場合、3 が素数であるという LD チェックで 2 の素数性を使用できます。そして走っている

私はこの説明を理解していると思いますが、誰かが素人の言葉で説明できれば非常にありがたいです:

  1. 「怠惰なリスト」とは何ですか?また、このコンテキストでどのように適用されますか?
  2. 2 が素数であることを知っていると、どのようにしてプログラムが悪意を持たなくなるのでしょうか?

どんな答えでも大歓迎です。

4

3 に答える 3

9

最初に注意すべきことは、コード自体は何もしないということです。これは単なる数式の集まりであり、それらから何らかの値を抽出しようとするまで、それがどれほど循環的であるかは問題ではありません。どうやってそれを行うのですか？

できること:

print $ take 1 primes1

ここは問題ありません。再帰コードを見なくても、primes1 の最初の値を取得できます。明示的に 2 として存在します。

print $ take 3 primes1

primes1いくつかの値を取得するために展開してみましょう。これらの式を管理しやすくするために、ここではprintandtakeの部分を無視していますが、この作業を行っているのはそれらがあるためだけであることを覚えておいてください。primes1は：

primes1 = 2 : filter prime [3..]

最初の値があり、2 番目への最初のステップはフィルターの展開です。これが厳密な言語である場合、最初に [3..] を拡張しようとして行き詰まります。可能なフィルターの定義は次のとおりです。

filter f (x:xs) = if f x then x : filter f xs else filter f xs

これは次を与えます:

primes1 = 2 : if prime 3 then 3 : filter prime [4..] else filter prime [4..]

次のステップは、が真か偽かを判断する必要があるため、とprime 3の定義を使用して展開してみましょう。primeldpldpf

primes1 = 2 : if ldp 3 == 3 then 3 : filter prime [4..] else filter prime [4..]
primes1 = 2 : if ldpf primes1 3 == 3 then 3 : filter prime [4..] else filter prime [4..]

ここで興味深いことに、primes1 は自分自身を参照し、ldpf はその計算を行うために最初の値を必要とします。幸いなことに、最初の値は簡単に取得できます。

primes1 = 2 : if ldpf (2 : tail primes) 3 == 3 then 3 : filter prime [4..] else filter prime [4..]

ここで、ldpf と find にガード句を適用し2^2 > 3ますldpf (2 : tail primes) 3 = 3。

primes1 = 2 : if 3 == 3 then 3 : filter prime [4..] else filter prime [4..]
primes1 = 2 : 3 : filter prime [4..]

これで 2 番目の値が得られました。評価の右辺が特に大きくなることはなく、再帰ループを遠くまでたどる必要がないことに注意してください。

primes1 = 2 : 3 : if prime 4 then 4 : filter prime [5..] else filter prime [5..]
primes1 = 2 : 3 : if ldp 4 == 4 then 4 : filter prime [5..] else filter prime [5..]
primes1 = 2 : 3 : if ldpf primes1 4 == 4 then 4 : filter prime [5..] else filter prime [5..]
primes1 = 2 : 3 : if ldpf (2 : tail primes1) 4 == 4 then 4 : filter prime [5..] else filter prime [5..]

ガード節を使用するため、rem 4 2 == 0ここでは 2 が得られます。

primes1 = 2 : 3 : if 2 == 4 then 4 : filter prime [5..] else filter prime [5..]
primes1 = 2 : 3 : filter prime [5..]
primes1 = 2 : 3 : if prime 5 then 5 : filter prime [6..] else filter prime [6..]
primes1 = 2 : 3 : if ldp 5 == 5 then 5 : filter prime [6..] else filter prime [6..]
primes1 = 2 : 3 : if ldpf primes1 5 == 5 then 5 : filter prime [6..] else filter prime [6..]
primes1 = 2 : 3 : if ldpf (2 : tail primes) 5 == 5 then 5 : filter prime [6..] else filter prime [6..]

ガード マッチがないため、次のように再帰します。

primes1 = 2 : 3 : if ldpf (tail primes) 5 == 5 then 5 : filter prime [6..] else filter prime [6..]
primes1 = 2 : 3 : if ldpf (3 : tail (tail primes)) 5 == 5 then 5 : filter prime [6..] else filter prime [6..]

その3^2 > 5式は 5 です。

primes1 = 2 : 3 : if 5 == 5 then 5 : filter prime [6..] else filter prime [6..]
primes1 = 2 : 3 : 5 : filter prime [6..]

必要な値は 3 つだけなので、評価を停止できます。

それで、今あなたの質問に答えます。遅延リストは、必要なものを評価するだけでよいリストであり、再帰ステップに到達したときに常に十分な値が計算済みであることを保証するため、この 2 が役立ちます。(2 がわからない場合に式を展開すると、すぐにループに陥ってしまうことを想像してください。)

于 2010-08-18T08:52:01.627 に答える
6

順番に：

怠惰とは、可能な場合ではなく、必要な場合にのみ式を評価するという特性です。遅延リストは、無限になる可能性があるリストです。評価が遅延していない場合、無限リストを評価しようとするのは明らかに悪い考えです。

「悪意のない」が何を意味するのかはわかりませんが、値「2」を既知の素数として持つと、再帰の基本ケースが提供されることがわかると思います。つまり、プログラムが実行する特定の入力を提供します。終了します。再帰関数 (または実際には相互再帰関数のセット) を記述するには、通常、アプリケーションの連続するステップで、この基本ケースに向かって入力値を減らす必要があります。

参考までに、この形のプログラム フラグメントは通常相互再帰的と呼ばれます。「循環参照」という用語は、この場合に実際に適用するものではありません。

于 2010-08-17T19:51:28.637 に答える
3

Haskell の決定的な特徴の 1 つは、その遅延性です。リストはその話の一部にすぎません。基本的に、Haskell は次の時点まで計算を実行しません。

  1. 計算の値は、必要な何かを計算するために必要です...
  2. Haskell に、他の方法よりも早く何かを計算するように指示しました。

したがって、primes1関数はInteger値のリストを生成しますが、全体の計算を満たすのに必要な以上のものは生成しません。それでも、次のように定義した場合:

primes1 :: [Integer]
primes1 = filter prime [2..]

問題があるでしょう。(間接的に)を評価primes1することによって、そのシーケンスの最初の値を生成しようとします。prime 2ldp 2primes1

によって生成されたシーケンスの最初の値として 2 を直接返すprimes1ことで、無限ループを回避できます。シーケンスで生成される後続の値ごとに、後続の値の計算の一部としてprimes1によって評価される前の値が既に生成されています。ldp

于 2010-08-17T20:06:25.637 に答える