[Haskell-cafe] Data.Map and strictness (was: Is Haskell aGoodChoice for WebApplications?(ANN: Vocabulink))

Claus Reinke claus.reinke at talk21.com
Thu May 7 08:30:34 EDT 2009

> seq something like size map that will force a traversal of the entire
> tree, and ensure that the result is actually demanded, ..
> (Not tested)

and not recommended, either, I'm afraid!-)

|> Actually, I'm unsure how to fix this. For an expression like this:
|>    Data.Map.delete key map
|> how can I use seq (or something else) to sufficiently evaluate the above
|> to ensure that the value associated with key can be garbage collected?

You can ensure that the Map update no longer holds on to the old key
by keeping a copy of the old Map in an unevaluated thunk, but for
garbage collection, you'd also have to make sure that there are no other
unused references to the old Map, and no other references to the value
in that old key. I assume you knew that, but the discussion suggested 
that we should keep making such things explicit.

|> My knowledge of Data.Map is limited to it's haddock documentation.

That won't be sufficient in practice, eg., most of the documentation is 
silent about strictness properties. If you are willing to look a little bit
under the hood, GHCi's :info is your friend:

    Prelude> :m +Data.Map
    Prelude Data.Map> :info Map
    data Map k a
      = Data.Map.Tip
      | Data.Map.Bin !Data.Map.Size !k a !(Map k a) !(Map k a)
            -- Defined in Data.Map

You can see that the constructors are not exported (GHCi reports
them qualified, even though we've brought Data.Map into scope),
so any use you make of their strictness properties is version dependent.
They are not likely to change soon, and should probably be documented
in the haddock API specification (at least for the abstract constructors
that are actually exported), so that we can rely on them with clear
conscience, but that isn't quite the case at the moment.

Anyway;-) You can see that size is actually pre-computed, so there's
no guarantee that asking for it will traverse the internal representation,
the element type is not stored strictly (which isn't all that unexpected, 
but sometimes surprises because it isn't documented), and everything
else is strict. So, with the current representation, if you force the Map,
its whole structure will be forced, though none of its elements will be.


PS. GHood is useful for observing dynamic strictness properties
        (what is inspected when, with what dependencies and results),
        though it won't help you directly with garbage collection issues
        (it can't observe when a value gets collected).

More information about the Haskell-Cafe mailing list