Haskell: Typklassen Frage

Question

Ich mag folgenden typeclass Mapping definieren:

{-# 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

Eine Instanz von Mapping ist 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

Und nun möchte ich eine Art Trie :: * -> * -> * -> * wie

erstellen

{-# 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)

So weit, so gut, jetzt will ich auch Trie die insert und empty definieren, und das ist, wo ich Probleme bekommen.

werde ich empty diskutieren, weil es einfacher ist und insert braucht es sowieso .. Wenn ich versuche, dies:

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

und das macht mir die folgende Fehlermeldung erhalten:

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}

Ich habe versucht und versucht, es zu lösen, aber fehlgeschlagen.

Wer weiß, wie es funktioniert? Ist es überhaupt möglich?

Answer 1

Fügen Sie eine funktionale Abhängigkeit :

{-# LANGUAGE ..., FunctionalDependencies #-}

class Mapping k v m | m -> k where
   ...

Die Fehler, die Sie haben, waren vor, da das Programm nicht eindeutig über war, welcher Schlüsseltyp an bestimmten Orten zu verwenden, damit die Fehler über die Art Variable k1. Die funktionale Abhängigkeit ermöglicht es dem Schlüsseltyp vom Kartentyp abgeleitet werden (indem er erklärt, dass es nur eine mögliche Antwort ist), die sich mit diesem Problem beschäftigt.

Answer 2

Code-Ganeshs Antwort zu demonstrieren:

{-# 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: Hatte funktionale Abhängigkeiten nicht existiert, würden wir wahrscheinlich brauchen auf eine lästige Schnittstelle und Verwendung Funktionstabellen statt Typklassen Kompromissen

.