Foldable package:constrained-categories

The Foldable class represents data structures that can be reduced to a summary value one element at a time. Strict left-associative folds are a good fit for space-efficient reduction, while lazy right-associative folds are a good fit for corecursive iteration, or for folds that short-circuit after processing an initial subsequence of the structure's elements. Instances can be derived automatically by enabling the DeriveFoldable extension. For example, a derived instance for a binary tree might be:

{-# LANGUAGE DeriveFoldable #-}
data Tree a = Empty
| Leaf a
| Node (Tree a) a (Tree a)
deriving Foldable

A more detailed description can be found in the Overview section of Data.Foldable#overview. For the class laws see the Laws section of Data.Foldable#laws.

Foldable class, generalised to use arrows in categories other than ->. This changes the interface somewhat – in particular, foldr relies on currying and hence can't really be expressed in a category without exponential objects; however the monoidal folds come out quite nicely. (Of course, it's debatable how much sense the Hask-Monoid class even makes in other categories.) Unlike with the Functor classes, there is no derived instance Foldable f => Foldable f (->) (->): in this case, it would prevent some genarality. See below for how to define such an instance manually.