具有多个参数的Haskell和类型类

Question

在编写从彼此继承的类型类时,我遇到了一个简单的问题.我正在尝试创建一个类型类的层次结构,以实现某种程度的表示抽象.假设我想要一个集合类型类:

{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE FlexibleInstances #-}

class Collection c a where
  isMember :: a -> c -> Bool

我已经定义了一个树类型:

data Tree a = Empty | Node a (Tree a) (Tree a)
  deriving (Show, Eq)

我想让我的树成为一个集合,所以:

inOrder :: Tree a -> [a]
inOrder Empty = []
inOrder (Node a l r) = (inOrder l) ++ [a] ++ (inOrder r)

instance (Eq a) => Collection (Tree a) a where
  isMember a c = a `elem` (inOrder c)

这不太正常:

*Main> (isMember '2' Empty)
<interactive>:1:1:
    No instance for (Collection (Tree a) Char)
      arising from a use of `isMember' at <interactive>:1:1-18
    Possible fix:
      add an instance declaration for (Collection (Tree a) Char)
    In the expression: (isMember '2' Empty)
    In the definition of `it': it = (isMember '2' Empty)

假设我必须为每种具体类型创建一个实现,那么大概会丢失类型类的值.所以我没有正确编写实例声明.但我无法弄清楚如何继续.

Answer 1

这里的问题是,默认情况下,每个类型类参数都独立于其他类参数.简单地应用于isMembera Char和未知元素类型的树是不足以让它推断它应该使用(看似明显的)实例.

这显然不是你想要它的工作方式,而且引导有点傻,但这就是它的工作原理.要解决这个问题,你需要给它一些建立连接的方法,其中有其他扩展:FunctionalDependencies更常见,虽然TypeFamilies更新,更好用,但仍然有一些粗糙的边缘.

使用函数依赖项,您可以指定类型类参数的某个子集完全确定其他子集,例如Collection c a | c -> a.这有其自身的缺陷,但在许多情况下运作良好.

对于类型族,您可能会将其减少为单参数类型类,并且元素类型相关联,例如:

class Collection c where
    type Elem c
    isMember :: Elem c -> c -> Bool

Answer 2

您需要添加函数依赖项以指示容器类型确定元素类型:

{-# LANGUAGE FunctionalDependencies #-}

class Collection c a | c -> a where
    ...

还有其他方法可以做到这一点,比如使用类型系列,但我认为这是最简单的修复方法.