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

2
votes

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.

2
haskellconcurrencylazy-evaluationweak-head-normal-form

2 Answers

4
votes

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.

1
votes

Map in Map.insert is not map constructor. It is a module name. The function insert :: Ord k => k -> a -> Map k a -> Map k a is called here. Its result will get evaluated to WHNF before return () is calculated as the next computational step in the combined IO action, thanks to the call to seq. You can consult the source of insert for details. It does a lot of forcing through bang patterns and such.