17

Haskell の学習を支援するために、Project Euler の問題に取り組んでいます。各問題を解決した後、Haskell wiki と照らし合わせて解決策を確認し、より良いコーディング プラクティスを学びます。問題3の解決策は次のとおりです。

primes = 2 : filter ((==1) . length . primeFactors) [3,5..]

primeFactors n = factor n primes
  where
    factor n (p:ps) 
        | p*p > n        = [n]
        | n `mod` p == 0 = p : factor (n `div` p) (p:ps)
        | otherwise      = factor n ps

problem_3 = last (primeFactors 317584931803)

これについての私の単純な解釈は、primesは で定義され、primeFactorsは で定義されているということですprimes。したがって、評価primeFactors 9は次のプロセスに従います。

  1. 評価しfactor 9 primesます。
  2. 最初primesの要素である 2 を求めます。
  3. 次primesの要素を求めます。
  4. このプロセスの一環として、評価しprimeFactors 3ます。
  5. 最初primesの要素である 2 を求めます。
  6. 次primesの要素を求めます。
  7. このプロセスの一環として、評価しprimeFactors 3ます。
  8. ...

つまり、手順 2 ～ 4 が無限に繰り返されます。アルゴリズムが終了するので、明らかに私は間違っています。私はここでどんな間違いを犯していますか？

4

3 に答える 3

17

primeFactors評価している数値の平方根までしか読み取りません。リスト内をさらに検索することはありません。つまり、リストに含めるかどうかをテストしている数に「追いつく」ことはありません。Haskell は遅延しているため、これはprimeFactorsテストが終了することを意味します。

覚えておくべきもう 1 つのことはprimes、これは、アクセスするたびにリストに評価される関数ではなく、遅延構築されたリストであるということです。したがって、15 番目の要素が 1 回アクセスされると、2 回目のアクセスは「無料」になります (たとえば、それ以上の計算は必要ありません)。

于 2011-12-12T03:17:30.313 に答える
8

ケビンの答えは満足のいくものですが、あなたの論理の欠陥を特定させてください. 間違っているのは#6です。だから私たちは評価していますprimeFactors 3：

primeFactors 3          ==>
factor 3 primes         ==>
factor 3 (2 : THUNK)    ==>
2*2 > 3 == True         ==>
[3]

THUNK が であると判断するために、THUNK を評価する必要はありませprimeFactor 3ん[3]。

于 2011-12-12T22:17:28.970 に答える
7

primeFactors 3次の要素は要求せずprimes、最初の要素のみを要求します。これは、 が既に2*2より大きいためです3

于 2011-12-12T05:59:01.903 に答える