Haskell's `seq` evaluates arguments redundantly?

Question

If I understand the discussion here correctly, seq should not be evaluating a value twice, as in x `seq` x should be evaluating x once.

Then why do I have this behaviour?

λ> :set +s
λ> let fib x = if x <= 1 then x else fib (x - 1) + fib (x - 2)
(0.01 secs, 102,600 bytes)
λ> fib 30
832040
(2.49 secs, 638,088,448 bytes)
λ> let x = fib 30 in x
832040
(2.47 secs, 638,088,792 bytes)
λ> let x = fib 30 in x `seq` x
832040
(4.95 secs, 1,276,067,128 bytes)

which is clearly double evaluating? Am I misunderstanding something?

EDIT: As asked @danidiaz below, I also evaluated

λ> (\x -> x `seq` x) (fib 30)
832040
(2.51 secs, 638,087,888 bytes)
λ> let x = (fib 30) :: Int in x `seq` x
832040
(2.52 secs, 732,476,640 bytes)

which are even more surprising now.

EDIT 2: I see that this question has been marked as a duplicate of an earlier question that asks about the monomorphism restriction. When I encountered this problem, I had no idea that this was due to the restriction. So if someone finds him/herself in my position I guess the answer to this question would be helpful.

What happens if you try `(\x -> x \`seq\` x) (fib 30)` and `let x = (fib 30) :: Int in x \`seq\` x` ? — danidiaz, May 19 '18 at 08:52
The problem is that `fib` has the polymorphic type `(Ord a, Num a) => a -> a`. Hence, in the expression ``x `seq` x``, the first `x` could be instantiated to a different monomorphic type than the second `x`. For example, the first `x` could be an `Int` whereas the second `x` could be a `Double`. There's nothing that forces the two to be the same type. That's the reason why `x` is evaluated twice. — Aadit M Shah, May 19 '18 at 09:08
The solution is simple. Give `fib` a explicit type signature like `let fib :: Int -> Int; fib x = if x <= 1 then x else fib (x - 1) + fib (x - 2)`. — Aadit M Shah, May 19 '18 at 09:09
Avoiding this kind of performance issues is, precisely, why the Monomorphism Restriction was introduced. Without the MR `x` is polymorphic and ``x `seq` x`` actually means something like ``x () `seq` x ()``, as if `x` were a function, and there `seq` will call the function twice (understandably). — chi, May 19 '18 at 12:32

danidiaz · Accepted Answer · 2018-05-19T09:48:01.390

For the first part of this answer, :set -XNoMonomorphismRestriction in ghci. It will be explained later.

Naively, one would expect that in Haskell let x = 5 in (x + 1,x + 2) would always be equivalent to (\x -> (x + 1, x + 2)) 5. But they have different types!

let x = 5 in (x + 1,x + 2) :: (Num a, Num b) => (a, b)

(\x -> (x + 1,x + 2)) 5 :: Num b => (b, b)

The reason is a feature of Haskell called let-bound polymorphism. Unlike lambda-bound identifiers, identifiers bound in a let can be instantiated in different ways in the body of the let. For example:

ghci> let f = id in (f True, f 'a')
(True,'a')

ghci> (\f -> (f True, f 'a')) id
*** ERROR ***

Now, you didn't give a type signature to your fib funtion, and the one that is deduced is something like

fib :: (Ord a, Num a) => a -> a

that will work for different instances of Num like Int, Float, etc.

But because of this, when you write x `seq` x, ghci can't be sure that the two xs are actually of the same type! And if they might be different, then they can't be shared.

That's the reason why (\x -> x `seq` x) (fib 30) does have sharing. Because the x is lambda-bound, the compiler is sure that both occurrences really are the same value. Same for let x = (fib 30) :: Int in x `seq` x because we have removed polymorphism using an explicit type.

There's another way out. Turning on the -XMonomorphismRestriction extension increases the amount of type defaulting, causing let expressions to be more monomorphic than one might expect. That should be enough to recover sharing in this case as well.

Haskell's `seq` evaluates arguments redundantly?

1 Answers1