Haskell's `seq` evaluates arguments redundantly? [duplicate]

  • A+
Category:Languages

This question already has an answer here:

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.


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.

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: