Time cost of Haskell `seq` operator

Question

This FAQ says that

The seq operator is

seq :: a -> b -> b

x seq y will evaluate x, enough to check that it is not bottom, then discard the result and evaluate y. This might not seem useful, but it means that x is guaranteed to be evaluated before y is considered.

That's awfully nice of Haskell, but does it mean that in

x `seq` f x

the cost of evaluating x will be paid twice ("discard the result")?

Aristotelianism

Perhaps "discard the result" is too strong. It discards the result in the same way const discards its second argument. If the argument has been evaluated, it doesn't somehow unevaluate it or throw away the result, it just ignores it. "x seq y will evaluate x, enough to check that it is not bottom, then ignore the result and evaluate y" is perhaps a better way to phrase it. – Triangulate

It begins to dawn on me how different Haskell's computation model is from my core programming language (C++). – Aristotelianism

Answer 1

The seq function will discard the value of x, but since the value has been evaluated, all references to x are "updated" to no longer point to the unevaluated version of x, but to instead point to the evaluated version. So, even though seq evaluates and discards x, the value has been evaluated for other users of x as well, leading to no repeated evaluations.

Accomplice

Answer 2

No, it's not compute and forget, it's compute - which forces caching.

For example, consider this code:

 let x = 1 + 1
 in x + 1

Since Haskell is lazy, this evaluates to ((1 + 1) + 1). A thunk, containing the sum of a thunk and one, the inner thunk being one plus one.

Let's use javascript, a non-lazy language, to show what this looks like:

 function(){
   var x = function(){ return 1 + 1 };
   return x() + 1;
 }

Chaining together thunks like this can cause stack overflows, if done repeatedly, so seq to the rescue.

let x = 1 + 1
in x `seq` (x + 1)

I'm lying when I tell you this evaluates to (2 + 1), but that's almost true - it's just that the calculation of the 2 is forced to happen before the rest happens (but the 2 is still calculated lazily).

Going back to javascript:

 function(){
   var x = function(){ return 1 + 1 };
   return (function(x){
     return x + 1;
   })( x() );
 }

Cuprite

Answer 3

I believe x will only be evaluated once (and the result retained for future use, as is typical for lazy operations). That behavior is what makes seq useful.

Empanel

Answer 4

Of course seq by itself does not "evaluate" anything. It just records the forcing order dependency. The forcing itself is triggered by pattern-matching. When seq x (f x) is forced, x will be forced first (memoizing the resulting value), and then f x will be forced. Haskell's lazy evaluation means it memoizes the results of forcing of expressions, so no repeat "evaluation" (scary quotes here) will be performed.

I put "evaluation" into scary quotes because it implies full evaluation. In the words of Haskell wikibook,

"Haskell values are highly layered; 'evaluating' a Haskell value could mean evaluating down to any one of these layers."

Let me reiterate: seq by itself does not evaluate anything. seq x x does not evaluate x under any circumstance. seq x (f x) does not evaluate anything when f = id, contrary to what the report seems to have been saying.

Pudendas

Answer 5

You can always check with unsafePerformIO or trace…

import System.IO.Unsafe (unsafePerformIO)

main = print (x `seq` f (x + x))
  where
    f = (+4)
    x = unsafePerformIO $ print "Batman!" >> return 3

Berserker