为什么这个实现是可折叠类型类的一个坏实例？

Question

我正在阅读精彩的Haskell Book。在 Traversable 一章（21）的最后，我需要为以下 Tree 编写一个实例：

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

这是我的解决方案的完整代码的链接。练习建议尝试同时实现foldMap和foldr。这就是我的实现方式foldr（没有考虑调用顺序）：

foldr _ z Empty = z
foldr f z (Leaf x) = f x z
foldr f z (Node left x right) = 
  f x $ foldr f (foldr f z left) right

然后我实现foldMap如下：

foldMap f Empty = mempty
foldMap f (Leaf x) = f x
foldMap f (Node left x right) = 
  foldMap f left <> f x <> foldMap f right

当我运行 QuickCheck 的foldable测试批次时，我遇到了一些失败。将我的foldr实现更改为以下内容会使所有测试都通过：

foldr _ z Empty = z
foldr f z (Leaf x) = f x z
foldr f z (Node left x right) = 
  foldr f (f x (foldr f z right)) left

我尝试自己运行失败的测试用例，但无法重现失败：

*Ch21_12_ExercisesTree Data.Monoid> tree = Node (Node (Leaf (-5)) 3 (Node (Leaf 3) 5 Empty)) (-2) Empty
*Ch21_12_ExercisesTree Data.Monoid> foldr (<>) (mempty :: Sum Int) t
Sum {getSum = 4}
*Ch21_12_ExercisesTree Data.Monoid> foldMap Sum t
Sum {getSum = 4}

我怀疑有一些我没有弄清楚foldQuickCheck 正在使用的ing 函数。

问题：

1. 为什么会出现故障？
2. 有没有办法通过QuickCheck获取测试中使用的功能？

Answer 1

我刚刚意识到我使用了可交换的 Monoid ...我能够使用非可交换的 Monoid 重新创建失败：

> ftree = fmap (First . Just) tree
> foldr (<>) mempty ft
First {getFirst = Just (-2)}
> foldMap (First . Just) ft
First {getFirst = Just (First {getFirst = Just (-5)})}

这可能是一个简单的案例。我想在具有实际数据类型的生产代码中，这可能会复杂得多。