Haskell: question sur les classes de types
Question
Je souhaite définir la classe de type suivante Mapping
:
{-# LANGUAGE MultiParamTypeClasses #-}
class Mapping k v m where
empty :: m v
insert :: k -> v -> m v -> m v
search :: k -> m v -> Maybe v
delete :: k -> m v -> m v
Une instance de Mapping
est Data.Map.Map
{-# LANGUAGE ..., FlexibleInstances #-}
instance Ord k => Mapping k v (Map.Map k) where
empty = Map.empty
search = Map.lookup
insert = Map.insert
delete = Map.delete
Et maintenant je veux créer un type Trie :: * - > * - > * - > *
tel que
{-# LANGUAGE ..., UndecidableInstances #-}
data Trie m k v = Trie {
trValue :: Maybe v,
trChildren :: m (Trie m k v)
}
instance Mapping k (Trie m k v) m => Mapping [k] v (Trie m k) where
search [] tree = trValue tree
search (x:xs) tree =
search xs =<< search x (trChildren tree)
Jusqu'ici tout va bien,
Maintenant, je veux aussi définir les balises insert
et vides
de Trie
, et c’est là que j’ai des problèmes.
Je discuterai de empty
car c'est plus simple et insert
en a besoin de toute façon.
Si j'essaye ceci:
instance Mapping k (Trie m k v) m => Mapping [k] v (Trie m k) where
empty = Trie { trValue = Nothing, trChildren = empty }
...
et cela me donne l'erreur suivante:
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}
J'ai essayé et essayé de le résoudre mais j'ai échoué.
Quelqu'un sait-il comment le faire fonctionner? Est-ce même possible?
La solution
Ajouter une dépendance fonctionnelle :
{-# LANGUAGE ..., FunctionalDependencies #-}
class Mapping k v m | m -> k where
...
Les erreurs que vous avez eues avant étaient dues au fait que le programme était ambigu quant au type de clé à utiliser à certains endroits, d’où les erreurs concernant la variable de type k1
. La dépendance fonctionnelle permet de déduire le type de clé du type de carte (en déclarant qu’il n’ya qu’une réponse possible), ce qui résout ce problème.
Autres conseils
Code montrant la réponse de Ganesh:
{-# LANGUAGE FlexibleInstances, FunctionalDependencies, MultiParamTypeClasses, StandaloneDeriving, UndecidableInstances #-}
import qualified Data.Map as Map
import Data.Maybe (fromMaybe)
class Mapping k m | m -> k where
empty :: m v
insert :: k -> v -> m v -> m v
search :: k -> m v -> Maybe v
delete :: k -> m v -> m v
instance Ord k => Mapping k (Map.Map k) where
empty = Map.empty
search = Map.lookup
insert = Map.insert
delete = Map.delete
data Trie m v = Trie {
trValue :: Maybe v,
trChildren :: m (Trie m v)
}
deriving instance (Show v, Show (m (Trie m v))) => Show (Trie m v)
trieMod :: Mapping k m => Maybe v -> [k] -> Trie m v -> Trie m v
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 k m => 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: Si les dépendances fonctionnelles n'existaient pas, nous devrions probablement faire un compromis sur une interface gênante et utiliser des tables de fonctions au lieu de classes de types.