2

I wanted to use this code of Sieve of Eratosthenes from this page: http://en.literateprograms.org/Sieve_of_Eratosthenes_(Haskell)#chunk def:primes_naive

Only a bit modified, so it only shows the primes up to a number:

primes :: Integral a => a -> [a]
primes m  = sieve [2..m]
  where
    sieve (p:xs) = p : sieve [x|x <- xs, x `mod` p > 0]

But in WinGHCi always the error comes (example 10):

primes 10
[2,3,5,7*Main> *** Exception: eratosthenes.hs:4:5-55: Non-exhaustive patterns in function sieve

I know this error from recursive functions, where for example cases are missing, but what is missing here?

Will Ness
  • 70,110
  • 9
  • 98
  • 181
Rainflow
  • 161
  • 1
  • 2
  • 5
  • 1
    Although the formulation looks like the sieve of Eratosthenes, the evaluation is actually different and very slow. You might be interested in [this article](https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf). – Sam van Herwaarden Jan 12 '16 at 10:20
  • change it to ``sieve (p:xs) | p*p<=m = p : sieve [x|x <- xs, x `mod` p > 0] | otherwise = (p:xs)`` for a fix and a tremendous speedup. – Will Ness Aug 12 '16 at 16:37

2 Answers2

5

Unlike the version on the website, your function will eventually consume the whole list, so you need a pattern matching for []

sieve [] = []
zakyggaps
  • 3,070
  • 2
  • 15
  • 25
2

As zakyggaps said, your version evaluates the function sieve with a finite list [2..m] which eventually will evaluate the empty list case.

Another way to solve this problem is to use the function takeWhile :: (a -> Bool) -> [a] -> [a] to evaluate sieve [2..] until you reach your limit m.

primes :: Integral a => a -> [a]
primes m  = takeWhile (\p -> p <= m) $ sieve [2..]
  where
    sieve (p:xs) = p : sieve [x|x <- xs, x `mod` p > 0]
Lilymonade
  • 465
  • 4
  • 11