是否有关于可折叠类型类的法律限制可折叠实例的派生方式？

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类型类是否存在使预序遍历实例不合法的法律？

Answer 1

Foldable本身在法律上很差。基本方法是foldMap。预计其他方法的行为与它们的默认定义一样，直到懒惰细节。参数化产生了两条定律：

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

在实践中，大多数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匹配的合法实例。

Answer 2

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

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

Answer 3

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