directed-foldable

I was motivated to write this library by a discussion on whether foldl should be replaced by foldlStrict or rather foldl' from Data.List.

My hope was that by having separate left to right and right to left folds and by default only allow folds which are efficient, it would be impossible to accidentally use foldl and create a space leak.

Instead of having one giant Foldable class, this package splits it with the following rationale:

• ForwardFoldable(foldr) allows efficient forward folding (e.g. lists)
• BackwardFoldable(foldl) allows efficient backward folding (not lists, e.g. Seq)
• Foldable(fold, foldMap) allows efficient folding in any direction

By only adding instance ForwardFoldable [], you can not accidentally write foldl (+) 0 [0..1000], but are forced to use foldlStrict (+) 0 [0..1000].

I went ahead and created this library based on ghc's implementation of Foldable, Foldable1, and Traversable.

Creating a new instance

Ideally you would only need to implement ForwardFoldable or BackwardFoldable and derive Foldable. In practice, you need to use the predefined functions to express foldMap using foldr or foldl.

data F a
instance ForwardFoldable F where
    foldr f z = _ -- todo
instance Foldable F where
    foldMap = forwardFoldMap
    foldMapStrict = forwardFoldMapStrict

Could not deduce BackwardFoldable []

Do you mean to use lazy foldl on lists? Consider foldlStrict.

In case you want to do folds in opposite direction of the structure's preferred direction, there is a wrapper Inefficient foldable a for you. This is intended as opt out of the runtime guarantees.

If you want to get the last element of a non-empty list, which is obviously not possible in O(1), you can use

l = last (Inefficient (1 :| [0..1000]))

Notes

I dislike using apostrophe ' to denote strict and use the Strict suffix instead. I will revisit this decision when my haskell-language-server powered editor allows renaming variables made up of non letters. Here an ' inside a code block: '