Search code examples
haskellexceptionghci

Non-exhaustive patterns in function defined in GHCi

I'm trying to write a sieve of Eratosthenes function that gives a user all Primes from 2 to their upper Limit. So I've written this code:

main = do
putStrLn "Upper Limit"
g <- readLn
let sieve [] = []
let sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p /= 0]
let primes = sieve [2..g]
print primes

The code compiles and is giving me the right solution but I'm getting this exception at the end of the solution:

Exception: Non-exhaustive patterns in function sieve

So I've checked what patterns aren't matched.

warning: [-Wincomplete-patterns]
    Pattern match(es) are non-exhaustive
    In an equation for `sieve': Patterns not matched: (_:_)

warning: [-Wincomplete-patterns]
    Pattern match(es) are non-exhaustive
    In an equation for `sieve': Patterns not matched: []

Which I don't understand since I've given let sieve [] = [] And I thought _ in Haskell means any variable so what does the pattern (_:_) mean? Any help would be appreciated.

Solution

  • The problem is that you define sieve in two separate let statements. As a result the Haskell compiler thinks that you define two separate sieve functions. Therefore the first sieve lacks a (_:_) pattern and the latter the [] pattern.

    If you later use sieve, the Haskell compiler will link to the closest one, so the latter (as a result a call to sieve) in let primes = sieve [2..g] will only know of the second sieve definition (and will thus error on the end of the list).

    You can solve this by using the following let statement:

    let { sieve [] = [] ; sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p /= 0] }