haskellconcurrencylazy-evaluationweak-head-normal-form

The example of strict evaluation from Simon Marlow's book "Parallel and Concurrent Programming in Haskell"

Simon Marlow in his book "Parallel and Concurrent Programming in Haskell" writes:

The insert operation hadthis line:

putMVar m (Map.insert name number book)

This places in the MVar the unevaluated expression Map.insert name number book. If we were to do many insert operations consecutively, the MVar would build up a large chain of unevaluated expressions. To get brief locking and no space leaks, we need to use a trick:

let book' = Map.insert name number book
putMVar m book'
seq book' (return ())

With this sequence, we’re storing an unevaluated expression in the MVar, but it is evaluated immediately after the putMVar.

I don't get it. seq a b operation evaluates a in weak head normal form. So there will be unevaluated expression. As I can see only the Map constructor will be evaluated and all of it contents will be unevaluated.

Solution

  • As I can see only the Map constructor will be evaluated and all of it contents will be unevaluated.

    Internally, the Map type is implemented using a strict tree. Either the whole tree spine gets evaluated, or none of it. Here's a snippet from the library code:

    data Map k a  = Bin {-# UNPACK #-} !Size !k a !(Map k a) !(Map k a)
              | Tip

    The strictness annotations (!) prevent unevaluated values to be stored as subtrees. So, if we evaluate a Map k a value to weak head normal form, we actually fully evaluate the tree spine.