Implement 'Foldable' on NonEmpty

Question

Given:

data NonEmpty a = NonEmpty a (Array a)

I completed the following exercise from PureScript by Example:

Write a Foldable instance for NonEmpty. Hint: reuse the Foldable instance for arrays.

instance foldableNonEmpty :: Foldable NonEmpty where
  foldr f acc (NonEmpty a as) = foldr f (f a acc) as
  foldl f acc nonEmpty        = foldr (flip f) acc nonEmpty
  foldMap f (NonEmpty a as)   = f a <> (foldMap f as)

Please critique my implementation. Can I do better?

Answer 1

Yes, you can. Given that foldr is right-associative, your implementation is incorrect. Intuitively, foldr will recurse down a structure until it bottoms out and then will it start accumulating the result by going back up. So, this version would be more appropriate:

foldr f acc (NonEmpty a as) = f a (foldr f acc as)

In fact your version is a correct foldl:

foldl f acc (NonEmpty a as) = foldl f (f acc a) as

I think your version of foldMap is fine given the associativity of the monoidal operation.