Haskell实现Applicative List：是否必须使用辅助函数concatenation？

这是一项自主练习。为了让<*>的最后一种情况正常运行，我实现了concatenation作为辅助函数。我是否遗漏了更简便的实现方式？即能否无需辅助函数或以其他形式编写该情况？（我的主要参考资料是Haskell Wikibook）

我的代码如下：

data List a = Empty | Item a (List a)
    deriving (Eq, Ord, Show, Read)

instance Functor List where
    fmap ab Empty       = Empty
    fmap ab (Item a la) = Item (ab a) (fmap ab la)

instance Applicative List where
    pure a                    = Item a Empty
    Empty       <*> _         = Empty
    _           <*> Empty     = Empty
    Item ab lab <*> Item a la = -- 这是我有疑问的情况
        Item (ab a) (concatenation (ab <$> la) (lab <*> Item a la))

根据我有限的经验，此前实现实例从未需要辅助函数，因此我怀疑此处是否有必要使用它。

解答 #

你的自定义List本质是标准单链表，而List的Applicative实例语义是笛卡尔积——把函数列表里的每个函数，应用到元素列表的每个元素上，收集所有结果。这种语义天然需要列表拼接操作，所以辅助函数其实是合理的，但你可以换更简洁的写法，或者把拼接逻辑内联到实例里：

方式1：局部定义拼接函数

把concatenation（也就是常用的列表拼接append）作为实例内部的局部函数，避免全局定义辅助函数：

instance Applicative List where
    pure a = Item a Empty
    Empty <*> _ = Empty
    _ <*> Empty = Empty
    Item ab lab <*> Item a la = 
        let append Empty ys = ys
            append (Item x xs) ys = Item x (append xs ys)
        in Item (ab a) (append (fmap ab la) (lab <*> Item a la))

方式2：用concatMap思路重构<*>

换个角度，<*>可以理解为“对每个函数，用它映射元素列表，再把所有结果拼起来”。基于这个逻辑，用concatMap的思路实现会更清晰：

instance Applicative List where
    pure a = Item a Empty
    fs <*> xs = concatMap (\f -> fmap f xs) fs
      where
        concatMap _ Empty = Empty
        concatMap f (Item x xs) = append (f x) (concatMap f xs)
        append Empty ys = ys
        append (Item y ys) zs = Item y (append ys zs)

补充说明

不用纠结“是否需要辅助函数”——列表拼接是List类型的核心操作之一，不管是全局定义还是局部内联，它都是实现Applicative语义的必要部分。你之前没用到辅助函数，可能是因为其他类型的Applicative实例不需要这种聚合操作，但List的情况特殊，它的<*>天然需要把多个子列表的结果合并。

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