Haskell: class type question

Question

I want to define the following Mapping class:

 {-# LANGUAGE MultiParamTypeClasses #-} class Mapping kvm where empty :: mv insert :: k -> v -> mv -> mv search :: k -> mv -> Maybe v delete :: k -> mv -> mv 

One Mapping Instance - Data.Map.Map

 {-# LANGUAGE ..., FlexibleInstances #-} instance Ord k => Mapping kv (Map.Map k) where empty = Map.empty search = Map.lookup insert = Map.insert delete = Map.delete 

And now I want to create the type Trie :: * -> * -> * -> * , for example

 {-# LANGUAGE ..., UndecidableInstances #-} data Trie mkv = Trie { trValue :: Maybe v, trChildren :: m (Trie mkv) } instance Mapping k (Trie mkv) m => Mapping [k] v (Trie mk) where search [] tree = trValue tree search (x:xs) tree = search xs =<< search x (trChildren tree) 

So far so good, now I also want to define Trie insert and empty and that I get into problems.

I will discuss empty because it is simpler and insert needs it anyway .. If I try this:

 instance Mapping k (Trie mkv) m => Mapping [k] v (Trie mk) where empty = Trie { trValue = Nothing, trChildren = empty } ... 

and this makes me get the following error:

 Could not deduce (Mapping k (Trie m k1 v) (m k1)) from the context (Mapping [k1] v (Trie m k1), Mapping k1 (Trie m k1 v) (m k1)) arising from a use of `empty' at test.hs:27:49-53 Possible fix: add (Mapping k (Trie m k1 v) (m k1)) to the context of the instance declaration or add an instance declaration for (Mapping k (Trie m k1 v) (m k1)) In the `trChildren' field of a record In the expression: Trie {trValue = Nothing, trChildren = empty} In the definition of `empty': empty = Trie {trValue = Nothing, trChildren = empty} 

I tried and tried to solve it, but could not.

Does anyone know how to make it work? Is it possible?

Answer 1

Add a functional dependency :

 {-# LANGUAGE ..., FunctionalDependencies #-} class Mapping kvm | m -> k where ... 

The errors that you received before that were due to the fact that the program was ambiguous as to what type of key to use in certain places, therefore, errors in a variable of type k1 . The functional dependency allows you to infer the key type from the card type (declaring that there is only one possible answer) that concerns this problem.

Answer 2

Code to demonstrate the Ganesh answer:

 {-# LANGUAGE FlexibleInstances, FunctionalDependencies, MultiParamTypeClasses, StandaloneDeriving, UndecidableInstances #-} import qualified Data.Map as Map import Data.Maybe (fromMaybe) class Mapping km | m -> k where empty :: mv insert :: k -> v -> mv -> mv search :: k -> mv -> Maybe v delete :: k -> mv -> mv instance Ord k => Mapping k (Map.Map k) where empty = Map.empty search = Map.lookup insert = Map.insert delete = Map.delete data Trie mv = Trie { trValue :: Maybe v, trChildren :: m (Trie mv) } deriving instance (Show v, Show (m (Trie mv))) => Show (Trie mv) trieMod :: Mapping km => Maybe v -> [k] -> Trie mv -> Trie mv trieMod val [] trie = trie { trValue = val } trieMod val (x:xs) trie = trie { trChildren = insert x newChild children } where children = trChildren trie newChild = trieMod val xs prevChild prevChild = fromMaybe empty . search x $ children instance Mapping km => Mapping [k] (Trie m) where empty = Trie { trValue = Nothing, trChildren = empty } search [] trie = trValue trie search (x:xs) trie = search xs =<< search x (trChildren trie) insert key val = trieMod (Just val) key delete = trieMod Nothing type TernarySearchTree a = Trie (Map.Map a) 

Btw: If functional dependencies did not exist, we probably would have to compromise on the annoying interface and use function tables instead of class classes.