2

Haskell で単純な (そして真面目ではない) 素数ジェネレーターを書きました。素数を生成し、数値の素数を判断するための相互再帰的な定義を使用します。

primes :: (Integral a) => [a]
primes = 2 : filter isPrime [3, 5..]

isPrime :: (Integral a) => a -> Bool
isPrime m = all (indiv m) (takeWhile (<= (intSqrt m)) primes)

intSqrt :: (Integral a) => a -> a
intSqrt 1 = 1
intSqrt n = div (m + (div (n - 1) m)) 2
  where m = intSqrt (n - 1)

indiv :: (Integral a) => a -> a -> Bool
indiv m n = rem m n /= 0

を参照するたびに、既に生成された素数のサブリストを再構築しているように見えることに気付きましたprimes。

*Main> take 200 primes
[2,3,5,7, ..., 1223]
(2.70 secs, 446142856 bytes)
*Main> take 200 primes
[2,3,5,7, ..., 1223]
(2.49 secs, 445803544 bytes)

しかし、次のような具体的な整数型を使用するように型注釈を変更すると、

primes :: [Integer]
isPrime :: Integer -> Bool

各素数は 1 回だけ生成されます。

*Main> :r
[1 of 1] Compiling Main             ( Primes.hs, interpreted )
Ok, modules loaded: Main.
*Main> take 200 primes
[2,3,5,7, ..., 1223]
(2.15 secs, 378377848 bytes)
*Main> take 200 primes
[2,3,5,7, ..., 1223]
(0.01 secs, 1626984 bytes)

私には好奇心が強いようです。これが起こっている特定の理由はありますか？

4

1 に答える 1

7

あなたが言う時

primes :: [Integer]

thenprimesは定数ですが、

primes :: (Integral a) => [a]

次に、それは隠しパラメータを持つ関数です:Integralどちらの型のインスタンスaです。また、他の関数と同様に、同じパラメーターで呼び出すと、結果が再計算されます (明示的にメモしていない限り)。

于 2013-02-15T21:23:18.703 に答える