Haskell:类型类问题

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 ，这就是我遇到问题的地方。

我将讨论 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}

我已经尝试并尝试解决它但失败了。

有谁知道如何使它工作？甚至可能吗？

Answer 1

添加 functional dependency :

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

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

您之前遇到的错误是因为程序在某些地方使用哪种键类型不明确，因此有关类型变量的错误 k1 .函数依赖允许从映射类型推断出键类型(通过声明只有一个可能的答案)，从而解决了这个问题。