自定义函子实例：期望一种 '* - > *'，而是 'AST' 有种 '*'

Question

我有这个简单的ADT：

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

和函子实例：

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

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

data AST a = ... 
--  ^type parameter

我们也可以看到这样的Functor类的定义：

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

请注意，f在班级的头部有“种” * -> *这意味着它作为某种功能需要另一种类型（第一个*）并生成一个类型（第二个*）。正如你可以看到fmap将采用类型a -> b（我们没有太多的控制什么b是）的功能。在您定义的fmap中，我们只能提供String -> String函数。

现在把AST作为一个仿函数没什么意义，因为它不是函子。

但是，您可以轻松地概括您AST到：

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

如果你有这种类型的工作，一个AST String相当于旧定义为AST。

这同样适用于列表[]（也是Functor）。列表的伪 -definition是：

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

我们定义Functor一个列表如下：我们做不状态Functor [a]，但Functor []

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

心灵。

Answer 2

函子必须是多态的，即data AST a = ...。在这种情况下，这就是“善良”的意思。它想要AST不是一个类型，而是一个类型函数，取一个类型并返回一个类型。