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.
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 x
s 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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With