求证：满足Applicative与Foldable的Monoid类型是否可推导Traversable实例？

我最近琢磨出一个有意思的结论：对于所有满足Applicative和Foldable约束，且其所有实例t a均为Monoid的类型构造器t :: * -> *，我们可以自动推导出对应的Traversable实例。

核心实现：sequenceA函数 #

下面是我写出的sequenceA实现——它正是Traversable类型类的核心方法：

sequenceA :: (Applicative t, Foldable t, Monoid (t a), Applicative f) => t (f a) -> f (t a)
sequenceA = foldl (liftA2 $ \b a -> mappend b (pure a)) (pure mempty)

代码逻辑拆解 #

让我一步步解释这段代码的工作原理：

• 借助Foldable的foldl方法，我们可以遍历输入的t (f a)结构
• 初始值设为pure mempty：把Monoid的单位值（空结构）嵌入到目标上下文f中
• 每遍历到一个f a元素时，用liftA2把两个上下文值结合：
  1. 用t的Applicative实例提供的pure，把当前a包装成一个仅包含该元素的t a结构
  2. 用Monoid的mappend，把这个新生成的t a和之前累积的t a合并
  3. liftA2帮我们把整个合并操作提升到f上下文里，确保所有操作都在Applicative环境中完成

实际示例验证 #

我们用最常见的列表类型[]来验证，它完全满足所有约束：

• []是Applicative（pure生成单元素列表，<*>是列表的遍历应用）
• []是Foldable（支持各种折叠操作）
• [a]是Monoid（mappend是列表拼接，mempty是空列表）

测试代码如下：

-- 输入: [Just 1, Just 2, Just 3]
-- 调用sequenceA后输出: Just [1,2,3]

-- 输入: [Just 1, Nothing, Just 3]
-- 调用sequenceA后输出: Nothing

这个结果和列表原生的Traversable实例行为完全一致，说明这个实现是可行的。

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