हास्केल: प्रकार कक्षाएं सवाल

Question

मैं निम्नलिखित typeclass 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 को परिभाषित करना चाहता हूं, और यही वह जगह है जहां मुझे समस्याएं आती हैं।

मैं empty पर चर्चा करेंगे क्योंकि यह आसान है और किसी भी तरह insert इसकी आवश्यकता है .. यदि मैं यह कोशिश:

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 
    ... 

त्रुटियों तुम से पहले मिल गया थे क्योंकि प्रोग्राम है जो कुंजी प्रकार, इसलिए त्रुटियों प्रकार चर k1 के बारे में कुछ स्थानों पर उपयोग करने के लिए के बारे में अस्पष्ट था:

Answer 1

एक functional dependency जोड़ें। कार्यात्मक निर्भरता कुंजी प्रकार को नक्शा प्रकार से निकाला जा सकता है (यह घोषणा करके कि केवल एक ही संभावित उत्तर है), जो इस समस्या से संबंधित है।

Answer 2

कोड गणेश का जवाब प्रदर्शित करने के लिए:

{-# 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: कार्यात्मक निर्भरता से ही अस्तित्व में नहीं होते, तो हमें शायद एक कष्टप्रद इंटरफेस पर समझौता और कार्य तालिकाओं के बजाय प्रकार वर्गों का उपयोग करने की आवश्यकता होगी।