Haskell: các lớp học kiểu chất vấn

Question

Tôi muốn xác định typeclass sau 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 

Một thể hiện của Mapping là 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 

Và bây giờ tôi muốn tạo ra một loại Trie :: * -> * -> * -> * như

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

Cho đến nay rất tốt, bây giờ tôi cũng muốn xác định 's insert và empty, và đó là nơi tôi gặp vấn đề.

tôi sẽ thảo luận empty vì nó đơn giản và insert cần nó dù sao đi nữa .. Nếu tôi cố gắng này:

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

và làm cho tôi nhận được lỗi sau:

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} 

Tôi đã đã cố gắng và cố gắng giải quyết nó nhưng thất bại.

Có ai biết cách làm cho nó hoạt động không? Thậm chí có thể không?

Answer 1

Thêm một functional dependency:

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

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

Các lỗi bạn đã nhận trước là vì chương trình đã mơ hồ về những loại chìa khóa để sử dụng ở những nơi nhất định, do đó các lỗi về loại biến k1. Sự phụ thuộc chức năng cho phép loại khóa được suy ra từ loại bản đồ (bằng cách tuyên bố rằng chỉ có một câu trả lời có thể), mà đề cập đến vấn đề này.

Answer 2

Mã để chứng minh Ganesh của câu trả lời:

{-# 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: Có phải phụ thuộc hàm không tồn tại, chúng ta có lẽ sẽ cần phải thỏa hiệp về một giao diện gây phiền nhiễu và sử dụng bảng chức năng thay vì các lớp học kiểu.