ghc -XMultiParamTypeClasses -XFunctionalDependencies -XUndecidableInstances ~/test.hsghc -XMultiParamTypeClasses -XFunctionalDependencies -XUndecidableInstances ~/test.hs

test.hs

main :: IO Int
main = main

class Key k m | k -> m where
      empty :: m v
      lookup' :: k -> m v -> Maybe v

data MB t = MB (Maybe t) (Maybe t)

instance Key Bool MB where
         empty = MB Nothing Nothing
         lookup' True (MB _ mt) = mt
         lookup' False (MB mf _) = mf

data MP x y v = MP (x (y v))

instance (Key a ma, Key b mb) => Key (a, b) (MP ma mb) where
         empty = MP (empty :: ma (mb v))
         lookup' (ka, kb) (MP m) = case lookup' ka m of
                                       Nothing -> Nothing
                                       Just m2 -> lookup' kb m2

{-                                                                                                                                          
instance (Key a, Key b) => Key (a, b) where                                                                                                 
         data Map (a, b) v = MP (Map a (Map b v))                                                                                           
         empty = MP empty                                                                                                                   
         lookup' (ka, kb) (MP m) = case lookup' ka m of                                                                                     
                                       Nothing -> Nothing                                                                                   
                                       Just m2 -> lookup' kb m2                                                                             
-}
{-                                                                                                                                          
instance Key Bool where                                                                                                                     
         data Map Bool v = MB (Maybe v) (Maybe v)                                                                                           
         empty = MB Nothing Nothing                                                                                                         
         lookup' True (MB _ mt) = mt                                                                                                        
         lookup' False (MB mf _) = mf                                                                                                       
-}