这个素数筛代码可以在Haskell中进一步简化吗

Question

代码运行良好

primes = next [2 ..]
  where
    next (p : ps) = p : next ts
      where
        ts = filter (x -> mod x p /= 0) ps

GHCI认为CCD_ 1中存在不完全模式。

从语法的角度来看，这是正确的。

但显然，"next"的输入不能为空。

那么，除了添加声明之外，还有其他解决方案吗({-# OPTIONS_GHC -Wno-incomplete-patterns #-}(？

Answer 1

穷尽性检查器知道next具有类型Num a => [a] -> [a]。空列表是next的有效参数，即使您从未在空列表上实际调用next。

这里的关键是，您并不是真的希望Num a => [a]作为您的参数类型。您知道它只会在无限列表上调用，所以使用一个不具有有限列表的类型作为值。

data Stream a = Cons a (Stream a)
sequence :: Num a => a -> Stream a
sequence x = Cons x (sequence (x + 1))
filterStream :: (a -> Bool) -> Stream a -> Stream a
filterStream p (Cons x xs) | p x = Cons x (filterStream p xs)
                           | otherwise = filterStream p xs
-- Since you'll probably want a list of values, not just a stream of them, at some point.
toList :: Stream a -> [a]
toList (Cons x xs) = x : toList xs
primes :: Stream Integer
primes = next (sequence 2)
  where 
    next (Cons x xs) = Cons x xs'
      where xs' = filterStream (x -> mod x p /= 0) xs

Stream库提供了一个模块Data.Stream，该模块定义了next0类型和许多用于列出函数的类似物。

import qualified Data.Stream as S
-- S.toList exists as well.
primes :: Stream Integer
primes = next (S.fromList [2..])
  where next (Cons x xs) = Cons x (S.filter (x -> mod x p /= 0) xs)

Answer 2

您的问题已经得到了正确的答案。为了完整性，另一种选择只是添加不需要的子句，我们知道永远不会被调用：

primes = next [2 ..]
  where
  next (p : xs) =
       p : next [x | x <- xs, mod x p > 0]
  next _ = undefined

另一个，更多的"；旧式"；解决方案是通过显式调用head和tail来分析参数(通常不推荐(：

primes = next [2 ..]
  where
  next xs = let { p = head xs } in
       p : next [x | x <- tail xs, mod x p > 0]

这也许可以算是一种简化。

在一个无关的音符上，你写道：；工作良好"；。不幸的是，虽然它确实产生了正确的结果，但速度非常缓慢。由于每次从输入列表中只取一个元素，因此它的时间复杂度是所产生素数的数量n中的二次。换句话说，primes !! n在n中为时间二次型。根据经验，

> primes !! 1000
7927     -- (0.27 secs, 102987392 bytes)
> primes !! 2000
17393    -- (1.00 secs, 413106616 bytes)
> primes !! 3000
27457    -- (2.23 secs, 952005872 bytes)
> logBase (2/1) (1.00 / 0.27)
1.8889686876112561                -- n^1.9
> logBase (3/2) (2.23 / 1.00)
1.9779792870810489                -- n^2.0

事实上，整组元素可以同时从输入中提取，直到当前素数的平方，因此代码只需要大约~n^1.5时间，给定或取log因子：

{-# LANGUAGE ViewPatterns #-}
primes_ = 2 : next primes_ [3 ..] 
  where 
  next (p : ps) (span (< p*p) -> (h, xs)) = 
      h ++ next ps [x | x <- xs, mod x p > 0]
  next _ _ = undefined

根据经验，我们再次得到

> primes !! 3000
27457     -- (0.08 secs,   29980864 bytes)
> primes !! 30000
350381    -- (1.81 secs,  668764336 bytes)
> primes !! 60000
746777    -- (4.74 secs, 1785785848 bytes)
> primes !! 100000
1299721   -- (9.87 secs, 3633306112 bytes)
> logBase (6/3)  (4.74 / 1.81)
1.388897361815054                 -- n^1.4
> logBase (10/6) (9.87 / 4.74)
1.4358377567888103                -- n^1.45

正如我们在这里看到的，复杂性优势也表现为绝对值上的巨大加速。

因此这个筛相当于最优试验划分，与问题中的不同。当然，当它在1976年首次提出时，Haskell还没有视图模式，事实上还没有Haskell本身。