编写Haskell链表LL类型Monad时>>=函数报错，求原因

错误原因分析 #

你的>>=实现第9行Node a ll_a >>= f = Node (f a) (ll_a >>= f)存在类型不匹配问题：

• Node构造器的类型是Node :: b -> LL b -> LL b，第一个参数需要是单个b类型值
• 但f a的类型是LL b（因为f的类型是a -> LL b），这就导致编译器报错Couldn't match expected type ‘b’ with actual type ‘LL b’

而第8行Node a Sentinel >>= f = f a能通过类型检查，是因为：

• >>=的返回类型要求是LL b，而f a正好是LL b类型，完全符合签名要求。不过这个分支其实是多余的，因为当ll_a为Sentinel时，通用分支的逻辑会自动等价于这个结果。

正确实现方案 #

要实现链表的Monad实例，>>=的行为应该是对链表每个元素应用f，然后把所有生成的子链表拼接起来（类似concatMap的逻辑）。我们需要先实现一个链表拼接函数append，再修正>>=：

完整代码 #

data LL a = Sentinel | Node a (LL a) deriving (Show)

-- 先实现Functor和Applicative（Monad的前置要求）
instance Functor LL where
    fmap _ Sentinel = Sentinel
    fmap f (Node x xs) = Node (f x) (fmap f xs)

instance Applicative LL where
    pure x = Node x Sentinel
    Sentinel <*> _ = Sentinel
    (Node f fs) <*> xs = append (fmap f xs) (fs <*> xs)

instance Monad LL where
    return = pure
    (>>=) :: LL a -> (a -> LL b) -> LL b
    Sentinel >>= _ = Sentinel
    Node a ll_a >>= f = append (f a) (ll_a >>= f)
    (>>) :: LL a -> LL b -> LL b
    x >> y = x >>= \_ -> y

-- 链表拼接辅助函数
append :: LL a -> LL a -> LL a
append Sentinel ys = ys
append (Node x xs) ys = Node x (append xs ys)

关键修正点 #

1. 用append函数将f a生成的子链表与后续元素绑定后的结果拼接，而不是把f a当作单个节点元素
2. 补充了Functor和Applicative实例，这是Haskell中定义Monad的必备前提（GHC 7.10+强制要求）
3. 移除了多余的Node a Sentinel >>= f分支，通用分支已经覆盖该逻辑

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