性能 – 使用无限列表时执行速度较慢

我开始尝试让我的头围绕着哈斯克尔表演,以及让事情快速和缓慢的原因,我对此感到有些困惑.

我有一个函数的两个实现,它生成一个特定值的素数列表.第一个是直接关闭Haskell维基：

primesTo :: (Ord a, Num a, Enum a) => a -> [a]
primesTo m = eratos [2..m]  where
   eratos []     = []
   eratos (p:xs) = p : eratos (xs `minus` [p*p, p*p+p..m])

第二个是相同的,但在内部使用无限列表：

primes2 :: (Ord a, Num a, Enum a) => a -> [a]
primes2 m = takeWhile (<= m) (eratos [2..])  where
   eratos []     = []
   eratos (p:xs) = p : eratos (xs `minus` [p*p, p*p+p..])

在这两种情况下,减函数是：

minus :: (Ord a) => [a] -> [a] -> [a]
minus (x:xs) (y:ys) = case (compare x y) of 
           LT -> x : minus  xs  (y:ys)
           EQ ->     minus  xs     ys 
           GT ->     minus (x:xs)  ys
minus  xs _ = xs

后者的实现比前者慢很多(约100倍),我不明白为什么.我本以为haskell的懒惰评估会使它们在引擎盖下相当等效.

对于问题而言,这显然是一个简化的测试用例 – 在现实生活中,优化将没有问题(虽然我不明白为什么需要它),但对我来说,只生成一个无限的素数列表的函数是比有限列表更有用,但看起来效率较慢.

在我看来,两者之间存在很大差异

(xs `minus` [p*p, p*p+p..m])  -- primesTo
(xs `minus` [p*p, p*p+p..])   -- primes2

该函数成对减去成对列表的步骤,并在一个列表到达结尾时终止.在上面的第一个减去表达式中,当后一个列表用完时,这不会超过(m-p * p)/ p步.在第二个中,它总是采用长度xs的顺序.

因此,您的无限列表已禁用至少一个有意义的优化.