递归数据构造器的Functor实例实现报错：无法构造无限类型

你的代码存在两个核心问题，直接导致了“无法构造无限类型”的错误：

1. 数据类型定义的类型参数缺失 #

你写的data List a = Hol x a| Hoofd x [List a]中，x是未声明的类型变量——Haskell要求数据类型的所有类型参数必须在=左侧的括号里明确声明。如果x是你想添加的标签（比如字符串、整数标记），需要把它作为额外的类型参数加到List后面，正确的定义应为：

data List x a = Hol x a | Hoofd x [List x a]
            deriving (Show,Eq,Ord)

此时x和a都是List的类型参数：Hol构造函数携带一个x类型的标签和一个a类型的元素，Hoofd携带标签和一个List x a的列表。

2. fmap递归调用的类型不匹配 #

处理Hoofd x rest时，rest的类型是[List x a]（List x a的列表），而fmap f是作用于单个List x a的函数。要把fmap f应用到列表的每个元素上，需要用**列表的fmap**包裹这个函数，也就是fmap (fmap f) rest。你之前直接写fmap f rest，Haskell会错误推断f的类型为List x a -> b，但Functor要求f是a -> b，这就导致类型不匹配，进而触发无限类型错误。

修复后的完整代码 #

data List x a = Hol x a | Hoofd x [List x a]
            deriving (Show,Eq,Ord)

instance Functor (List x) where
            fmap f (Hol x a) = Hol x (f a)
            fmap f (Hoofd x rest) = Hoofd x (fmap (fmap f) rest)

注意这里的instance Functor (List x)：因为Functor只需要一个类型参数，x是固定的，所以我们把List x作为Functor的实例，而非List本身。

内容的提问来源于stack exchange，提问作者Justin Young