Foldable for Tree type, "value of instance is undefined here, so this reference is not allowed"

Question

After defining the following simple tree structure

data Tree a = Leaf | Branch (Tree a) a (Tree a)

I tried defining a Foldable instance for it, only defining foldMap and using the foldrDefault and foldlDefault functions:

instance treeFoldableInstance :: Foldable Tree where
  foldr = foldrDefault
  foldl = foldlDefault
  foldMap f Leaf = mempty
  foldMap f (Branch left a right) = foldMap f left <> (f a) <> foldMap f right

This, however, results in:

The value of treeFoldableInstance is undefined here, so this reference is not allowed.

When I define foldl and foldr explicitly, it compiles. The documentation for this error tells me about laziness, but how does that apply here?

Answer 1

This occurs due to the use of foldlDefault and foldrDefault requiring the very dictionary you are trying to construct, and since PureScript is strictly evaluated, that isn't possible.

Probably the easiest fix here is to try something like:

instance treeFoldableInstance :: Foldable Tree where
  foldr f = foldrDefault f
  foldl f = foldlDefault f
  foldMap f Leaf = mempty
  foldMap f (Branch left a right) = foldMap f left <> (f a) <> foldMap f right

By eta-expanding the foldr and foldl definitions, it delays the self reference, as the desugared code becomes something like:

foldr = \f -> foldrDefault treeFoldableInstance f

So the reference to treeFoldableInstance is only evaluated after f is passed in, rather than during the declaration of treeFoldableInstance.