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

Question

我正在尝试 Foldable Haskell 中的 typeclass，以如下数据类型为例:

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

Foldable没有规律指导遍历顺序。其实我们可以想到写一个Foldable的行为例如选择特定的遍历顺序。如果 DeriveFoldable使用时，选择将遵循类型定义中的字段顺序(另见 Daniel Wagner's answer )；详细信息记录在 the relevant section of the GHC User's Guide .

(旁注:正如 dfeuer's answer 中所讨论的，Traversable 具有更丰富的法律，其中包括限制可接受的 foldMap 实现的范围。不过，Tree 的中序和前序遍历都给出了合法的实现Traversable。)