Samuel Bronson wrote:
I was trying my hand at writing some collection classes myself and I can't figure out a good typing for map that will let me make Map an instance of my Collection class... I don't much like the head of Mapping.
How about the following:
class Collection (d k e) (k, e) => Mapping d k e where -- * Query lookup :: (Monad m) => k -> d k e -> m e
instance Ord k => Collection (M.Map k e) (k, e) where null = M.null empty = M.empty <elided>
instance Ord k => Mapping M.Map k e where lookup = M.lookup
A higher-ranked type constructor gets rid of functional dependencies. The drawback of course is trying to use something like Integer as a mapping from Int to Bool. We have to declare a wrapper
-- Integer as a collection of bits newtype BitMap k e = BitMap Integer deriving Show
instance Collection (BitMap Int Bool) (Int, Bool) where empty = BitMap 0 fromList [] = empty fromList ((b,v):r) = let BitMap br = (fromList r):: BitMap Int Bool in BitMap ((if v then setBit else clearBit) br b)
instance Mapping BitMap Int Bool where lookup k (BitMap bm) = return $ testBit bm k
This actually works (and efficiently: BitMap is a newtype, so no tagging is involved at run-time), but leaves the sense of dissatisfaction. The type BitMap k e appears polymorphic, yet the only permissible values for `k' is Int, and for `e' is Bool. Alas, this facts isn't expressed anywhere. We can add explicit constraints, or better, use GADT:
data BitMap k e where BitMap :: Integer -> BitMap Int Bool
the rest of the code is unchanged.