the seq function and strictness

Question

I have been wondering about this a lot, but I haven't been able to find anything about it.

When using the seq function, how does it then really work? Everywhere, it is just explained saying that seq a b evaluates a, discards the result and returns b.

But what does that really mean? Would the following result in strict evaluation:

foo s t = seq q (bar q t) where
      q = s*t

What I mean is, is q strictly evaluated before being used in bar? And would the following be equivalent:

foo s t = seq (s*t) (bar (s*t) t)

I find it a little hard getting specifics on the functionality of this function.

This might be helpful: http://stackoverflow.com/questions/6872898/haskell-what-is-weak-head-normal-form "Its semantics are that seq x y means that whenever y is evaluated to weak head normal form, x is also evaluated to weak head normal form." — shang, Jun 15 '12 at 07:47

John L · Accepted Answer · 2012-06-17T13:16:51.093

You're not alone. seq is probably one of the most difficult Haskell functions to use properly, for a few different reasons. In your first example:

foo s t = seq q (bar q t) where
      q = s*t

q is evaluated before bar q t is evaluated. If bar q t is never evaluated, q won't be either. So if you have

main = do
    let val = foo 10 20
    return ()

as val is never used, it won't be evaluated. So q won't be evaluated either. If you instead have

main = print (foo 10 20)

the result of foo 10 20 is evaluated (by print), so within foo q is evaluated before the result of bar.

This is also why this doesn't work:

myseq x = seq x x

Semantically, this means the first x will be evaluated before the second x is evaluated. But if the second x is never evaluated, the first one doesn't need to be either. So seq x x is exactly equivalent to x.

Your second example may or may not be the same thing. Here, the expression s*t will be evaluated before bar's output, but it may not be the same s*t as the first parameter to bar. If the compiler performs common sub-expression elimination, it may common-up the two identical expressions. GHC can be fairly conservative about where it does CSE though, so you can't rely on this. If I define bar q t = q*t it does perform the CSE and evaluate s*t before using that value in bar. It may not do so for more complex expressions.

You might also want to know what is meant by strict evaluation. seq evaluates the first argument to weak head normal form (WHNF), which for data types means unpacking the outermost constructor. Consider this:

baz xs y = seq xs (map (*y) xs)

xs must be a list, because of map. When seq evaluates it, it will essentially transform the code into

case xs of
  [] -> map (*y) xs
  (_:_) -> map (*y) xs

This means it will determine if the list is empty or not, then return the second argument. Note that none of the list values are evaluated. So you can do this:

Prelude> seq [undefined] 4
4

but not this

Prelude> seq undefined 5
*** Exception: Prelude.undefined

Whatever data type you use for seqs first argument, evaluating to WHNF will go far enough to figure out the constructor and no further. Unless the data type has components that are marked as strict with a bang pattern. Then all the strict fields will also be evaluated to WHNF.

Edit: (thanks to Daniel Wagner for suggestion in comments)

For functions, seq will evaluate the expression until the function "has a lambda showing", which means that it's ready for application. Here are some examples that might demonstrate what this means:

-- ok, lambda is outermost
Prelude> seq (\x -> undefined) 'a'
'a'

-- not ok.  Because of the inner seq, `undefined` must be evaluated before
-- the lambda is showing
Prelude> seq (seq undefined (\x -> x)) 'b'
*** Exception: Prelude.undefined

If you think of a lambda binding as a (built-in) data constructor, seq on functions is perfectly consistent with using it on data.

Also, "lambda binding" subsumes all types of function definitions, whether defined by lambda notation or as a normal function.

The Controversy section of the HaskellWiki's seq page has a little about some of the consequences of seq in relation to functions.

Just to make it clear: there is no controversy about _when_ `seq` should be a no-op on functions. It's a no-op exactly when the function "has a lambda showing", and not a no-op when some computation must be done before a lambda is top-most (and therefore ready for application). The controversy is about whether we should think about the use of `seq` when designing optimizations -- since `seq` occupies an uncomfortable space in Haskell's semantics. — Daniel Wagner, Jun 15 '12 at 15:52
@DanielWagner - that's a good point. I couldn't think of a good way to explain it (certainly not as well as you did), so instead I pointed to the wiki hoping that readers could infer it themselves from the example there, which is only somewhat related as you point out. I'll add a bit more on this in an edit. — John L, Jun 16 '12 at 04:52
Your answer suggests, that ````seq a b```` evaluates ````a```` at first, but that is following to this article not necessarily true. Hence ````pseq```` exists. https://wiki.haskell.org/Seq "However, it is the case that evaluating b and then a, then returning b is a perfectly legitimate thing to do; it was to prevent this ambiguity that pseq was invented, but that's another story. " — Niklas Peter, Mar 22 '16 at 13:03
@NiklasPeter you're correct that `seq a b` doesn't guarantee ordering between the two, rather it guarantees that if `a` diverges then `seq a b` also diverges. I worded the answer this way as I think it's easier to understand but perhaps there's a better way to do so that is both clear and accurate. — John L, Apr 13 '16 at 04:27
If `seq` has no actual ordering, but simply demands that when the right hand side is WHNF or more, then the left hand side has to be WHNF as well, then is it a common occurance that the right hand side is actually evaluated first? The page here https://wiki.haskell.org/Seq says "In practice, this almost never happens...". — CMCDragonkai, Aug 24 '16 at 06:46
I've never actually checked how common it is. AIUI the usual way it happens is the compiler generates different branches depending on if the RHS diverges or not, or can statically determine that it does diverge, in which case the LHS may not be evaluated at all. Exceptions are frequently involved here, because they're considered divergence. — John L, Aug 27 '16 at 09:02

gfour · Answer 2 · 2012-06-15T13:49:55.170

6

You can think of seq as:

seq a b = case a of
            _ -> b

This will evaluate a to head-normal form (WHNF) and then continue with evaluating b.

Edit after augustss comment: this case ... of is the strict, GHC Core one, which always forces its argument.

edited Jun 15 '12 at 13:49

answered Jun 15 '12 at 12:05

gfour

959
6
9

3

Except that that Haskell does not evaluate `a`. – augustss Jun 15 '12 at 13:28

the seq function and strictness

2 Answers2

Linked