Understanding Haskell seq

Question

I'm a Haskell newbie having problems understanding seq, which I've summarized in the example below.

Here are 2 implementations of the same (silly) function. The function takes a positive int n and returns the tuple (n,n). The answer is produced by counting up from (0,0) using a helper function with a tuple accumulator. To avoid building up a large thunk I used seq to make the accumulator strict.

In testSeq1 the contents of the tuple are strict, whereas in testSeq2 the tuple itself is strict. I thought these 2 implementations would perform identically. But actually the 'total memory in use' is only 1MB for testSeq1 but a massive 187MB for testSeq2 (when tested using n = 1000000).

What's wrong with testSeq2?

testSeq1 :: Int -> (Int,Int)
testSeq1 n = impl n (0,0) where
    impl 0 (a,b) = (a,b)
    impl i (a,b) = seq a $ seq b $ impl (i-1) (a+1, b+1)

testSeq2 :: Int -> (Int,Int)
testSeq2 n = impl n (0,0) where
    impl 0 acc = acc
    impl i acc = seq acc $ impl (i-1) ((fst acc)+1, (snd acc)+1)

Answer 1

seqing a tuple only forces it to be evaluated as much as to expose its tuple constructor, but will not evaluate its components.

That is,

let pair = id (1+1, 2+2)
in seq pair $ ...

will apply id and produce (_thunk1, _thunk2) where the _thunks point to the additions, which are not evaluated at this time.

In your second example, you are forcing the accumulator acc, but not its components, hence some large thunks still build up.

You could use a so-called evaluation strategy such as:

evalPair :: (a,b) -> ()
evalPair (a,b) = seq a $ seq b ()

testSeq2 :: Int -> (Int,Int)
testSeq2 n = impl n (0,0) where
impl 0 acc = acc
impl i acc = seq (evalPair acc) $ impl (i-1) ((fst acc)+1, (snd acc)+1)

But then, testSeq1 is a simpler approach.

As another alternative, use strict tuples. Such tuples never have thunks for components, but only evaluated results. Forcing the tuple constructor will then force the components as well, as you expected.

import Data.Strict.Tuple

testSeq2 :: Int -> Pair Int Int
testSeq2 n = impl n (0 :!: 0) where
impl 0 acc = acc
impl i acc = seq acc $ impl (i-1) ((fst acc + 1) :!: (snd acc + 1))