haskell - Foldable 类型类是否有限制如何派生可折叠实例的法律？

Question

我正在尝试使用FoldableHaskell 中的类型类，使用以下数据类型作为示例：

data Tree a = Empty
            | Node (Tree a) a (Tree a)

如果我使用DeriveFoldableGHC 扩展，它似乎会派生一个Foldable实例

instance Foldable Tree where
  foldMap _ Empty = mempty
  foldMap f (Node l n r) = (foldMap f l) <> (f n) <> (foldMap f r)

即，树的中序遍历。但是，我没有看到任何明显的阻止不同Foldable实例的东西，例如前序遍历：

instance Foldable Tree where
  foldMap _ Empty = mempty
  foldMap f (Node l n r) = (f n) <> (foldMap f l) <> (foldMap f r)

是否存在Foldable使前序遍历实例非法的类型类的法律？

score 6 · Accepted Answer

Foldable本身在法律上是很差的。基本方法是foldMap。预计其他方法的行为类似于它们的默认定义，直至惰性细节。参数化产生了两个定律：

如果g :: m -> n是幺半群态射并且f :: a -> m是函数，那么
```
g . foldMap f = foldMap (g . f)
```
如果Foldable也是Functor，那么对于所有函数g :: b -> m和f :: a -> b，
```
foldMap (g . f) = foldMap g . fmap f
```

在实践中，大多数Foldable情况也是Traversable. Traversable有更丰富traverse的法律，并强加法律

foldMap f = getConst . traverse (Const . f)

这保证了对于 a Traversable，容器中的每个元素都恰好折叠一次。然而

instance Foldable [] where
  foldMap _ [] = mempty
  foldMap f (x:_:xs) = f x <> f x <> foldMap f xs

将是完全有效的，没有Traversable匹配的合法实例。

score 6 · Accepted Answer

Foldable没有规律指导遍历顺序。实际上，我们可以将编写Foldable实例的行为视为选择特定的遍历顺序。如果DeriveFoldable使用，则选择遵循类型定义中的字段顺序（另请参见Daniel Wagner 的回答）；详细信息记录在GHC 用户指南的相关部分。

（旁注：正如dfeuer 的回答中所讨论的，Traversable有更丰富的法律，除其他外，限制了可接受的实现范围。不过，为了您给出的合法实现，中foldMap序和前序遍历。）TreeTraversable

score 5 · Accepted Answer

不，没有规定必须以什么顺序访问字段的法律。按照字段在数据结构定义中出现的顺序（或者至少是用户可见的 API，如果使用模式同义词）访问字段是常规的，但是这只是惯例。

3 回答 3