Implement 'Foldable' on NonEmpty 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 &lt;&gt; (foldMap f as)


Please critique my implementation. Can I do better?
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.