haskell - 自定义 Functor 实例 : Expected kind ‘* -> *’ , 但 ‘AST’ 有种类 ‘*’

Question

我有这个相当简单的 ADT:

data AST = Node String [AST]
     | Leaf String
     | Empty
    deriving (Show)

还有这个 Functor 实例:

instance Functor AST where
    fmap f (Node s l) = Node (f s) (fmap f l)
    fmap f (Leaf s)   = Leaf (f s)
    fmap f Empty      = Empty

但是当我尝试编译它时，我得到了这个我完全不明白的错误:

Expected kind ‘* -> *’, but ‘AST’ has kind ‘*’
   • In the first argument of ‘Functor’, namely ‘AST’
     In the instance declaration for ‘Functor AST’

有人知道为什么会这样吗？我在 Internet 上找不到解决方案。

Answer 1

仿函数作用于类型构造函数:如果你给它一个AST，它期望看到:

data AST <b>a</b> = ...
--       ^ type parameter

我们也可以在Functor类的定义中看到这一点:

class Functor (f :: <b>* -> *</b>) where
  fmap :: (a -> b) -> f <b>a</b> -> f <b>b</b>

注意类头中的 f 有“kind” * -> * 这意味着充当某种函数接受另一种类型(第一个 *)并产生一个类型(第二个 *)。如您所见， fmap 将采用类型为 a -> b 的函数(我们无法控制 b 是什么)。在你对fmap的定义中，我们只能提供一个String -> String函数。

现在将 AST 设为仿函数没有多大意义，因为它不是仿函数。

但是，您可以轻松地将您的AST概括为:

data AST <b>a</b> = Node <b>a</b> [AST <b>a</b>]
     | Leaf <b>a</b>
     | Empty
    deriving (Show)

如果您使用该类型，则 AST String 等同于您对 AST 的旧定义。

列表 [] 也是如此(它也是一个 Functor)。列表的伪定义是:

data [] a = [] | a : [a]

我们在列表上定义 Functor 为:

instance Functor [] where
    fmap _ [] = []
    fmap f (x:xs) = (f x) : (fmap f xs)

请注意，我们不是声明Functor [a]，而是Functor []。