1

そこで、haskell で素数のリストを生成するプログラムを作成しています。以下に示す 2 つの関数を作成します。

{-
Given a list of prime numbers, this function will
add the next prime number to the list. So, given the 
list [2, 3], it will return [2, 3, 5]
-}
nextPrime xs =  xs ++ [lastVal + nextCounts]
    where
        lastVal       =  (head . reverse) $ xs
        isNextPrime y =  0 `elem` ( map ( y `mod`) xs )
        nextVals      =  (map isNextPrime [lastVal, lastVal+1 ..] )
        nextCounts    =  length $ takeWhile (\x -> x) nextVals


allPrimes xs = allPrimes np
    where 
        np = nextPrime xs

これで、関数「nextPrime」が本来の機能を実行しています。ただし、以下に示すように allPrimes を呼び出すと、次のようになります。

take 5 $ allPrimes [2,3]

プログラムは無限ループに入ります。Haskells の「怠惰な」機能がこれらすべてを処理するはずだと思っていましたか? 何が足りないの??

4

3 に答える 3

1

何がうまくいかないのかについての良い説明についてはドリューの答えを読んでいますが、これを機能させる方法の簡単なデモンストレーションについては、

nextPrime xs =  xs ++ [lastVal + nextCounts]
  where
    lastVal       =  (head . reverse) $ xs
    isNextPrime y =  0 `elem` ( map ( y `mod`) xs )
    -- ^ Style note, this name is super misleading, since it returns
    -- false when the number is prime :)
    nextVals      =  (map isNextPrime [lastVal, lastVal+1 ..] )
    nextCounts    =  length $ takeWhile (\x -> x) nextVals


allPrimes xs = last np : allPrimes np
  where np = nextPrime xs

これで、リストを作成しながら進みます。haskell は遅延しているため、 をnp評価する前にの最後の要素を取得できallPrimes npます。つまり、無限ループではありませんhead (a : infiniteLoop)。a

しかし、これは本当に非効率的です。Haskell ではリストは個別にリンクされているため、Python などとlastはO(n)対照的です。O(1)また、最初のリストの長さについては++コストがかかります。O(n)

その代わり

 nextPrime xs = lastVal + nextCounts
   where lastVal     = head xs
         isNextPrime = 0 `elem` map (y `rem`) xs
         nextVals    = map isNextPrime [lastVal ..]
         nextCount   = length $ takeWhile id nextVals

 allPrimes xs = p : allPrimes (p:xs)
    where p = nextPrime xs

そのため、コストのかかるトラバーサルを避けるために、リストを逆にしておきます。単純化することもできますnextPrime

import Data.Maybe
nextPrime xs = fromJust nextPrime
  where isPrime y =  not $ 0 `elem` map (rem y) xs
        nextPrime = find isPrime [head xs ..]

素数である最初の要素のリストを検索し、それをリストに追加するだけです。次のfromJust素数がない場合、エラーが発生します。しかし、常に次の素数があることが数学的にわかっているので、これは安全です。

最終的に、コードは次のようになります

 import Data.Maybe
 import Data.List
 nextPrime xs = fromJust nextPrime
   where isPrime y = 0 `notElem` map (rem y) xs
         nextPrime = find isPrime [head xs ..]
 allPrimes xs = p : allPrimes (p:xs)
   where p = nextPrime xs

それを評価するには、 を呼び出しますallPrimes [2]。

isPrimeこれを行うためのさらにクリーンな方法は、数値が素数かどうかを返す関数を使用することです。そして、ただ持つために

allPrimes = filter isPrime [1..]

しかし、それは好奇心旺盛な読者に任せます。

于 2013-09-29T17:56:32.283 に答える