Traversable如何利用其同时作为Foldable和Functor的子类这一事实？

Question

class (Functor t, Foldable t) => Traversable t where

    traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
    traverse g = sequenceA . fmap g

    sequenceA :: Applicative f => t (f a) -> f (t a)
    sequenceA = traverse id

Traversable如何利用其同时是Foldable和Functor的子类？

可遍历类型t意味着它同时也是函数子类型和可折叠类型。

我发现traverse使用了t是函数类型的事实，即fmap。 t是可折叠类型的事实在哪里被使用？ traverse是否使用了t是可折叠类型的事实？ sequenceA使用了哪一个事实：t是函数类型，t是可折叠类型，还是两者都是？

我们能否定义一个只是Functor的子类并以相同的方式定义traverse和sequenceA的类？

谢谢。

- Tim

Answer 1

没有使用Foldable实例。尽管如此，要求Foldable是可以的，因为如果我们可以遍历一个东西，那么我们就可以foldMap它：

foldMapDefault :: (Traversable t, Monoid m) => (a -> m) -> t a -> m
foldMapDefault f = fst . traverse (\a -> (f a, ()))

基本思想是使用标准的writer monad；由于writer的绑定操作使用mappend来组合“写入”的部分——这里是f a值——traverse将仅正确地mappend在一起。 （它还会建立一个t()，我们实际上并不关心；抛弃那部分的工作是fst的工作。）

为了简单和自包含性，我使用了writer monad，但真正的实现使用稍微费解的Const应用程序来避免构建（然后抛弃）不太有趣的t()值。 您可以在此处查看foldMapDefault的文档以及其实现此处。

- Daniel Wagner

---

“Const” 有什么神奇的地方？是的，“foldMapDefault”的实现充满了强制转换的魔力，但这并不是必要的。 - dfeuer

基于这位用户的其他问题，我的判断是给该用户的好答案应该一次只介绍一个新想法。将一个遍历转换为折叠已经是这一个想法了。我只能希望作者单子函子不是第二个想法，更不用说那个不太复杂但也不太流行的Const应用函子了。 - Daniel Wagner

Answer 2

通常情况下，派生子类有两个主要原因:

1. 你需要这个类来使你的定义工作，或者它使实现变得更加清晰，以至于不将其放在其中就没有意义。对于 Functor 就是这种情况。

2. 你可以从已有的主要定义部分自动派生出其他类，因此最好声明它。对于 Foldable 就是这种情况。

- Karl Bielefeldt

---

超类还有其他的原因。Num 是 Integral 的超类，因为如果某物不是数字，那么它就不可能是整数。Semigroup 现在是 Monoid 的超类，因为一个带有恒等元素的半群就是一个幺半群（在数学上）。 - dfeuer

@dfeuer，半群-幺半群关系可以说是在这里的第二点中。 - Daniel Wagner

@DanielWagner，这只是纯粹的历史偶然。 - dfeuer

Answer 3

从这里可以看到，类Traversable是一个Functor和一个Foldable，必须满足以下规律：

而Foldable更多信息见这里。这意味着它可以被折叠（foldMap，foldr，foldl...）

traverse函数必须满足以下规律：

• 自然性:

  对于每个应用变换t，t.traverse f = traverse (t.f)

• 身份

  traverse Identity = Identity

• 组合

  traverse(Compose.fmap g.f)=Compose.fmap(traverse g).traverse f

还有sequenceA：

• 自然性

  t.sequenceA = sequenceA.fmap t对于每个应用变换t

• 身份

  sequenceA.fmap Identity = Identity

• 组合

  sequenceA.fmap Compose = Compose.fmap sequenceA.sequenceA

sequenceA使用哪个事实：t是Functor类型，t是Foldable类型还是两者兼而有之？

Traversable，正如它的定义所说（以及上面引用的规律）：

class (Functor t, Foldable t) => Traversable t where

它既是一个Functor，又是一个Foldable，必须遵守的规则不仅限于Functor，它更为具体，但仍然是一个Functor，因为满足Functor的规则并且可以使用其类型类接口中的函数，甚至比Foldable更为具体，因此更强大、更少通用、更有约束力。

那么事实是什么呢？定义如此，但Traversable的设计者为什么选择了这两个？因为它们很有用，正如@Daniel Wagner的回答所示。其他例子：

instance Traversable [] where
    traverse f = List.foldr cons_f (pure [])
      where cons_f x ys = liftA2 (:) (f x) ys

这个例子使用了foldr函数。

instance Foldable [] where
    elem    = List.elem
    foldl   = List.foldl
    foldl'  = List.foldl'
    foldl1  = List.foldl1
    foldr   = List.foldr
    foldr1  = List.foldr1
    length  = List.length
    maximum = List.maximum
    minimum = List.minimum
    null    = List.null
    product = List.product
    sum     = List.sum
    toList  = id

所以，Traverse是一个Functor和Foldable，所以在需要时可以使用其接口的函数。（例如中的示例只是一个示例，而不是为什么设计者选择使用Functor和Foldable来定义Traversable的正当理由），因为这很有用。

- developer_hatch