[Haskell-beginners] Data.Map: fromList
allbery.b at gmail.com
Tue Sep 11 19:48:51 CEST 2012
On Tue, Sep 11, 2012 at 12:59 PM, Stayvoid <stayvoid at gmail.com> wrote:
> ghci> Map.fromList
> 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...
More information about the Beginners