Haskell这个素数筛码可以进一步简化吗？

Question

代码运行良好

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

只是 GHCI 认为 next 中有一个不完整的模式。

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

但是显然'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 library provides a module Data.Stream that defines the Stream 类型和列表函数的众多类似物。

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

您的问题已经有了正确的答案。为了完整起见，另一个选项只是添加不需要的子句，即 we know will never be called:

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

另一个更“old-style”的解决方案是通过显式调用 head 和 tail 来分析参数（非常 而不是 推荐，一般情况下）：

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

这或许可以算作一种简化。

在一个不相关的注释中，您写道它“运行良好”。不幸的是，虽然确实产生了正确的结果，但速度非常慢。因为每次总是只从输入列表中取出一个元素，所以它的时间复杂度是 quadratic n 产生的素数。换句话说，primes !! n 需要 n 的二次方时间。 Empirically,

> 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

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

那么这个筛相当于最优试分，不像题中的那个。当然刚提出的时候in 1976，Haskell还没有view patterns，实际上还没有Haskell本身。

Haskell这个素数筛码可以进一步简化吗？

Can this prime sieve code be further simplified in Haskell?

haskell

primes

sieve

non-exhaustive-patterns