0

我创建了以下 Haskell 素数函数（在 ghci 中）：

let pi :: Int -> Int -> Int;
pi 1 _ = 2;
pi x y = if all (/=0) (map (rem y) [pi z 2| z <- [1..(x-1)]]) then y else pi x (y+1);

请不要介意第二个/记忆的参数（它应该总是从 2 开始）。当然，正如预期的那样，thunk 很快就会失控。确认 43 是第 14 个素数需要超过 19 秒...

Prelude> pi 10 2
29
(0.14 secs, 23924220 bytes)
Prelude> pi 11 2
31
(0.48 secs, 71394644 bytes)
Prelude> pi 12 2
37
(1.64 secs, 244218772 bytes)
Prelude> pi 13 2
41
(5.57 secs, 832500204 bytes)
Prelude> pi 14 2
43
(19.11 secs, 2841677968 bytes)

我已经阅读了严格性（seq主要$!是），但我所有的尝试都花费了更长的时间！

4

2 回答 2

3

如果您添加trace到您的函数以查看对哪些调用进行pi评估，您将看到您的实现不使用已经计算的值。

import Prelude hiding (pi)
import Debug.Trace (trace)

pi :: Int -> Int -> Int
pi 1 y = trace ("pi 1 " ++ show y) 2
pi x y =
    trace ("pi " ++ show x ++ " " ++ show y) $
    if all (/=0) (map (rem y) [pi z 2| z <- [1..(x-1)]])
        then y
        else pi x (y+1)

评估pi 3 2现在打印以下内容（我添加了空格，以显示一种结构）：

pi 3 2
    pi 1 2
pi 3 3
    pi 1 2
    pi 2 2
        pi 1 2
    pi 2 3
        pi 1 2
pi 3 4
    pi 1 2
pi 3 5
    pi 1 2
    pi 2 2
        pi 1 2
    pi 2 3
        pi 1 2

您会看到很多冗余，并且对于更高的x. 懒惰在这里不是你的问题，而是你没有传播你到目前为止计算的值。换句话说，问题出在你的方法上，现在很难修复它。

于 2014-05-23T18:06:41.853 回答
0 
pi = (!!) primes . subtract 1

primes = 2 : filter isPrime [3..]

isPrime n = all ((/=) 0 . rem n)) $ takeWhile ((>=) n . (^2)) primes

> pi 14
43
it :: Integer
(0.00 secs, 0 bytes)
于 2014-05-23T21:03:08.627 回答