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?


1 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.