Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

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.

like image 341
RandomStudent Avatar asked May 19 '18 08:05

RandomStudent


1 Answers

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.

like image 78
danidiaz Avatar answered Sep 22 '22 01:09

danidiaz