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.

As the ultimate authority on Eratosthenes' sieve in Haskell you should take a look at Melissa O'Neill's article (lambda-the-ultimate.org/node/3127) in the Journal of Functional Programming (2009). There should be a few more tricks in it. — Volker Stolz
– Volker Stolz, Commented Feb 11, 2012 at 20:58

Rotsor · Accepted Answer · 2011-08-21 09:38:03Z

16

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)

edited Aug 21, 2011 at 9:38

answered Aug 21, 2011 at 6:08

Rotsor

13.8k6 gold badges46 silver badges58 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

user898033 Over a year ago

Thanks, this was exactly the problem. It runs much faster now.

Jon Purdy Over a year ago

I find it odd that the compiler missed this optimisation.

Collectives™ on Stack Overflow

Why is this recursive function in Haskell so slow?

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related