[Haskell-cafe] GADTs, type classes, existentials

[Mike Hamburg]

Hello all,

I'm trying to build a variation on Maps which supports a fast
"concat-like" operation, for a library I'm writing.  I'd rather not
re-implement Data.Map, so I'm having a try with GADTs.

The relevant part of my source file:

-------------------------------------------------------------------------
data MetaMap k v where
    Map  :: Ord k => Map.Map k v -> MetaMap k v
    Cat  :: MetaMap k1 (MetaMap k2  v) -> MetaMap (k1,k2) v
    {- other, similar constructors -}

lookup :: Monad m => k -> MetaMap k v -> m v
lookup k (Map  m) = Map.lookup k m
lookup k (Cat  m) = case k of (k1,k2) -> lookup k1 m >>= lookup k2
-------------------------------------------------------------------------

Unfortunately, this doesn't work:

Data/MetaMap.hs:45:20:
    Could not deduce (Ord k) from the context (Monad m)
      arising from use of `Map.lookup' at Data/MetaMap.hs:45:20-33
    Possible fix: add (Ord k) to the type signature(s) for `lookup'
    In the expression: Map.lookup k m
    In the definition of `lookup': lookup k (Map m) = Map.lookup k m

This error happens because the Ord constraint isn't propagated into the
function body.  Of course, I can't add Ord k to the type signature for
lookup, because one can't deduce Ord k from Ord (k1,k2).

Is there a clean way around this error?

Thanks for your time,
Mike Hamburg