[Haskell-cafe] Re: working Edison, a couple of collection modules, and typing troubles

[oleg at pobox.com]

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.