-----BEGIN PGP SIGNED MESSAGE----- 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/ -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.6 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iD8DBQFGnDgEmnpgrYe6r60RAu4FAJ93Fwcx7ZX08+qO4ZlzRVV52TXpNQCeNr7u ioq0XrWt/Wymfh52W1spiFk= =FC5h -----END PGP SIGNATURE-----
On Monday 16 July 2007, Tony Morris wrote:
...it seems to be a special case of Set? Does Data.Map add anything more useful than Map' below?
Why does Data.Set exist when it's just a special case of Data.Map? import Data.Map type Set a = Map a () And, in fact, I think going this way doesn't lose any functionality, whereas implementing Map in terms of Set loses you stuff like unionWith (at least, barring your taking time to re-implement it specifically), which may or may not be a big deal to you (I think I've used it before, though). The answer is, I suppose, that the interface is subtly different (and the semantics may be, too; are you sure that your insert using Set behaves the same way as insert on Map?), and when you're doing Set stuff, you don't want to be bugged by the fact that you're using a Map of ()s, and vice versa (although you could probably finesse things to the point where it wouldn't be noticeable). The real question is why there's Data.Map and Data.IntMap, when the compiler should really be able to detect that we're using a certain key type, and automatically use the optimized Map for that key type without our having to do anything. And the answer to that is that maybe, in the future, that will be the case, once associated types/data families are widely available. :) Cheers, Dan Doel
Tony Morris:
...it seems to be a special case of Set? Does Data.Map add anything more useful than Map' below?
[... Map-like structure based on Data.Set ...]
Note that you could also attempt to go in the other direction (but see the comments about strictness below):
type Set' a = Data.Map.Map a ()
Certainly, Data.Map and Data.Set are very similar in their implementations, but rather than seeing one as a specialisation of the other, it's more helpful to see them both as specialisations of a basic underlying binary tree structure. The specialisation occurs both in the interfaces (for the convenience of the user), and in the implementations (for efficiency). For example, at the interface, consider how you would perform the equivalent of Data.Map.lookup using your Map' type. You'll need a clever combination of intersection, singleton and toList, with appropriate lifting into an arbitrary monad. If you look at the implementations, you'll note that, among other things, the Data.Map.Map type is strict in the key, but not in the associated value. Data.Set is not strict in the value, so your Map' type will not be strict in its key. As well as improving the performance of Data.Map, strictness in the key also helps avoid problems with memory leaks.
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:
-----BEGIN PGP SIGNED MESSAGE----- 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/
-----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.6 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
iD8DBQFGnDgEmnpgrYe6r60RAu4FAJ93Fwcx7ZX08+qO4ZlzRVV52TXpNQCeNr7u ioq0XrWt/Wymfh52W1spiFk= =FC5h -----END PGP SIGNATURE----- _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
participants (5)
-
Albert Y. C. Lai -
Dan Doel -
Dan Weston -
Matthew Brecknell -
Tony Morris