1

代码运行良好

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

只是 GHCI 认为next.

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

但显然“下一个”的输入不能为空。

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

4

2 回答 2

2

穷举检查器知道next有 type 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定义了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)
于 2021-12-31T17:38:30.640 回答
0

你的问题已经得到了正确的答案。为了完整起见，另一个选项只是添加我们知道永远不会调用的不需要的子句：

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

在不相关的注释上，您写道它“运作良好”。不幸的是，虽然确实产生了正确的结果，但它的速度非常慢。它的复杂性是二次的，在产生的素数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的时间，给出或取一个对数因子：

{-# 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

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

那么，这个筛子相当于最优试划分，不像问题中的那个。当然，最初提出时，Haskell 还没有视图模式，事实上，还没有 Haskell 本身。

于 2022-02-06T14:02:06.167 回答