自定义 Functor 实例：预期类型为“* -> ”，但“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’

有谁知道为什么会这样？我在网上找不到解决方法。

Answer 1

仿函数必须是多态的，即data AST a = ...。这就是 "kind" 在这种情况下的意思。它希望 AST 不是一个类型，而是一个类型函数，接受一个类型并返回一个类型。

Answer 2

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

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

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

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

注意 class 头部的 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 []。

自定义 Functor 实例：预期类型为“* -> ”，但“AST”具有类型“”

Custom Functor instance: Expected kind ‘* -> ’, but ‘AST’ has kind ‘’

haskell

abstract-data-type

functor

自定义 Functor 实例：预期类型为“* -> *”，但“AST”具有类型“*”

Custom Functor instance: Expected kind ‘* -> *’, but ‘AST’ has kind ‘*’

haskell

abstract-data-type

functor

自定义 Functor 实例：预期类型为“* -> ”，但“AST”具有类型“”

Custom Functor instance: Expected kind ‘* -> ’, but ‘AST’ has kind ‘’