haskell -++，last & init 比 :, head & tail 快？

Question

给定这两种编写函数的方法，该函数可以找到不超过特定数字的所有素数:

primes1 = iterate
    (\ps -> ps ++ [([x |
        x <- [last ps + 1..],
        all (\p -> x `mod` p /= 0) ps] !! 0)])
    [2]

primesTo1 :: Integer -> [Integer]
primesTo1 n = init $ head $ dropWhile (\p -> last p <= n) primes1

primes2 = iterate
    (\ps -> ([x |
            x <- [head ps + 1..],
            all (\p -> x `mod` p /= 0) ps] !! 0)
        : ps)
    [2]

primesTo2 :: Integer -> [Integer]
primesTo2 n = tail $ head $ dropWhile (\p -> head p <= n) primes2

为什么 primesTo1 比 primesTo2 快很多，尽管使用了不同的函数； primesTo1 使用 ++, last & init 而不是 :, primesTo2 中使用的 head 和 tail。

使用 :set +s 的 ghci 输出:

*Main> primesTo1 10000
...
(0.51 secs, 124779776 bytes)
*Main> primesTo2 10000
...
(3.30 secs, 570648032 bytes)

用 ghc -O2 编译:

$ time ./primes1
...
./primes1  0.06s user 0.00s system 68% cpu 0.089 total
$ time ./primes2
...
./primes2  0.28s user 0.00s system 98% cpu 0.283 total

---

注意:我不是在为 Haskell 寻找最佳素数生成器，我只是对这两个函数的速度差异感到困惑。

Answer 1

正如“n.m.”所指出的，这是因为 primes2 首先尝试除以找到的最大素数，而 primes1 从最小素数开始。

因此，在 all 中使用它们之前，首先反转当前素数的列表实际上比 primes1 和 primes2 都快:

primes3 = iterate
    (\ps -> ([x |
            x <- [head ps + 1..],
            all (\p -> x `mod` p /= 0) $ reverse ps] !! 0)
        : ps)
    [2]

primesTo3 :: Integer -> [Integer]
primesTo3 n = tail $ head $ dropWhile (\p -> head p <= n) primes3

ghci 以 10000 作为参数的速度:

*Main> primesTo3 10000
...
(0.41 secs, 241128512 bytes)

并用 ghc -O2 编译:

$ time ./primes3
...
./primes  0.05s user 0.00s system 24% cpu 0.209 total