Why is this recursive function in Haskell so slow?

Question

I am trying to imitate the Sieve for finding all the prime less than some number using Haskell. I have found other Haskell program that use the Sieve method with great speed. However the following recursive function I wrote is very slow. The code is as follows

sieve' :: Integer -> Integer -> [Integer]

sieve' n 1 = [2 .. n]

sieve' n (k + 1) | [x | x <- sieve' n k, x == k + 1] == [] = sieve' n k

    |otherwise = [x | x <- sieve' n k,  x == k + 1 || not (mod x (k + 1) == 0)]



sieve :: Integer -> [Integer]

sieve n = sieve' n n

Sieve 20 takes about 2 minutes. Sieve 30 still hasn't finished while I am writing this question.

Can anyone explain why this recursive function is so slow. Thanks for any help you can provide.

Answer 1

Your second clause of sieve' function is making the recursive call (sieve' n k) twice, thus making your algorithm perform in exponential time.

To fix this problem you can bind the term to some name, thus ensuring it's evaluated once:

sieve' n (k + 1) | [x | x <- rec, x == k + 1] == [] = rec
    |otherwise = [x | x <- rec,  x == k + 1 || not (mod x (k + 1) == 0)]
  where
    rec = sieve' n k

Update in response to a comment asking why the compiler does not do this automatically:

This kind of transformation, called CSE (common subexpression elimination), is not an optimisation in general, but rather a trade-off between time and space usage, so the decision is better left for a programmer.

Googling for "CSE" reveals some interesting discussions, one of which references this very good example from 1987 book by Simon Peyton Jones called "The Implementation of Functional Programming Languages" (Oh my, this book is almost as old as I am)