自定义List类型实现Applicative函子时遭遇无限类型错误

一、修复“无法构造无限类型”错误 #

你的错误根源在于对<*>的类型逻辑理解有误：

• <*>的类型是List (a -> b) -> List a -> List b，最终要返回单个元素为b的List
• 你原代码里的Cons (fmap a (Cons c (d))) ...，fmap a xs的结果是List b，但Cons的第一个参数需要的是单个b类型的值，这就导致编译器试图推断b ~ List b，从而触发无限类型错误。

要实现原生列表的<*>行为（所有函数与所有元素的笛卡尔积应用），你需要先实现一个列表拼接函数，把每个函数作用于列表得到的结果依次拼接起来：

1. 先定义append辅助函数：

append :: List a -> List a -> List a
append Nil ys = ys
append (Cons x xs) ys = Cons x (append xs ys)

2. 修正Applicative实例：

instance Applicative List where
    pure a = Cons a Nil
    -- <*> :: List (a -> b) -> List a -> List b
    Nil <*> _ = Nil
    _ <*> Nil = Nil
    Cons f fs <*> xs = append (fmap f xs) (fs <*> xs)

这样修改后，fmap f xs会把函数f作用到xs的每个元素得到List b，再通过append和后续函数列表fs作用于xs的结果拼接，最终返回符合类型要求的List b。

二、用类似concatMap的方式实现<*> #

完全可以模仿原生列表的concatMap风格实现，这和用append的方式本质等价，只是写法不同：

1. 先实现自定义List的concat和concatMap：

concat :: List (List a) -> List a
concat Nil = Nil
concat (Cons xs xss) = append xs (concat xss)

concatMap :: (a -> List b) -> List a -> List b
concatMap f = concat . fmap f

2. 用concatMap实现<*>：

instance Applicative List where
    pure a = Cons a Nil
    fs <*> xs = concatMap (\f -> concatMap (\x -> Cons (f x) Nil) xs) fs

等价性说明 #

• 内层concatMap (\x -> Cons (f x) Nil) xs的作用就是fmap f xs：把每个x转换成单元素列表，再concat起来就是f作用于所有x的结果
• 外层concatMap则是把每个函数对应的结果列表拼接在一起，和之前用append递归拼接的逻辑完全一致。

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