[Haskell-cafe] Why does Data.Map exist when...

Dan Weston westondan at imageworks.com
Tue Jul 17 00:37:30 EDT 2007

Your Map' (==) is lying! :)

Your definition purports to establish an equivalence class for all MP 
(key,value) with the same key, but MP(key,1) and MP(key,2) are not 
"equivalent" in any meaningful way outside the internals of Map' (else 
you could dispense with the payload entirely!)

Set is now not a representation of Map', but a co-representation. 
Details are exposed to outsiders to hide them from Map'. Everyone else 
pays so that Map' 's life is a little easier.

Contrast that with, say, a set represented by a list, with compare 
defined to sort before comparing. This is a meaningful (to outsiders) 
equivalence relation because it hides the internal representation 
artifact that lists have a (spurious) ordering.

IMHO the interface should represent the external properties, not some 
internal invariant. In short, Map' doesn't say what it mean and mean 
what it says. If you told me for a, b :: MyPair k v that a == b, I would 
(foolishly) expect that a = b. I suspect that I wouldn't be the only one 
to make that mistake.

Dan Weston

Tony Morris wrote:
> Hash: SHA1
> ...it seems to be a special case of Set? Does Data.Map add anything more
> useful than Map' below?
> import Data.Set as Set
> newtype MyPair a b = MP (a, b)
>   deriving Show
> instance (Eq a) => Eq (MyPair a b) where
>   MP (a, _) == MP (a', _) = a == a'
> instance (Ord a) => Ord (MyPair a b) where
>   MP (a, _) `compare` MP(a', _) = a `compare` a'
> type Map' k a = Set (MyPair k a)
> - --
> Tony Morris
> http://tmorris.net/
> Version: GnuPG v1.4.6 (GNU/Linux)
> Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
> iD8DBQFGnDgEmnpgrYe6r60RAu4FAJ93Fwcx7ZX08+qO4ZlzRVV52TXpNQCeNr7u
> ioq0XrWt/Wymfh52W1spiFk=
> =FC5h
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe

More information about the Haskell-Cafe mailing list