Foldable 类型类是否有限制如何派生 Foldable 实例的法律？

Question

我正在 Haskell 中试验 Foldable 类型类，使用以下数据类型作为示例：

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

如果我使用 DeriveFoldable GHC 扩展，它似乎会根据

派生一个 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

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

Answer 2

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)

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

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

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

Answer 3

Foldable没有规律指导遍历顺序。实际上，我们可以将编写 Foldable 实例的行为视为选择特定的遍历顺序。如果使用 DeriveFoldable，则选择将遵循类型定义中字段的顺序（另请参见 ); the details are documented in the relevant section of the GHC User's Guide。

（旁注：正如中所讨论的，Traversable 有更丰富的法律，除其他外，限制了可接受的 foldMap 实现的范围。仍然，顺序和预序Tree 的遍历给出了 Traversable 的合法实现。）

Foldable 类型类是否有限制如何派生 Foldable 实例的法律？

Are there laws for the Foldable typeclass that constrain how Foldable instances can be derived?

haskell

deriving

foldable