haskpy.typeclasses.foldable.Foldable

Foldable

class Foldable

Bases: Type

Foldable typeclass

Strictly minimal complete definition:

• fold_map or foldl or foldr

Recommended minimal complete definition:

• foldl

• foldr

• to_iter

• length

If default implementation is used for any of those, a performance warning is raised.

It is very strongly recommended to implement both foldl and foldr because the default implementations won’t scale up in Python. Also, to_iter is strongly recommended as many other methods rely on that and the default implementation is slow.

Note that foldl and foldr are sequential, but fold_map could be parallelized because it uses monoids. Thus, if parallelized implementation is needed, then also fold_map should be implemented.

The default implementations are defined in circular fashion so that only one of fold_map, foldl and foldr is strictly needed: fold_map uses foldl, which uses foldr, which uses fold_map. But as said, instance implementations of at least both foldl and foldr are strongly recommended.

Examples

In Haskell, Data.Set is Foldable, but not a Functor

__contains__(x)

Override elem if you want to change the default implementation

__iter__()

Override to_iter if you want to change the default implementation

__len__()

Override length if you want to change the default implementation

elem(x)

t a -> a -> bool

fold(monoid)

fold2(monoid)

fold_map(monoid, f)

Monoid m => t a -> (a -> m) -> m (ignoring monoid argument)

The default implementation is based on foldl (or, if not implemented, recursively on foldr). Thus, all possibilities for parallelism is lost.

monoid is the monoidic class of the values inside the foldable. It is only used to determine the identity value.

foldl(combine, initial)

t a -> (b -> a -> b) -> b -> b

The default implementation is based on foldr (or, if not implemented, recursively on fold_map). Either way, the default implementation doesn’t scale up well, so an instance implementation is strongly recommended.

Intuition:

• equivalent to for-loop on lists

• never works on infinite lists (so not possible to implement map in terms of foldl)

References

Tony Morris - An Intuition for List Folds

foldr(combine, initial)

t a -> (a -> b -> b) -> b -> b

Warning

The default is very poor in Python. It is strongly recommended to provide an instance implementation for this.

The default implementation uses fold_map by utilizing (endo)function monoid:

empty :: b -> b

append :: (b -> b) -> (b -> b) -> (b -> b)

One can see combine function as a transformation to this monoid:

combine :: a -> (b -> b)

Then, just use endofunction monoid to compose all those b -> b endofunctions into a single endofunction b -> b. Finally, apply this function to the initial value.

Intuition:

• performs constructor replacement

• may work on infinite lists

• doesn’t “calculate from the right” but associates to the right (otherwise it couldn’t work on infinite lists)

References

Tony Morris - An Intuition for List Folds

head(default)

Return head (or default if no head): f a -> a -> a

length()

t a -> int

The default implementation isn’t very efficient as it traverses through the iterator.

null()

t a -> bool

sum()

t a -> number

to_iter()

t a -> Iter a

Instead of to_list (as in Haskell), let’s provide to_iter. With iterables, we can write efficient implementations for many other methods (e.g., sum, elem) even for large or sometimes infinite foldables.

The default implementation isn’t very efficient as it uses folding to construct the iterator.