已知foldMap可通过traverse实现，如何用foldMap实现traverse？能否完成？

好问题！其实反过来用foldMap实现traverse是完全可行的，但需要借助**自由 applicative 结构（Free Applicative）**来搭建Monoid（foldMap依赖的代数结构）和Applicative（traverse依赖的结构）之间的桥梁。

核心思路 #

foldMap的作用是把遍历型结构（Traversable）里的每个元素映射成Monoid实例，再折叠成一个单一的Monoid值。而traverse需要把每个元素的f a（f是Applicative）组合成f (t a)。自由 applicative（Ap类型）正好能把Applicative操作编码成可折叠的结构，让foldMap可以处理。

具体实现代码 #

首先需要导入Control.Applicative.Free模块里的Ap相关工具，然后就能写出实现：

import Control.Applicative.Free (Ap, runAp, liftAp)

traverse :: (Traversable t, Applicative f) => (a -> f b) -> t a -> f (t b)
traverse f = runAp sequenceA . foldMap (liftAp . f)

代码解释 #

1. liftAp . f：把每个a转换成Ap f b——liftAp的作用是把普通的Applicative值包裹成自由 applicative 结构，这样它就具备了可折叠的Monoid行为（自由 applicative 天然支持按顺序组合操作）。
2. foldMap (...)：用foldMap把整个遍历型结构t a里的所有Ap f b折叠成一个单一的Ap f (t b)，这个过程会保留原结构的顺序信息（对应traverse的顺序执行逻辑）。
3. runAp sequenceA：把自由 applicative 结构还原成真正的Applicative值。runAp接受一个函数，这里用sequenceA把Ap里的操作序列转换成最终的f (t b)。

为什么需要自由 applicative？ #

直接用普通Applicative值无法被foldMap处理，因为Applicative本身不是Monoid（除非有特殊实例）。而自由 applicative 相当于给Applicative操作做了一层“可折叠”的包装，既保留了Applicative的顺序组合能力，又满足了foldMap对Monoid的要求，完美填补了两者之间的 gap。

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