Why is this implementation a bad instance of the Foldable Typeclass?

Question

I'm working through the wonderful Haskell Book. At the end of the Traversable chapter (21), I need to write an instance for the following Tree:

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

Here is a link to the full code of my solution. The exercises recommends trying to implement both foldMap and foldr. This is how I implemented foldr (without putting much thought into the invocation order):

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

I then implemented foldMap as follows:

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

When I run QuickCheck's foldable test batch, I get some failures. Changing my foldr implementation to the following makes all the tests pass:

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

I tried running the failing test case on my own, but couldn't recreate the failure:

*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}

I suspect there's something I'm not figuring out about the folding function that QuickCheck is using.

Questions:

1. Why are failures occurring?
2. Is there a way to get the function used in the test by QuickCheck?

Answer 1

I just realized that I used a commutative Monoid ... I was able to recreate the failure using a non-commutative Monoid:

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

This is probably a simple case. I'd imagine that in production code with real data types this could be much more complicated.

Answer 2

As you already deduced, the reason you're getting failures is because the two implementations are distinguishable, which you can observe by using a non-commutative monoid.

---

Getting the function used by quickcheck is a not so simple. See, for example, this question/answer about Showing functions generated by quickcheck for a little more info.

The way to get Showable functions out of QuickCheck is to wrap the function in the Fun type. That said, the code you're calling (found here) just uses functions directly, so they can never be shown. One option you could try is to create your own version of the foldable function where you use the type Fun a b in place of a -> b and applyFun as necessary to apply the functions.

Answer 3

foldr can be obtained from foldMap by using the Endo monoid, with the a -> b -> b function turning a values into b -> b functions that can be (monoidally) composed. That being so, if your foldMap is...

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

... the corresponding foldr must be:

foldr f z Empty = id z  -- mempty amounts to id
foldr f z (Leaf x) = (f x) z
foldr f z (Node left x right) = 
  ((\e -> foldr f e left) . f x . (\e -> foldr f e right)) z  -- (<>) amounts to (.)

If we tidy that up a little...

foldr f 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)

... we get the correct definition of foldr as written in your question. As the difference between the implementations has to do with the order of composition, trying out a non-commutative monoid readily leads to a failing case, as you have found out.

On the QuickCheck subquestion, I defer to DDub's answer..