About strictness in haskell

Question

I've created the following Haskell prime function (within ghci):

let pi :: Int -> Int -> Int;
pi 1 _ = 2;
pi x y = if all (/=0) (map (rem y) [pi z 2| z <- [1..(x-1)]]) then y else pi x (y+1);

Please don't mind the second/memoized argument (it should always start out at 2). Of course as expected the thunks get out of control quick. It takes over 19sec to confirm 43 is the 14th prime...

Prelude> pi 10 2
29
(0.14 secs, 23924220 bytes)
Prelude> pi 11 2
31
(0.48 secs, 71394644 bytes)
Prelude> pi 12 2
37
(1.64 secs, 244218772 bytes)
Prelude> pi 13 2
41
(5.57 secs, 832500204 bytes)
Prelude> pi 14 2
43
(19.11 secs, 2841677968 bytes)

I've read up on strictness (seq,$! mainly) but all my attempts took even longer!

Answer 1

If you add trace to your function to see which calls to pi are evaluated, you'll see that your implementation doesn't use already calculated values.

import Prelude hiding (pi)
import Debug.Trace (trace)

pi :: Int -> Int -> Int
pi 1 y = trace ("pi 1 " ++ show y) 2
pi x y =
    trace ("pi " ++ show x ++ " " ++ show y) $
    if all (/=0) (map (rem y) [pi z 2| z <- [1..(x-1)]])
        then y
        else pi x (y+1)

Evaluating pi 3 2 now prints the following (with spaces added by me, to show kind of a structure):

pi 3 2
    pi 1 2
pi 3 3
    pi 1 2
    pi 2 2
        pi 1 2
    pi 2 3
        pi 1 2
pi 3 4
    pi 1 2
pi 3 5
    pi 1 2
    pi 2 2
        pi 1 2
    pi 2 3
        pi 1 2

You see a lot of redundancy, and this gets exponentially worse for higher values of x. Laziness isn't your problem here, it's that you're not propagating the values you have calculated so far. In other words, the problem is with your approach, and it's hard to fix it as it is right now.

Answer 2

pi = (!!) primes . subtract 1

primes = 2 : filter isPrime [3..]

isPrime n = all ((/=) 0 . rem n)) $ takeWhile ((>=) n . (^2)) primes

> pi 14
43
it :: Integer
(0.00 secs, 0 bytes)