ハスケル：型クラスは

Question

は、私は、次の型クラス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 

一つMappingのインスタンスが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 

ですそして今、私は種類を作成したいのTrie :: * -> * -> * -> *など

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

これまでのところ、 今私はTrieのinsertとemptyを定義したいと思っています。それが問題になります。

それは簡単ですし、私はこれしようとinsertが...とにかく を、それを必要とするので、私はemptyについて説明します：

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

をしているが、私は次のエラーを取得する可能：

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} 

私はしました試して解決しようとしましたが失敗しました。

どのように動作させるか知っていますか？それも可能ですか？あなたが前に持ってプログラムが​​変数の型については、特定の場所で、したがって、エラーを使用するためにどのキータイプについて曖昧だったためだった

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

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

エラー：

Answer 1

はfunctional dependencyを追加します。関数の依存関係により、この問題を扱うキータイプを（可能な答えが1つだけであることを宣言することによって）マップタイプから導き出すことができます。

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

がところで：

Answer 2

コードガネーシュの答えを証明するために関数従属性が存在していなかったならば、我々はおそらく迷惑なインターフェースで妥協し、関数テーブルの代わりの型クラスを使用する必要があります。