[Haskell-beginners] Data.Map: fromList

[Brandon Allbery]

On Tue, Sep 11, 2012 at 12:59 PM, Stayvoid <stayvoid at gmail.com> wrote:

> ghci> Map.fromList
> [("betty","555-2938"),("bonnie","452-2928"),("lucille","205-2928")]
> fromList
> [("betty","555-2938"),("bonnie","452-2928"),("lucille","205-2928")]
>
> Why does Map.fromList represent its output like this?
>

It doesn't; the Show instance for Data.Map, however, does a toAscList and
then wraps the resulting list in a fromList, because the internals of a Map
are deliberately hidden.

If the internals of Map were visible, it would be possible to build an
invalid Map; at best it would be unbalanced and slow, at worst it would be
misordered and keys would randomly go "missing" as a result.  See, for
example, how (Map Double a) misbehaves (try searching the haskell-cafe list
for "Map Double"):  the poorly defined Ord constraint on floating point
types, especially in the presence of NaN, means keys *do* sometimes go
missing in this case and (Map Double a) ends up being rather unreliable.

This also means you can break a Map by providing an incorrect or
inconsistent Ord instance for its key.  This is why typeclass instances are
global; if there were local instances, you could do severe violence to a
Map by providing an incompatible/incoherent local Ord instance for the type
of its key.

data Map.Map k a
>   = Data.Map.Tip
>   | Data.Map.Bin !Data.Map.Size !k a !(Map.Map k a) !(Map.Map k a)
>

A node in a Map is either a Tip (placeholder of sorts) or a Bin comprising
a strict number of subnodes/values, a strict key and its associated value,
and strict left and right subtrees (which may be Tip-s if this is a leaf).
 You should never try to work with this directly (and under normal
circumstances you can't, as the constructors are hidden), as outlined above.

-- 
brandon s allbery                                      allbery.b at gmail.com
wandering unix systems administrator (available)     (412) 475-9364 vm/sms
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20120911/996f62e8/attachment-0001.htm>