为什么 Traversable 不能多次访问它的元素？
Why can't a Traversable visit its elements more than once?
我记得在某处读到像这样的类型不能 Traversable:
data Bar a = Bar a deriving(Show)
instance Functor Bar where
fmap f (Bar x) = Bar (f x)
instance Foldable Bar where
foldMap f (Bar x) = f x <> f x
我记得的一点解释是，为了 foldMap = foldMapDefault 成立，Traversable 实例必须多次访问其元素，而合法实例不能这样做。但是，我不记得为什么合法实例不能那样做。考虑这个：
instance Traversable Bar where
sequenceA (Bar x) = Bar <$ x <*> x
乍一看还不错。这样做有什么违法的？
我仍然没有解释为什么 Traversables 通常不能多次访问它们的元素，但我确实弄清楚了为什么我问题中的特定实例是非法的：
一个Traversable有三个规律：自然性、同一性、合成性。 fmap = fmapDefault和foldMap = foldMapDefault也应该是这样的。自然性因参数化而自由。对于所讨论的 Traversable，身份、fmap = fmapDefault 和 foldMap = foldMapDefault 都很容易验证。因此，一定是组合法则失败了。我开始操纵它的 sequenceA 版本并将东西插入其中，结果是这样的：
(\y z -> Bar <$ y <*> z) <$> x <*> x = (\y z -> Bar <$ z <*> z) <$> x <*> x
现在很清楚如何找到反例了。首先，我们需要找到 y 和 z 使得 Bar <$ y <*> z 和 Bar <$ z <*> z 不同。由于 y 未用于其内在值，因此它一定会产生某种效果。通过检查，y = Nothing 和 z = Just () 将导致第一个为 Nothing，第二个为 Just (Bar ())。
接下来，我们需要找到一个x，这样第一次使用x就是我们的y、Nothing，第二次使用x 将是我们的 z、Just ()。我们可以为此使用 State，其中初始状态为 Nothing，而 x 为 get <* put (Just ())。
现在我们认为我们有一个完整的反例，那么我们来验证一下。原来的定律是sequenceA . fmap Compose = Compose . fmap sequenceA . sequenceA，所以让我们把它的每一边都放在自己的变量中：
import Data.Functor.Compose
lhs = sequenceA . fmap Compose
rhs = Compose . fmap sequenceA . sequenceA
并存储我们的 x:
import Control.Monad.State
x = get <* put (Just ())
最后，把它们放在一起：
λ> evalState (getCompose $ lhs $ Bar x) Nothing
Nothing
λ> evalState (getCompose $ rhs $ Bar x) Nothing
Just (Bar ())
我们的反例有效！如果定律成立，lhs 和 rhs 将是等效的，但它们显然不是，因为将一个换成另一个会产生不同的结果。
有几个合理的有利位置可以解决这个问题。我这里的策略虽然可能有点粗糙，但效果很好，同时在没有太多技术复杂性的情况下说明了关键思想。
这个答案有两个部分。第一部分，如果reader时间不够可以独立阅读，介绍选择的视角和主要结论。第二部分通过提供详细的理由对此进行了扩展。在它的最后，有一个简明的列表，列出了 Traversable 法律允许和禁止的事情。
答案有点长，所以这里有一个章节标题列表，可以用 Ctrl+F 跳过：
第一部分
- 形状和内容
- 复制效果
- 免费的应用演示
第二部分
- 近距离可填充和可遍历
- 复制效果：再一次，有感觉
- foldMapDefault 和其他自然法则
- 执行摘要：Traversable 的注意事项
事实上，有人可能会 object 这个答案对于这种格式来说太长了。在我的辩护中，我注意到 parent 问题在有关复制效果的部分中得到解决，其他所有内容要么证明直接答案是正确的，要么与上下文相关。
形状和内容
最终，这一切都归结为我喜欢称之为 shape-and-contents 的分解。用最简单的术语来说，这意味着 Traversable 可以通过 class 编码，如下所示：
class (Functor t, Foldable t) => Fillable t where
fill :: t () -> [a] -> t a
fill 采用 t 函子形状，我们在这里使用 t () 值表示，并用 [a] 列表中的内容填充它。我们可以依靠Functor和Foldable给我们一个反方向的转换：
detach :: (Functor t, Foldable t) => t a -> (t (), [a])
detach = (() <$) &&& toList
使用 fill 和 detach，我们可以根据列表的具体 sequenceA 实现 sequenceA：分离、排序列表，然后填充：
sequenceFill :: (Fillable t, Applicative f) => t (f a) -> f (t a)
sequenceFill = uncurry (fmap . fill) . second (sequenceList) . detach
-- The usual sequenceA for lists.
sequenceList :: Applicative f => [f a] -> f [a]
sequenceList = foldr (liftA2 (:)) (pure [])
如果有点尴尬，也可以用 Traversable:
来定义 fill
-- Partial, handle with care.
fillTr :: Traversable t => t () -> [a] -> t a
fillTr = evalState . traverse (const pop)
where
pop = state (\(a : as) -> (a, as))
（有关此方法的现有技术，例如，参见 this answer。）
在Fillable方面，Traversable定律说fill和detach 几乎见证了两个方向一个同构：
fill 必须是 detach 的左逆：
uncurry fill . detach = id
这相当于Traversable的恒等律。
detach 必须表现为 fill 的左逆，只要 fill 仅提供具有兼容大小的列表和形状（否则情况无望):
-- Precondition: length (toList sh) = length as
detach . uncurry fill $ (sh, as) = (sh, as)
这个属性对应的是构图法则。事实上，它本身比合成法强。然而，如果我们假设恒等律，它在实质上等同于合成律。既然如此，可以将这些属性作为 Traversable 定律的替代表示，除非您想单独研究合成定律。 （这个near-equivalence在第二部分的回答中会有更详细的解释，等我们更仔细地看组合法之后。）
复制效果
所有这些与您的问题有什么关系？假设我们想要定义一个遍历来复制效果而不改变可遍历的形状（因为改变它会公然违反身份法则）。现在，假设我们的 sequenceA 实际上是 sequenceFill，如上定义，我们有哪些选择？由于 sequenceFill 搭载在 sequenceList 上，众所周知，它只访问每个元素一次，我们唯一的希望是依赖一个伴侣 Foldable 实例，这样 toList，因此 detach，生成一个包含重复元素的列表。在这种情况下，我们能否使 Fillable 定律成立？
第一定律问题不大。原则上，我们总是可以定义 fill 以便它取消重复，丢弃由 detach.
引入的元素的额外副本
如果我们有去重fill，然而，第二定律是失败的原因。通过参数化，fill 无法区分由 detach 引入的重复项列表与我们可能提供给它的任何其他列表，因此 detach . uncurry fill 将始终用其他元素的重复项替换某些元素.
既然如此，重复效果的 traverseFill 只能由非法 Fillable 产生。由于 Fillable 法则等同于 Traversable 法则，我们得出结论，合法的 Traversable 不能复制效果。
（上面讨论的效果复制场景，顺便说一下，适用于你的 Bar 类型：它不符合第二个 Fillable 法则，因此它也不符合 Traversable 组合定律，正如你的反例所示。）
我非常喜欢的一篇论文涵盖了这个问题和与之相关的问题是 Bird 等人，Understanding Idiomatic Traversals Backwards and Forwards (2013)。虽然乍一看可能不像那样，但它的方法与我在这里展示的内容密切相关。特别是，它的“表示定理”与这里探讨的 detach/fill 关系本质上是相同的，主要区别在于论文中的定义更严格，无需大惊小怪 fill 应该在给定长度错误的列表时执行。
免费应用演示
尽管我不会尝试呈现 Bird 等人的完整论点。论文，在这个答案的上下文中，值得注意的是它对上述表示定理的证明如何依赖于自由应用函子的公式。我们可以稍微扭曲这个想法以获得 Traversable 在 Ap from free's Control.Applicative.Free:
方面的额外表示
-- Adapted from Control.Applicative.Free.
data Ap f a where
Pure :: a -> Ap f a
Ap :: f a -> Ap f (a -> b) -> Ap f b
instance Applicative (Ap f) where
pure = Pure
Pure f <*> y = fmap f y
Ap x y <*> z = Ap x (flip <$> y <*> z)
liftAp :: f a -> Ap f a
liftAp x = Ap x (Pure id)
retractAp :: Applicative f => Ap f a -> f a
retractAp (Pure a) = pure a
retractAp (Ap x y) = x <**> retractAp y
class (Functor t, Foldable t) => Batchable t where
toAp :: t (f a) -> Ap f (t a)
sequenceBatch :: (Batchable t, Applicative f) => t (f a) -> f (t a)
sequenceBatch = retractAp . toAp
toApTr :: Traversable t => t (f a) -> Ap f (t a)
toApTr = traverse liftAp
我非常确定以下是适用的法律，但仔细检查可能是值得的：
retractAp . toAp . fmap Identity . runIdentity = id
toAp . fmap Identity . runIdentity . retractAp = id
虽然这看起来与我们开始时简陋的 detach 和 fill 组合相去甚远，但它最终只是对同一想法的更精确编码。 Ap f (t a) 值是包含在 Pure 中的单个 t a 结构，或者是零个或多个 f a 值（Ap 构造函数）的序列，由适当 arity 的函数，它需要与 f a 一样多的 a 并产生 t a。根据我们对 shape-and-contents 分解的初步尝试，我们有：
Ap值中的f a对应列表内容；
该函数（如果有的话）对重新组装可遍历结构时要使用的形状进行编码，以及应该如何填充它。 shape-list 不匹配问题在类型级别巧妙地避免了，它静态地保证函数将具有正确的 arity；
至于效果，retractAp 以明显的方式执行组合它们的作用，很像 sequenceList 在 sequenceFill 中所做的。
（第一部分结束。）
近距离可填充和可遍历
正如所承诺的那样，第二部分将从证明 Fillable 确实是 Traversable 的演示开始。在下文中，我将使用更容易用笔和纸操作的定义的调整版本：
-- Making the tuple shuffling implicit. It would have been fine to use
-- the derived Foldable and Traversable. I will refrain from that here
-- only for the sake of explicitness.
newtype Decomp t a = Decomp { getDecomp :: (t (), [a]) }
deriving Functor
deriving instance (Show a, Show (t ())) => Show (Decomp t a)
detach' :: (Functor t, Foldable t) => t a -> Decomp t a
detach' = Decomp . detach
fill' :: Fillable t => Decomp t a -> t a
fill' = uncurry fill . getDecomp
-- Sequence the list, then shift the shape into the applicative layer.
-- Also a lawful sequenceA (amounts to Compose ((,) (t ())) []).
sequenceList' :: Applicative f => Decomp t (f a) -> f (Decomp t a)
sequenceList'
= fmap Decomp . uncurry (map . (,)) . second sequenceList . getDecomp
instance Traversable Decomp where
sequenceA = sequenceList'
instance Foldable Decomp where
foldMap = foldMapDefault
sequenceFill' :: (Fillable t, Applicative f) => t (f a) -> f (t a)
sequenceFill' = fmap fill' . sequenceList' . detach'
（顺便说一句，上面更清晰的定义提供了一个很好的机会来注意，如果我们要离开写实际 Haskell 的范围，移动携带的形状不需要太多在 sequenceFill' 到类型级别的过程中，实际上根据可能的形状对可遍历函子进行分区。据我所知，这将使我们在容器的标准依赖类型处理方面取得进展。我不会在这里深入研究；如果你想探索，我衷心推荐 the answers on the topic by Conor McBride (pigworker)。）
身份
我们可以从处理恒等律开始，这是一个更直接的问题：
-- Abbreviations:
I = Identity
uI = runIdentity
C = Compose
uC = getCompose
-- Goal: Given the identity law...
sequenceFill' @_ @I . fmap I = I
-- ... obtain detach-then-fill:
fill' . detach' = id
sequenceFill' @_ @I . fmap I = I
uI . fmap fill' . sequenceList' @I . detach' . fmap I = id
-- sequenceList is lawful (identity law):
uI . fmap fill' . I . fmap uI . detach' . fmap I = id
uI . fmap fill' . I . detach' . fmap uI . fmap I = id
uI . fmap fill' . I . detach' = id
uI . I . fill' . detach' = id
fill' . detach' = id -- Goal.
由于上面推导的所有步骤都是可逆的，我们可以得出同构的detach-then-fill方向等价于恒等律
作文
关于组合规律，我们不妨从同样的策略入手：
-- Goal: Given the composition law...
sequenceFill' @_ @(C _ _) . fmap C = C . fmap sequenceFill' . sequenceFill'
-- ... obtain fill-then-detach...
detach' . fill' = id
-- ... within the domain specified by its precondition.
sequenceFill' @_ @(C _ _) . fmap C = C . fmap sequenceFill' . sequenceFill'
fmap fill' . sequenceList' @(C _ _) . detach' . fmap C
= C . fmap (fmap fill' . sequenceList' . detach')
. fmap fill' . sequenceList' . detach'
-- LHS
fmap fill' . sequenceList' @(C _ _) . detach' . fmap C
fmap fill' . sequenceList' @(C _ _) . fmap C . detach'
-- sequenceList' is lawful (composition law)
fmap fill' . C . fmap sequenceList' . sequenceList' . detach'
C . fmap (fmap fill') . fmap sequenceList' . sequenceList' . detach'
C . fmap (fmap fill' . sequenceList') . sequenceList' . toList'
-- RHS
C . fmap (fmap fill' . sequenceList' . detach')
. fmap fill' . sequenceList' . detach'
C . fmap (fmap fill' . sequenceList') . fmap (detach' . fill')
. sequenceList' . detach'
-- LHS = RHS
C . fmap (fmap fill' . sequenceList') . sequenceList' . detach'
= C . fmap (fmap fill' . sequenceList') . fmap (detach' . fill')
. sequenceList' . detach'
-- C is injective:
fmap (fmap fill' . sequenceList') . sequenceList' . detach'
= fmap (fmap fill' . sequenceList') . fmap (detach' . fill')
. sequenceList' . detach' -- On hold.
在这一点上，我们似乎陷入了比我们预期发现的 detach' . fill' = id 更弱的 属性。从好的方面来说，它有一些好处：
上面推导的所有步骤都是可逆的，所以属性等价于组合律
等式两边的sequenceList' . detach'和fmap (fmap fill' . sequenceList')额外项使得每个fill'前面都有一个detach' ，每个 detach' 后跟一个 fill'。这意味着 fill-then-detach 定律的前提条件自动成立。
fill-then-detach 法则比 属性 严格。既然如此，如果 detach' . fill' = id（在前提条件等的范围内）则此 属性 以及合成定律也成立。
我稍后会回到这些观察，以证明我早先声称 detach' . fill' = id 可以被视为 Traversable 定律。
幂等性
短暂休息，然后我们继续正常的日程安排。通过将组合法则中的两个应用函子专门化为 Identity，我们可以发现一些琐事。从我们停止的地方继续：
fmap (fmap fill' . sequenceList') . sequenceList' . detach'
= fmap (fmap fill' . sequenceList') . fmap (detach' . fill')
. sequenceList' . detach'
-- In particular:
fmap (fmap fill' . sequenceList' @I) . sequenceList' @I . detach'
= fmap (fmap fill' . sequenceList' @I) . fmap (detach' . fill')
. sequenceList' @I . detach'
-- sequenceList' is lawful (identity):
fmap (fmap fill' . I . fmap uI) . I . fmap uI . detach'
= fmap (fmap fill' . I . fmap uI) . fmap (detach' . fill') . I
. fmap uI . detach'
-- shift the I leftwards, and the uI rightwards, on both sides:
I . I . fill' . detach' . fmap uI . fmap uI
= I . I . fill' . detach' . fill' . detach' . fmap uI . fmap uI
-- I is injective, and fmap uI is surjective:
fill' . detach' = fill' . detach' . fill' . detach'
我们最终得到 fill' . detach' 的幂等性 属性，并且间接地 sequenceA。尽管就 Traversable 而言，这样的 属性 并不奇怪，因为它直接遵循恒等律，但有趣的是，它本身也遵循组合律。 （在一个相关的说明中，我有时想知道我们是否可以从 Semitraversable class 中获得任何里程，这只会有组合法则。）
复制效果：再一次，有感觉
现在是重新审视您最初的问题的好时机：究竟为什么重复效果会导致法律出现问题？ Fillable 演示文稿有助于澄清联系。我们再看一下组合律的两边，就是我们刚刚给出的形式：
fmap (fmap fill' . sequenceList')
. sequenceList' . detach' -- LHS
fmap (fmap fill' . sequenceList')
. fmap (detach' . fill')
. sequenceList' . detach' -- RHS
让我们假设恒等律成立。在这种情况下，sequenceFill' 中重复效果的唯一可能来源是被 detach' 重复的元素（因为 sequenceList' 不重复，而 fill' 不能重复，因为恒等律）。
现在，如果 detach' 在某些位置引入重复项，fill' 必须删除它们以便恒等律成立。然而，由于参数化，这些位置的元素将始终被删除，即使相关元素实际上没有被复制，因为列表不是由 detach' 创建的。换句话说，fill' 有一个前提条件是无害地删除重复项，即必须给它提供可能由 detach' 生成的列表。在组合法则中，根据应用效果的不同，第一个 sequenceList' 可能会产生超出此前提条件的列表。在这种情况下，右侧的 fmap fill' 将消除实际上没有复制的内部效果（请记住第一个 sequenceList' 仅处理外部应用层），差异将被第二个 sequenceList' . detach' 适当检测到，它作用于内部效果层，我们将以违法告终。
事实上，我们可以肯定一些更强的东西：如果sequenceFill'重复效果，总是有可能以上述方式违反法律。对于这样的说法，我们所需要的只是一个足够好的反例：
advance :: State (Const (Sum Natural) x) (Const (Sum Natural) x)
advance = get <* modify (+1)
诀窍在于，如果您对仅包含 advance 副本的列表进行排序，您将返回的列表保证不会有任何重复的 Const (Sum Natural) 效果：
GHCi> flip evalState 0 $ sequenceA (replicate 3 advance)
[Const (Sum {getSum = 0}),Const (Sum {getSum = 1}),Const (Sum {getSum = 2})]
既然如此，如果这样的列表达到了重复效果的sequenceFill'实现，其中的fmap fill'总是会丢弃non-duplicates:
data Bar a = Bar a
deriving (Show, Functor)
instance Foldable Bar where
foldMap f (Bar x) = f x <> f x
-- This corresponds to your Traversable instance.
instance Fillable Bar where
fill (Decomp (_, [x, y])) = Bar y
GHCi> flip evalState 0 <$> (advance <$ Bar ())
Bar (Const (Sum {getSum = 0}))
GHCi> flip evalState 0 <$> detach' (advance <$ Bar ())
Decomp {getDecomp = (Bar (),[Const (Sum {getSum = 0}),Const (Sum {getSum = 0})])}
GHCi> flip evalState 0 $ (sequenceList' . detach') (advance <$ Bar ())
Decomp {getDecomp = (Bar (),[Const (Sum {getSum = 0}),Const (Sum {getSum = 1})])}
GHCi> flip evalState 0 $ (fmap fill' . sequenceList' . detach') (advance <$ Bar ())
Bar (Const (Sum {getSum = 1}))
违规现在不可避免：
GHCi> lhs = fmap (fmap fill' . sequenceList') . sequenceList' . detach'
GHCi> rhs = fmap (fmap fill' . sequenceList') . fmap (detach' . fill') . sequenceList' . detach'
GHCi> flip evalState 0 $ lhs (advance <$ Bar ())
Const (Sum {getSum = 1})
GHCi> flip evalState 0 $ rhs (advance <$ Bar ())
Const (Sum {getSum = 2})
（advance，正如您可能已经注意到的，与 your answer 中的反例非常相似，只是进行了调整，以便它可以与任意 traversable-like 结构一起使用。）
这足以说明重复效果不符合合成法则
简化合成法
在这一点上，有一个方便的方法来证明为什么我们可以使用简化的 fill-then-detach 属性...
-- Precondition: length (toList sh) = length as
detach' . fill' $ (sh, as) = (sh, as)
... 代替我们在最后几节中处理的更大的组合法则。再次假设恒等律成立。在那种情况下，我们可以 class 确定 detach' 在两种情况下的可能实现：
detach' 从不重复元素。因此，detach' 在 fill-then-detach 前提条件的限制内是满射的（例如，如果可遍历函子是长度为六的向量，detach' 可以生成所有可能的列表长度为六，但它不会生成其他长度的列表）。但是，如果具有左逆函数的函数是满射的，那么它的左逆函数也是右逆函数。因此，detach' . fill' = id在前提条件的范围内，组合律成立。
(“在 fill-then-detach 前提条件的限制内”有点像挥手，但我相信可以通过使用依赖类型根据形状划分可遍历函子类型来使其变得严格，在我在第二部分开头提到的方式。）
detach' 重复元素。但是，在那种情况下，随之而来的重复效应意味着合成定律将不成立，正如我们刚刚展示的那样，更强的 detach' . fill' = id 属性.
也不成立
既然如此，只要恒等律成立，Traversable组合律和Fillablefill-then-detach律总是一致的；它们之间的区别只能出现在违反身份法的实现中。因此，如果合在一起，答案第一部分所述的 Fillable 定律等同于 Traversable 定律。
foldMapDefault 和其他自然法则
Fillable 演示文稿的一个美妙之处在于它如何明确表明我们在定义合法 sequenceA 时唯一的自由选择是效果排序的顺序.一旦通过选择 Foldable 实现选择了某个顺序，它确定了 toList 和 detach'，sequenceList' 必须在对效果进行排序时遵循该顺序。此外，由于 fill' 是（在 fill-then-detach 前提条件的范围内）detach' 的完全倒数，因此它是唯一确定的。
我们在基础库中的class层次结构没有在q中排列与 Fillable 相同：真正的 sequenceA 是 Traversable 的 self-sufficient 方法，与 sequenceFill' 不同，它不依赖于 Foldable为其实施。相反，Foldable 和 Traversable 之间的联系被超级class 相干律理顺：
-- Given:
foldMapDefault :: (Traversable t, Monoid m) => (a -> m) -> t a -> m
foldMapDefault f = getConst . traverse (Const . f)
foldMapDefault = foldMap
（Functor 和 fmapDefault 有一个类似的 属性，但参数化意味着它遵循恒等律。）
根据toList和sequenceA，这条定律变成：
toList = getConst . sequenceA . fmap (Const . (:[]))
如果我们使用 sequenceA = sequenceFill' 将我们带回 Fillable 演示文稿...
getConst . fmap fill' . sequenceList' . detach' . fmap (Const . (:[]))
getConst . fmap fill' . sequenceList' . fmap (Const . (:[])) . detach'
-- fmap @(Const _) doesn't do anything:
getConst . sequenceList' . fmap (Const . (:[])) . detach'
-- sequenceList' is lawful (foldMapDefault law):
toList @(Detach _) . detach'
snd . getDecomp . detach'
toList
...我们得出结论，foldMapDefault 定律自动成立。
Bird 等人的“'naturality' 数据类型”
继恒等律和组合律之后，Traversable 的第三大著名律是应用函子中的自然律，通常简称为自然律：
-- Precondition: h is an applicative homomorphism, that is:
-- h (pure a) = pure a
-- h (u <*> v) = h u <*> h v
h . sequenceA = sequenceA . fmap h
虽然有用，但也很重要 theory-wise（它反映了另一种观点 sequenceA 作为应用函子和应用同态类别中的自然变换，例如在 Jaskelioff 和 Rypacek 中讨论, An Investigation of the Laws of Traversals), the naturality law follows from a free theorem for sequenceA (in the vein of Voigtländer, Free Theorems Involving Constructor Classes), 所以在这个答案的上下文中没有太多要说的。
伯德等人。第一部分提到的论文在第 6 节中讨论了一种不同的自然性 属性，作者称之为“'naturality' in the datatype”。与广为人知的自然法则不同，它是可遍历函子本身的自然法则属性：
-- Precondition: r preserves toList, that is
-- toList . r = toList
fmap r . sequenceA = sequenceA . r
(Bird et al. 不要明确使用 Foldable，而是用 contents = getConst . traverse (Const . (:[]) 来说明 属性。假设 foldMapDefault 相干律成立，则没有区别。)
Fillable 视角非常适合这种自然性属性。我们可以首先注意到我们可以对某些函子 t 进行自然转换以在 Decomp t 上工作：
-- Decomp as a higher-order functor.
hmapDecomp :: (forall x. t x -> u x) -> Decomp t a -> Decomp u a
hmapDecomp r (Decomp (sh, as)) = Decomp (r sh, as)
如果r保留toList（或者，我们甚至可以说，如果它是可折叠同态），则它也保留detach'，并且vice-versa:
-- Equivalent to toList . r = toList
hmapDecomp r . detach' = detach' . r'
（hmapDecomp 不影响内容列表，而且，作为自然变换，r 与 detach' 的 (() <$) 一半交换。）
如果我们进一步假设 Fillable 定律，我们可以利用 fill' 和 detach' 是逆的事实（在 fill-then-detach 的前提条件范围内law) 将 r 从 detach' 转移到 fill':
hmapDecomp r . detach' = detach' . r
hmapDecomp r . detach' . fill' = detach' . r . fill'
hmapDecomp r = detach' . r . fill'
fill' . hmapDecomp r = fill' . detach' . r . fill'
fill' . hmapDecomp r = r . fill'
也就是说，对形状应用r然后填充它与填充然后对填充的形状应用r相同。
此时，我们可以回到 sequenceFill':
fill' . hmapDecomp r = r . fill'
fmap (fill' . hmapDecomp r) = fmap (r . fill')
fmap (fill' . hmapDecomp r) . sequenceList' . detach'
= fmap (r . fill') . sequenceList' . detach'
-- LHS
fmap (fill' . hmapDecomp r) . sequenceList' . detach'
-- sequenceList' only changes the list, and `hmapDecomp` r only the shape.
fmap fill' . sequenceList' . hmapDecomp r . detach'
-- r is a foldable homomorphism.
fmap fill' . sequenceList' . detach' . r
sequenceFill' . r
-- RHS
fmap (r . fill') . sequenceList' . detach'
fmap r . sequenceFill'
-- LHS = RHS
fmap r . sequenceFill' = sequenceFill' . r
我们因此获得了可遍历函子 属性 的自然性，正如考虑到 Fillable 和 Traversable 定律之间的等价性所预期的那样。不过，我们确实在这个过程中学到了一些东西。鸟等。在谈论这个 属性 时，我们有理由对“自然性”一词保持谨慎，因为在标准 class 层次结构的上下文中，对 toList 保留自然转换的限制似乎是无关紧要的。但是，从 Fillable 的角度来看，fill' 是由我们选择的 Foldable 实例决定的，因此 属性 与任何其他自然 属性 一样锐利对于构造函数 class。既然如此，我相信我们可以放弃围绕“自然”的恐吓引语。
执行摘要：Traversable 的注意事项
我们现在可以列出一份相当完整的 Traversable 法律后果清单。虽然没有真正的区别，但我会在这里用 traverse 来说话，因为使用它而不是 sequenceA 可以更清楚地了解“元素”与“效果”的含义。
合法traverse不得:
以任何方式改变可遍历形状，由于恒等律。
- 如果变化是幂等的，仍然会违反恒等律，但组合律可能成立。
根据恒等律删除或复制元素。
- 特别是，即使通过用其他元素覆盖某些元素来保持形状不变，也是不允许的。
重新排序可遍历结构中的元素，由于恒等律
重复效果，即使元素没有重复，由于合成法则。
合法traverse可以:
- 重新排序效果，即以与原始可遍历结构中的元素顺序不同的顺序排列效果。
- 效果的顺序甚至可以取决于结构的各个形状。
合法traverse必须:
- 按照
toList 给出的顺序排列效果Foldable 类型实例，根据 foldMapDefault 法则。
合法traverse将:
保留应用同态，即保留pure和return的自然变换，由于自然法则，自由持有。
保留可折叠同态，即保留toList/foldMap的自然变换，由于naturality-in-the-traversable 定律，遵循恒等律和合成律。
我记得在某处读到像这样的类型不能 Traversable:
data Bar a = Bar a deriving(Show)
instance Functor Bar where
fmap f (Bar x) = Bar (f x)
instance Foldable Bar where
foldMap f (Bar x) = f x <> f x
我记得的一点解释是，为了 foldMap = foldMapDefault 成立，Traversable 实例必须多次访问其元素，而合法实例不能这样做。但是，我不记得为什么合法实例不能那样做。考虑这个：
instance Traversable Bar where
sequenceA (Bar x) = Bar <$ x <*> x
乍一看还不错。这样做有什么违法的？
我仍然没有解释为什么 Traversables 通常不能多次访问它们的元素，但我确实弄清楚了为什么我问题中的特定实例是非法的：
一个Traversable有三个规律：自然性、同一性、合成性。 fmap = fmapDefault和foldMap = foldMapDefault也应该是这样的。自然性因参数化而自由。对于所讨论的 Traversable，身份、fmap = fmapDefault 和 foldMap = foldMapDefault 都很容易验证。因此，一定是组合法则失败了。我开始操纵它的 sequenceA 版本并将东西插入其中，结果是这样的：
(\y z -> Bar <$ y <*> z) <$> x <*> x = (\y z -> Bar <$ z <*> z) <$> x <*> x
现在很清楚如何找到反例了。首先，我们需要找到 y 和 z 使得 Bar <$ y <*> z 和 Bar <$ z <*> z 不同。由于 y 未用于其内在值，因此它一定会产生某种效果。通过检查，y = Nothing 和 z = Just () 将导致第一个为 Nothing，第二个为 Just (Bar ())。
接下来，我们需要找到一个x，这样第一次使用x就是我们的y、Nothing，第二次使用x 将是我们的 z、Just ()。我们可以为此使用 State，其中初始状态为 Nothing，而 x 为 get <* put (Just ())。
现在我们认为我们有一个完整的反例，那么我们来验证一下。原来的定律是sequenceA . fmap Compose = Compose . fmap sequenceA . sequenceA，所以让我们把它的每一边都放在自己的变量中：
import Data.Functor.Compose
lhs = sequenceA . fmap Compose
rhs = Compose . fmap sequenceA . sequenceA
并存储我们的 x:
import Control.Monad.State
x = get <* put (Just ())
最后，把它们放在一起：
λ> evalState (getCompose $ lhs $ Bar x) Nothing
Nothing
λ> evalState (getCompose $ rhs $ Bar x) Nothing
Just (Bar ())
我们的反例有效！如果定律成立，lhs 和 rhs 将是等效的，但它们显然不是，因为将一个换成另一个会产生不同的结果。
有几个合理的有利位置可以解决这个问题。我这里的策略虽然可能有点粗糙，但效果很好，同时在没有太多技术复杂性的情况下说明了关键思想。
这个答案有两个部分。第一部分，如果reader时间不够可以独立阅读，介绍选择的视角和主要结论。第二部分通过提供详细的理由对此进行了扩展。在它的最后，有一个简明的列表，列出了 Traversable 法律允许和禁止的事情。
答案有点长，所以这里有一个章节标题列表，可以用 Ctrl+F 跳过：
第一部分
- 形状和内容
- 复制效果
- 免费的应用演示
第二部分
- 近距离可填充和可遍历
- 复制效果：再一次，有感觉
- foldMapDefault 和其他自然法则
- 执行摘要：Traversable 的注意事项
事实上，有人可能会 object 这个答案对于这种格式来说太长了。在我的辩护中，我注意到 parent 问题在有关复制效果的部分中得到解决，其他所有内容要么证明直接答案是正确的，要么与上下文相关。
形状和内容
最终，这一切都归结为我喜欢称之为 shape-and-contents 的分解。用最简单的术语来说，这意味着 Traversable 可以通过 class 编码，如下所示：
class (Functor t, Foldable t) => Fillable t where
fill :: t () -> [a] -> t a
fill 采用 t 函子形状，我们在这里使用 t () 值表示，并用 [a] 列表中的内容填充它。我们可以依靠Functor和Foldable给我们一个反方向的转换：
detach :: (Functor t, Foldable t) => t a -> (t (), [a])
detach = (() <$) &&& toList
使用 fill 和 detach，我们可以根据列表的具体 sequenceA 实现 sequenceA：分离、排序列表，然后填充：
sequenceFill :: (Fillable t, Applicative f) => t (f a) -> f (t a)
sequenceFill = uncurry (fmap . fill) . second (sequenceList) . detach
-- The usual sequenceA for lists.
sequenceList :: Applicative f => [f a] -> f [a]
sequenceList = foldr (liftA2 (:)) (pure [])
如果有点尴尬，也可以用 Traversable:
fill
-- Partial, handle with care.
fillTr :: Traversable t => t () -> [a] -> t a
fillTr = evalState . traverse (const pop)
where
pop = state (\(a : as) -> (a, as))
（有关此方法的现有技术，例如，参见 this answer。）
在Fillable方面，Traversable定律说fill和detach 几乎见证了两个方向一个同构：
fill必须是detach的左逆：uncurry fill . detach = id这相当于
Traversable的恒等律。detach必须表现为fill的左逆，只要fill仅提供具有兼容大小的列表和形状（否则情况无望):-- Precondition: length (toList sh) = length as detach . uncurry fill $ (sh, as) = (sh, as)这个属性对应的是构图法则。事实上，它本身比合成法强。然而，如果我们假设恒等律，它在实质上等同于合成律。既然如此，可以将这些属性作为
Traversable定律的替代表示，除非您想单独研究合成定律。 （这个near-equivalence在第二部分的回答中会有更详细的解释，等我们更仔细地看组合法之后。）
复制效果
所有这些与您的问题有什么关系？假设我们想要定义一个遍历来复制效果而不改变可遍历的形状（因为改变它会公然违反身份法则）。现在，假设我们的 sequenceA 实际上是 sequenceFill，如上定义，我们有哪些选择？由于 sequenceFill 搭载在 sequenceList 上，众所周知，它只访问每个元素一次，我们唯一的希望是依赖一个伴侣 Foldable 实例，这样 toList，因此 detach，生成一个包含重复元素的列表。在这种情况下，我们能否使 Fillable 定律成立？
第一定律问题不大。原则上，我们总是可以定义
引入的元素的额外副本fill以便它取消重复，丢弃由detach.如果我们有去重
fill，然而，第二定律是失败的原因。通过参数化，fill无法区分由detach引入的重复项列表与我们可能提供给它的任何其他列表，因此detach . uncurry fill将始终用其他元素的重复项替换某些元素.
既然如此，重复效果的 traverseFill 只能由非法 Fillable 产生。由于 Fillable 法则等同于 Traversable 法则，我们得出结论，合法的 Traversable 不能复制效果。
（上面讨论的效果复制场景，顺便说一下，适用于你的 Bar 类型：它不符合第二个 Fillable 法则，因此它也不符合 Traversable 组合定律，正如你的反例所示。）
我非常喜欢的一篇论文涵盖了这个问题和与之相关的问题是 Bird 等人，Understanding Idiomatic Traversals Backwards and Forwards (2013)。虽然乍一看可能不像那样，但它的方法与我在这里展示的内容密切相关。特别是，它的“表示定理”与这里探讨的 detach/fill 关系本质上是相同的，主要区别在于论文中的定义更严格，无需大惊小怪 fill 应该在给定长度错误的列表时执行。
免费应用演示
尽管我不会尝试呈现 Bird 等人的完整论点。论文，在这个答案的上下文中，值得注意的是它对上述表示定理的证明如何依赖于自由应用函子的公式。我们可以稍微扭曲这个想法以获得 Traversable 在 Ap from free's Control.Applicative.Free:
-- Adapted from Control.Applicative.Free.
data Ap f a where
Pure :: a -> Ap f a
Ap :: f a -> Ap f (a -> b) -> Ap f b
instance Applicative (Ap f) where
pure = Pure
Pure f <*> y = fmap f y
Ap x y <*> z = Ap x (flip <$> y <*> z)
liftAp :: f a -> Ap f a
liftAp x = Ap x (Pure id)
retractAp :: Applicative f => Ap f a -> f a
retractAp (Pure a) = pure a
retractAp (Ap x y) = x <**> retractAp y
class (Functor t, Foldable t) => Batchable t where
toAp :: t (f a) -> Ap f (t a)
sequenceBatch :: (Batchable t, Applicative f) => t (f a) -> f (t a)
sequenceBatch = retractAp . toAp
toApTr :: Traversable t => t (f a) -> Ap f (t a)
toApTr = traverse liftAp
我非常确定以下是适用的法律，但仔细检查可能是值得的：
retractAp . toAp . fmap Identity . runIdentity = id
toAp . fmap Identity . runIdentity . retractAp = id
虽然这看起来与我们开始时简陋的 detach 和 fill 组合相去甚远，但它最终只是对同一想法的更精确编码。 Ap f (t a) 值是包含在 Pure 中的单个 t a 结构，或者是零个或多个 f a 值（Ap 构造函数）的序列，由适当 arity 的函数，它需要与 f a 一样多的 a 并产生 t a。根据我们对 shape-and-contents 分解的初步尝试，我们有：
Ap值中的f a对应列表内容；该函数（如果有的话）对重新组装可遍历结构时要使用的形状进行编码，以及应该如何填充它。 shape-list 不匹配问题在类型级别巧妙地避免了，它静态地保证函数将具有正确的 arity；
至于效果，
retractAp以明显的方式执行组合它们的作用，很像sequenceList在sequenceFill中所做的。
（第一部分结束。）
近距离可填充和可遍历
正如所承诺的那样，第二部分将从证明 Fillable 确实是 Traversable 的演示开始。在下文中，我将使用更容易用笔和纸操作的定义的调整版本：
-- Making the tuple shuffling implicit. It would have been fine to use
-- the derived Foldable and Traversable. I will refrain from that here
-- only for the sake of explicitness.
newtype Decomp t a = Decomp { getDecomp :: (t (), [a]) }
deriving Functor
deriving instance (Show a, Show (t ())) => Show (Decomp t a)
detach' :: (Functor t, Foldable t) => t a -> Decomp t a
detach' = Decomp . detach
fill' :: Fillable t => Decomp t a -> t a
fill' = uncurry fill . getDecomp
-- Sequence the list, then shift the shape into the applicative layer.
-- Also a lawful sequenceA (amounts to Compose ((,) (t ())) []).
sequenceList' :: Applicative f => Decomp t (f a) -> f (Decomp t a)
sequenceList'
= fmap Decomp . uncurry (map . (,)) . second sequenceList . getDecomp
instance Traversable Decomp where
sequenceA = sequenceList'
instance Foldable Decomp where
foldMap = foldMapDefault
sequenceFill' :: (Fillable t, Applicative f) => t (f a) -> f (t a)
sequenceFill' = fmap fill' . sequenceList' . detach'
（顺便说一句，上面更清晰的定义提供了一个很好的机会来注意，如果我们要离开写实际 Haskell 的范围，移动携带的形状不需要太多在 sequenceFill' 到类型级别的过程中，实际上根据可能的形状对可遍历函子进行分区。据我所知，这将使我们在容器的标准依赖类型处理方面取得进展。我不会在这里深入研究；如果你想探索，我衷心推荐 the answers on the topic by Conor McBride (pigworker)。）
身份
我们可以从处理恒等律开始，这是一个更直接的问题：
-- Abbreviations:
I = Identity
uI = runIdentity
C = Compose
uC = getCompose
-- Goal: Given the identity law...
sequenceFill' @_ @I . fmap I = I
-- ... obtain detach-then-fill:
fill' . detach' = id
sequenceFill' @_ @I . fmap I = I
uI . fmap fill' . sequenceList' @I . detach' . fmap I = id
-- sequenceList is lawful (identity law):
uI . fmap fill' . I . fmap uI . detach' . fmap I = id
uI . fmap fill' . I . detach' . fmap uI . fmap I = id
uI . fmap fill' . I . detach' = id
uI . I . fill' . detach' = id
fill' . detach' = id -- Goal.
由于上面推导的所有步骤都是可逆的，我们可以得出同构的detach-then-fill方向等价于恒等律
作文
关于组合规律，我们不妨从同样的策略入手：
-- Goal: Given the composition law...
sequenceFill' @_ @(C _ _) . fmap C = C . fmap sequenceFill' . sequenceFill'
-- ... obtain fill-then-detach...
detach' . fill' = id
-- ... within the domain specified by its precondition.
sequenceFill' @_ @(C _ _) . fmap C = C . fmap sequenceFill' . sequenceFill'
fmap fill' . sequenceList' @(C _ _) . detach' . fmap C
= C . fmap (fmap fill' . sequenceList' . detach')
. fmap fill' . sequenceList' . detach'
-- LHS
fmap fill' . sequenceList' @(C _ _) . detach' . fmap C
fmap fill' . sequenceList' @(C _ _) . fmap C . detach'
-- sequenceList' is lawful (composition law)
fmap fill' . C . fmap sequenceList' . sequenceList' . detach'
C . fmap (fmap fill') . fmap sequenceList' . sequenceList' . detach'
C . fmap (fmap fill' . sequenceList') . sequenceList' . toList'
-- RHS
C . fmap (fmap fill' . sequenceList' . detach')
. fmap fill' . sequenceList' . detach'
C . fmap (fmap fill' . sequenceList') . fmap (detach' . fill')
. sequenceList' . detach'
-- LHS = RHS
C . fmap (fmap fill' . sequenceList') . sequenceList' . detach'
= C . fmap (fmap fill' . sequenceList') . fmap (detach' . fill')
. sequenceList' . detach'
-- C is injective:
fmap (fmap fill' . sequenceList') . sequenceList' . detach'
= fmap (fmap fill' . sequenceList') . fmap (detach' . fill')
. sequenceList' . detach' -- On hold.
在这一点上，我们似乎陷入了比我们预期发现的 detach' . fill' = id 更弱的 属性。从好的方面来说，它有一些好处：
上面推导的所有步骤都是可逆的，所以属性等价于组合律
等式两边的
sequenceList' . detach'和fmap (fmap fill' . sequenceList')额外项使得每个fill'前面都有一个detach'，每个detach'后跟一个fill'。这意味着 fill-then-detach 定律的前提条件自动成立。fill-then-detach 法则比 属性 严格。既然如此，如果
detach' . fill' = id（在前提条件等的范围内）则此 属性 以及合成定律也成立。
我稍后会回到这些观察，以证明我早先声称 detach' . fill' = id 可以被视为 Traversable 定律。
幂等性
短暂休息，然后我们继续正常的日程安排。通过将组合法则中的两个应用函子专门化为 Identity，我们可以发现一些琐事。从我们停止的地方继续：
fmap (fmap fill' . sequenceList') . sequenceList' . detach'
= fmap (fmap fill' . sequenceList') . fmap (detach' . fill')
. sequenceList' . detach'
-- In particular:
fmap (fmap fill' . sequenceList' @I) . sequenceList' @I . detach'
= fmap (fmap fill' . sequenceList' @I) . fmap (detach' . fill')
. sequenceList' @I . detach'
-- sequenceList' is lawful (identity):
fmap (fmap fill' . I . fmap uI) . I . fmap uI . detach'
= fmap (fmap fill' . I . fmap uI) . fmap (detach' . fill') . I
. fmap uI . detach'
-- shift the I leftwards, and the uI rightwards, on both sides:
I . I . fill' . detach' . fmap uI . fmap uI
= I . I . fill' . detach' . fill' . detach' . fmap uI . fmap uI
-- I is injective, and fmap uI is surjective:
fill' . detach' = fill' . detach' . fill' . detach'
我们最终得到 fill' . detach' 的幂等性 属性，并且间接地 sequenceA。尽管就 Traversable 而言，这样的 属性 并不奇怪，因为它直接遵循恒等律，但有趣的是，它本身也遵循组合律。 （在一个相关的说明中，我有时想知道我们是否可以从 Semitraversable class 中获得任何里程，这只会有组合法则。）
复制效果：再一次，有感觉
现在是重新审视您最初的问题的好时机：究竟为什么重复效果会导致法律出现问题？ Fillable 演示文稿有助于澄清联系。我们再看一下组合律的两边，就是我们刚刚给出的形式：
fmap (fmap fill' . sequenceList')
. sequenceList' . detach' -- LHS
fmap (fmap fill' . sequenceList')
. fmap (detach' . fill')
. sequenceList' . detach' -- RHS
让我们假设恒等律成立。在这种情况下，sequenceFill' 中重复效果的唯一可能来源是被 detach' 重复的元素（因为 sequenceList' 不重复，而 fill' 不能重复，因为恒等律）。
现在，如果 detach' 在某些位置引入重复项，fill' 必须删除它们以便恒等律成立。然而，由于参数化，这些位置的元素将始终被删除，即使相关元素实际上没有被复制，因为列表不是由 detach' 创建的。换句话说，fill' 有一个前提条件是无害地删除重复项，即必须给它提供可能由 detach' 生成的列表。在组合法则中，根据应用效果的不同，第一个 sequenceList' 可能会产生超出此前提条件的列表。在这种情况下，右侧的 fmap fill' 将消除实际上没有复制的内部效果（请记住第一个 sequenceList' 仅处理外部应用层），差异将被第二个 sequenceList' . detach' 适当检测到，它作用于内部效果层，我们将以违法告终。
事实上，我们可以肯定一些更强的东西：如果sequenceFill'重复效果，总是有可能以上述方式违反法律。对于这样的说法，我们所需要的只是一个足够好的反例：
advance :: State (Const (Sum Natural) x) (Const (Sum Natural) x)
advance = get <* modify (+1)
诀窍在于，如果您对仅包含 advance 副本的列表进行排序，您将返回的列表保证不会有任何重复的 Const (Sum Natural) 效果：
GHCi> flip evalState 0 $ sequenceA (replicate 3 advance)
[Const (Sum {getSum = 0}),Const (Sum {getSum = 1}),Const (Sum {getSum = 2})]
既然如此，如果这样的列表达到了重复效果的sequenceFill'实现，其中的fmap fill'总是会丢弃non-duplicates:
data Bar a = Bar a
deriving (Show, Functor)
instance Foldable Bar where
foldMap f (Bar x) = f x <> f x
-- This corresponds to your Traversable instance.
instance Fillable Bar where
fill (Decomp (_, [x, y])) = Bar y
GHCi> flip evalState 0 <$> (advance <$ Bar ())
Bar (Const (Sum {getSum = 0}))
GHCi> flip evalState 0 <$> detach' (advance <$ Bar ())
Decomp {getDecomp = (Bar (),[Const (Sum {getSum = 0}),Const (Sum {getSum = 0})])}
GHCi> flip evalState 0 $ (sequenceList' . detach') (advance <$ Bar ())
Decomp {getDecomp = (Bar (),[Const (Sum {getSum = 0}),Const (Sum {getSum = 1})])}
GHCi> flip evalState 0 $ (fmap fill' . sequenceList' . detach') (advance <$ Bar ())
Bar (Const (Sum {getSum = 1}))
违规现在不可避免：
GHCi> lhs = fmap (fmap fill' . sequenceList') . sequenceList' . detach'
GHCi> rhs = fmap (fmap fill' . sequenceList') . fmap (detach' . fill') . sequenceList' . detach'
GHCi> flip evalState 0 $ lhs (advance <$ Bar ())
Const (Sum {getSum = 1})
GHCi> flip evalState 0 $ rhs (advance <$ Bar ())
Const (Sum {getSum = 2})
（advance，正如您可能已经注意到的，与 your answer 中的反例非常相似，只是进行了调整，以便它可以与任意 traversable-like 结构一起使用。）
这足以说明重复效果不符合合成法则
简化合成法
在这一点上，有一个方便的方法来证明为什么我们可以使用简化的 fill-then-detach 属性...
-- Precondition: length (toList sh) = length as
detach' . fill' $ (sh, as) = (sh, as)
... 代替我们在最后几节中处理的更大的组合法则。再次假设恒等律成立。在那种情况下，我们可以 class 确定 detach' 在两种情况下的可能实现：
detach'从不重复元素。因此，detach'在 fill-then-detach 前提条件的限制内是满射的（例如，如果可遍历函子是长度为六的向量，detach'可以生成所有可能的列表长度为六，但它不会生成其他长度的列表）。但是，如果具有左逆函数的函数是满射的，那么它的左逆函数也是右逆函数。因此，detach' . fill' = id在前提条件的范围内，组合律成立。(“在 fill-then-detach 前提条件的限制内”有点像挥手，但我相信可以通过使用依赖类型根据形状划分可遍历函子类型来使其变得严格，在我在第二部分开头提到的方式。）
也不成立detach'重复元素。但是，在那种情况下，随之而来的重复效应意味着合成定律将不成立，正如我们刚刚展示的那样，更强的detach' . fill' = id属性.
既然如此，只要恒等律成立，Traversable组合律和Fillablefill-then-detach律总是一致的；它们之间的区别只能出现在违反身份法的实现中。因此，如果合在一起，答案第一部分所述的 Fillable 定律等同于 Traversable 定律。
foldMapDefault 和其他自然法则
Fillable 演示文稿的一个美妙之处在于它如何明确表明我们在定义合法 sequenceA 时唯一的自由选择是效果排序的顺序.一旦通过选择 Foldable 实现选择了某个顺序，它确定了 toList 和 detach'，sequenceList' 必须在对效果进行排序时遵循该顺序。此外，由于 fill' 是（在 fill-then-detach 前提条件的范围内）detach' 的完全倒数，因此它是唯一确定的。
我们在基础库中的class层次结构没有在q中排列与 Fillable 相同：真正的 sequenceA 是 Traversable 的 self-sufficient 方法，与 sequenceFill' 不同，它不依赖于 Foldable为其实施。相反，Foldable 和 Traversable 之间的联系被超级class 相干律理顺：
-- Given:
foldMapDefault :: (Traversable t, Monoid m) => (a -> m) -> t a -> m
foldMapDefault f = getConst . traverse (Const . f)
foldMapDefault = foldMap
（Functor 和 fmapDefault 有一个类似的 属性，但参数化意味着它遵循恒等律。）
根据toList和sequenceA，这条定律变成：
toList = getConst . sequenceA . fmap (Const . (:[]))
如果我们使用 sequenceA = sequenceFill' 将我们带回 Fillable 演示文稿...
getConst . fmap fill' . sequenceList' . detach' . fmap (Const . (:[]))
getConst . fmap fill' . sequenceList' . fmap (Const . (:[])) . detach'
-- fmap @(Const _) doesn't do anything:
getConst . sequenceList' . fmap (Const . (:[])) . detach'
-- sequenceList' is lawful (foldMapDefault law):
toList @(Detach _) . detach'
snd . getDecomp . detach'
toList
...我们得出结论，foldMapDefault 定律自动成立。
Bird 等人的“'naturality' 数据类型”
继恒等律和组合律之后，Traversable 的第三大著名律是应用函子中的自然律，通常简称为自然律：
-- Precondition: h is an applicative homomorphism, that is:
-- h (pure a) = pure a
-- h (u <*> v) = h u <*> h v
h . sequenceA = sequenceA . fmap h
虽然有用，但也很重要 theory-wise（它反映了另一种观点 sequenceA 作为应用函子和应用同态类别中的自然变换，例如在 Jaskelioff 和 Rypacek 中讨论, An Investigation of the Laws of Traversals), the naturality law follows from a free theorem for sequenceA (in the vein of Voigtländer, Free Theorems Involving Constructor Classes), 所以在这个答案的上下文中没有太多要说的。
伯德等人。第一部分提到的论文在第 6 节中讨论了一种不同的自然性 属性，作者称之为“'naturality' in the datatype”。与广为人知的自然法则不同，它是可遍历函子本身的自然法则属性：
-- Precondition: r preserves toList, that is
-- toList . r = toList
fmap r . sequenceA = sequenceA . r
(Bird et al. 不要明确使用 Foldable，而是用 contents = getConst . traverse (Const . (:[]) 来说明 属性。假设 foldMapDefault 相干律成立，则没有区别。)
Fillable 视角非常适合这种自然性属性。我们可以首先注意到我们可以对某些函子 t 进行自然转换以在 Decomp t 上工作：
-- Decomp as a higher-order functor.
hmapDecomp :: (forall x. t x -> u x) -> Decomp t a -> Decomp u a
hmapDecomp r (Decomp (sh, as)) = Decomp (r sh, as)
如果r保留toList（或者，我们甚至可以说，如果它是可折叠同态），则它也保留detach'，并且vice-versa:
-- Equivalent to toList . r = toList
hmapDecomp r . detach' = detach' . r'
（hmapDecomp 不影响内容列表，而且，作为自然变换，r 与 detach' 的 (() <$) 一半交换。）
如果我们进一步假设 Fillable 定律，我们可以利用 fill' 和 detach' 是逆的事实（在 fill-then-detach 的前提条件范围内law) 将 r 从 detach' 转移到 fill':
hmapDecomp r . detach' = detach' . r
hmapDecomp r . detach' . fill' = detach' . r . fill'
hmapDecomp r = detach' . r . fill'
fill' . hmapDecomp r = fill' . detach' . r . fill'
fill' . hmapDecomp r = r . fill'
也就是说，对形状应用r然后填充它与填充然后对填充的形状应用r相同。
此时，我们可以回到 sequenceFill':
fill' . hmapDecomp r = r . fill'
fmap (fill' . hmapDecomp r) = fmap (r . fill')
fmap (fill' . hmapDecomp r) . sequenceList' . detach'
= fmap (r . fill') . sequenceList' . detach'
-- LHS
fmap (fill' . hmapDecomp r) . sequenceList' . detach'
-- sequenceList' only changes the list, and `hmapDecomp` r only the shape.
fmap fill' . sequenceList' . hmapDecomp r . detach'
-- r is a foldable homomorphism.
fmap fill' . sequenceList' . detach' . r
sequenceFill' . r
-- RHS
fmap (r . fill') . sequenceList' . detach'
fmap r . sequenceFill'
-- LHS = RHS
fmap r . sequenceFill' = sequenceFill' . r
我们因此获得了可遍历函子 属性 的自然性，正如考虑到 Fillable 和 Traversable 定律之间的等价性所预期的那样。不过，我们确实在这个过程中学到了一些东西。鸟等。在谈论这个 属性 时，我们有理由对“自然性”一词保持谨慎，因为在标准 class 层次结构的上下文中，对 toList 保留自然转换的限制似乎是无关紧要的。但是，从 Fillable 的角度来看，fill' 是由我们选择的 Foldable 实例决定的，因此 属性 与任何其他自然 属性 一样锐利对于构造函数 class。既然如此，我相信我们可以放弃围绕“自然”的恐吓引语。
执行摘要：Traversable 的注意事项
我们现在可以列出一份相当完整的 Traversable 法律后果清单。虽然没有真正的区别，但我会在这里用 traverse 来说话，因为使用它而不是 sequenceA 可以更清楚地了解“元素”与“效果”的含义。
合法traverse不得:
以任何方式改变可遍历形状，由于恒等律。
- 如果变化是幂等的，仍然会违反恒等律，但组合律可能成立。
根据恒等律删除或复制元素。
- 特别是，即使通过用其他元素覆盖某些元素来保持形状不变，也是不允许的。
重新排序可遍历结构中的元素，由于恒等律
重复效果，即使元素没有重复，由于合成法则。
合法traverse可以:
- 重新排序效果，即以与原始可遍历结构中的元素顺序不同的顺序排列效果。
- 效果的顺序甚至可以取决于结构的各个形状。
合法traverse必须:
- 按照
toList给出的顺序排列效果Foldable类型实例，根据foldMapDefault法则。
合法traverse将:
保留应用同态，即保留
pure和return的自然变换，由于自然法则，自由持有。保留可折叠同态，即保留
toList/foldMap的自然变换，由于naturality-in-the-traversable 定律，遵循恒等律和合成律。