Can this prime sieve code be further simplified in Haskell?

Question

The code works well

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

Just GHCI think there is a incomplete patter in next.

Well, this is correct from a grammatical point of view.

But obviously the input of 'next' cannot be empty.

So is there a solution other than adding the declaration ({-# OPTIONS_GHC -Wno-incomplete-patterns #-})?

Answer 1

The exhaustiveness checker knows that next has type Num a => [a] -> [a]. The empty list is a valid argument to next, even if you never actually call next on the empty list.

The key here is that you don't really want Num a => [a] as your argument type. You know it will only be called on an infinite list, so use a type that doesn't have finite lists as values.

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

The Stream library provides a module Data.Stream that defines the Stream type and numerous analogs to list functions.

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)