为什么Traversable不允许多次访问其元素？

Question

为什么Traversable不允许多次访问其元素？

7

我记得在某处读到过，像这样的类型无法被 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

一开始看起来似乎没什么问题。这样做有什么违法的吗？

- Joseph Sible-Reinstate Monica

4

这个非常好的问题由Bird等人处理，《理解惯用遍历的正反向方式》（特别是第7节，接近给出直接答案）。（我会尝试以一种非正式的方式在答案中解释它，假设在我发布之前没有其他人来这里使其变得多余。） - duplode

正如承诺的那样，我已经添加了“Fillable”和“Traversable”法律等价性的完整推导，以及对您特定问题的更深入探讨（在第二个新部分中关于复制效果），以及一些补充材料。我一直想把这些东西好好地写下来，所以非常感谢您给我提供了这个机会。 - duplode

2个回答

3

有几个合理的视角可以解决这个问题。我的策略或许有点粗糙，但可以胜任任务，同时阐述了关键思想，没有太多技术复杂性。

这个答案分为两部分。第一部分可以独立阅读，如果读者时间紧缺，它介绍了所选的观点和主要结论。第二部分通过提供详细的理由来扩展这个观点。在最后，有一个简明的列表，列出了可允许和不允许的Traversable法则。

答案变得有点长，所以这里是一个节标题的列表，可以用Ctrl+F跳过：

- 第一部分 - 形状和内容 - 复制效果 - 自由应用程序演示 - 第二部分 - 填充和Traversable，近距离观察 - 再次复制效果，带着感觉 - foldMapDefault和其他自然法则 - 执行摘要：Traversable的可行和不可行之处

实际上，有人可能会认为这个答案在这种格式下太长了。为了辩护，我指出父问题已在关于复制效果的部分中得到解答，其他所有内容要么证明了直接回答的正确性，要么与上下文相关。

形状和内容

归根结底，一切都取决于我所称的形状和内容分解。简单来说，它意味着Traversable可以通过像这样的类进行编码：

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 must be a left inverse of detach:
```
 uncurry fill . detach = id
```
This amounts to the identity law of Traversable.
detach must behave as a left inverse of fill as long as fill is only supplied lists and shapes with compatible sizes (otherwise the situation is hopeless):
```
 -- Precondition: length (toList sh) = length as
 detach . uncurry fill $ (sh, as) = (sh, as)
```
This property corresponds to the composition law. On its own, it is, in fact, stronger than the composition law. If we assume the identity law, however, it becomes materially equivalent to the composition law. That being so, it is fine to take these properties as an alternate presentation of the Traversable laws, except perhaps if you want to study the composition law in isolation. (There will be a more detailed explanation of this near-equivalence in the second part of the answer, after we look more closely at the composition law.)

复制效果

那与您的问题有什么关系呢？假设我们想定义一个遍历，它可以复制效果而不改变可遍历形状（因为改变将是违反身份法则的明显违规行为）。现在，假设我们的sequenceA实际上是上面定义的sequenceFill，我们有哪些选择？由于sequenceFill依赖于sequenceList，后者已知会恰好访问每个元素一次，我们唯一的希望是依靠一个伴随的Foldable实例，使得toList，因此detach，生成一个带有重复元素的列表。我们能在这种情况下使Fillable定律成立吗？

第一条法则并不是一个大问题。原则上，我们可以始终定义fill，以便它撤消重复，丢弃detach引入的元素的额外副本。
然而，如果我们有一个去重的fill，第二个法则就是一个失败的案例。根据参数性，fill无法区分具有由detach引入的重复项的列表和我们可能提供给它的任何其他列表，因此detach . uncurry fill将始终用其他元素的副本替换某些元素。

既然如此，只有非法的Fillable才能产生会复制效果的traverseFill。由于Fillable定律等同于Traversable定律，我们得出结论：合法的Traversable不能复制效果。

（顺便说一下，上面讨论的效果复制场景也适用于您的Bar类型：它未通过第二个Fillable定律，因此它也未通过Traversable组合定律，正如您的反例所示。）

我非常喜欢的一篇论文涉及到这个问题和相关事项，那就是Bird等人的《理解惯用遍历正反方向》（2013）。尽管乍一看可能不像，但它的方法与我在这里展示的方法密切相关。特别是，它的“表示定理”基本上与此处探讨的detach/fill关系相同，主要区别在于该论文中的定义更加严格，消除了在给出错误长度的列表时需要纠结fill应该做什么的需求。

自由应用介绍

尽管我不会尝试呈现Bird等人论文的全部论点，但在这个答案的背景下，值得注意的是它所证明的上述表示定理如何依赖于自由应用函子的一个公式。我们可以稍微扭曲这个想法，以获得关于Traversable的额外演示，其中包括free的Control.Applicative.Free中的Ap。

-- 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构造函数），以及适当元数的函数，该函数接受与f a相同数量的a并生成一个t a。就我们对形状和内容分解的初始尝试而言，我们有：

Ap 值中的 f a 对应于内容列表;
函数（如果有）编码了在重新组装可遍历结构时要使用的形状以及如何填充它。类型级别上巧妙地避免了形状列表不匹配的问题，因为静态保证函数将具有正确的元数;
至于效果，retractAp 执行将它们以显而易见的方式组合的角色，就像 sequenceFill 中的 sequenceList 一样。

（第一部分结束。）

Fillable 和 Traversable，近距离观察

正如承诺的那样，第二部分将从证明 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'中一路携带的形状移动到类型级别并不需要太多的工作，实际上可以根据可能的形状划分可遍历的函子。据我所知，这将使我们走上标准的依赖类型容器处理之路。我不会在这里进一步探讨; 如果你想探索，我衷心推荐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.

由于上述推导中的所有步骤都是可逆的，因此我们可以得出同构的分离-填充方向等价于恒等律。

组合

至于组合律，我们可以采用相同的策略：

-- 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'之后。
填充-分离定律比这个属性严格更强。因此，如果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类，它仅具有组合法则。）

重复效果：再来一次，有感觉地

现在是重新审视您最初的问题的好时机：为什么重复效果会导致法则方面的麻烦？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'将不可避免地丢弃非重复项。

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，正如您可能已经注意到的那样，与您的答案中的反例非常相似，只是进行了微调，以便可以与任意可遍历的结构一起使用。)

这足以表明效果的重复与组合法则不兼容。

简化组合法则

此时，有一种方便的方法来证明为什么我们可以使用简化的填充-然后-分离属性...

-- Precondition: length (toList sh) = length as
detach' . fill' $ (sh, as) = (sh, as)

在过去的几个部分中，我们一直在处理更为臃肿的组合法。现在，假设恒等律成立，我们可以将detach'的可能实现分类为两种情况：

detach' 不会复制元素。因此，在填充-分离前提条件的限制下，detach' 是满射的（例如，如果可遍历的函数对象是长度为6的向量，则detach' 可以生成所有长度为6的可能列表，但不会生成其他长度的列表）。如果一个具有左逆的函数是满射的，则其左逆也是右逆。因此，在前提条件的范围内，detach' . fill' = id，并且组合律成立。

（“在填充-分离前提条件的限制下”这一点可能感觉像是敷衍了事，但我相信可以通过使用依赖类型将可遍历的函数对象类型按形状划分来使其严格化，就像我在第二部分开头所暗示的那样。）
detach' 会复制元素。在这种情况下，由于随后的效果重复，组合律不再成立，正如我们刚刚证明的那样，更强的 detach' . fill' = id 特性也不再成立。

因此，只要满足恒等律，Traversable组合法则和Fillable填充-分离法则总是一致的；它们之间的差异只能在违反恒等律的实现中显示出来。因此，如果将它们放在一起，答案第一部分中所述的Fillable法则等同于Traversable法则。

foldMapDefault和其他自然性法则

Fillable表述的一个美妙特性是，它明确了我们在定义合法的sequenceA时唯一的自由选择是按顺序对效果进行排序。一旦通过选择Foldable实现来选择某个特定的顺序，该实现确定了toList和detach'，sequenceList'必须遵循该顺序以便对效果进行排序。此外，由于fill'（在填充-分离前提的范围内）是detach'的完全反函数，因此它是唯一确定的。

我们在基本库中拥有的类层次结构与Fillable不完全相同:真正的sequenceA是Traversable的一个自给自足的方法，不像sequenceFill'那样，在实现时并不依赖于Foldable。相反，Foldable与Traversable之间的联系是通过一个超类协调定律加以解决的。

-- 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等人的“数据类型中的自然性”

在恒等律和组合律之后，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

虽然有用，从理论上也很重要（它反映了sequenceA的另一种观点，即在适用函子和适用同态范畴中作为自然变换的观点，例如在Jaskelioff和Rypacek的An Investigation of the Laws of Traversals中讨论），但自然性法则是由于sequenceA的自由定理而得出的（类似于Voigtländer的Free Theorems Involving Constructor Classes），因此在本答案的背景下没有太多可说的。

在第一部分提到的Bird等人的论文中，在第6节中讨论了一个不同的自然性属性，作者称之为“数据类型中的自然性”。与更为知名的自然性法则不同，它是遍历函子本身的自然性属性：

-- Precondition: r preserves toList, that is
-- toList . r = toList
fmap r . sequenceA = sequenceA . r

(Bird等人并没有明确使用“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'，反之亦然：

-- Equivalent to toList . r = toList
hmapDecomp r . detach' = detach' . r'

(hmapDecomp 不会影响内容列表，并且作为一种自然变换，r 与 (() <$) 的 detach' 部分是可交换的。)

如果我们进一步假设 Fillable 法则，我们可以利用 fill' 和 detach' 是反函数的事实（在填充-分离法则的前提条件下），将 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定律之间的等价性。尽管如此，在这个过程中我们确实学到了一些东西。Bird等人在谈论这个属性时对“自然性”一词持谨慎态度是有道理的，因为在标准类层次结构的上下文中，限制于保留toList的自然变换似乎是不必要的。然而，从Fillable的角度来看，fill'由我们选择的Foldable实例确定，因此该属性与构造器类的任何其他自然性属性一样尖锐。既然如此，我相信我们可以放弃“自然性”周围的引号。

执行摘要：可遍历的dos和don'ts

我们现在能够列出可遍历定律的相当完整的后果清单。虽然没有真正的区别，但我将在这里用traverse来讲述，因为使用它而不是sequenceA使得“元素”与“效应”更加清晰。

一个合法的 traverse 不允许:

由于恒等律，以任何方式改变遍历的形状。
- 如果更改是幂等的，则仍将违反恒等律，但组合律可能成立。
删除或复制元素，由于恒等律。
- 特别地，即使通过用其他元素覆盖一些元素来保持形状不变也是不允许的。
由于恒等律，重新排列遍历结构中的元素。
即使没有元素的重复，也不允许重复效果，由于组合律。

一个合法的 traverse 可以允许:

重新排列效果，即按与原始遍历结构中元素不同的顺序序列化效果。
- 效果的顺序甚至可以取决于结构的个体形状。

一个合法的 traverse 必须：

按照 toList 的顺序依次执行序列效果，这是由于类型的 Foldable 实例中的 foldMapDefault 法则造成的。

一个合法的 traverse 将会：

保留 applicative homomorphisms，即保留 pure 和 return 的自然变换，这是由自然性法则自由地保持的。
保留 foldable homomorphisms，即保留 toList/foldMap 的自然变换，这是由自然性-in-the-traversable法则根据恒等和组合法则推导出来的。

- duplode

Jaskelioff和Rypacek特别提到非重复是他们所称的线性定律（我们称之为组合定律）的结果。 - dfeuer

1

@dfeuer虽然Jaskelioff和Rypacek在第4.2节中讨论了非重复性，并通过反例的方式提出了与法律的联系，但我认为他们没有提供明确的证据。在这方面，Bird等人更进一步。 - duplode

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Joseph Sible-Reinstate Monica · Accepted Answer

我仍然无法解释为什么一般的Traversable不能多次访问它们的元素，但我确实找出了为什么我问题中的特定实例是不合法的：

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 应该是等价的，但它们显然不是，因为将一个替换为另一个会得到不同的结果。