haskpy.typeclasses.traversable.Traversable

Traversable

class Traversable

Bases: Functor, Foldable

Data structures that can be traversed, accumulating results and effects

Minimal complete definition:

traverse | sequence

__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

__rpow__(f)

Lifting operator ** lifts similarly as <$> in Haskell

f ** x translates to x.map(f) and map(f, x).

Why ** operator?

• It’s not typically used as often as multiplication or addition so less risk of confusion.

• It’s not commutative operator as isn’t lifting either.

• The two operands have very different roles. They are not at the same “level”.

• The right operand is “higher”, that is, it’s inside a structure and the left operand is kind of “raised to the power” of the second operand, where the “power” is the functorial structure.

• The same operand is also used for function composition because function composition is just mapping. Visually the symbol can be seen as chaining two stars similarly as function composition chains two functions.

elem(x)

t a -> a -> bool

flap(x)

Functor f => f (a -> b) -> a - > f b

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.

map(f)

Functor f => f a -> (a -> b) -> f b

null()

t a -> bool

replace(x)

Haskell ($>) operator

sequence(applicative)

Evalute each action in the structure and collect the results

For Traversable t:

Applicative f => t (f a) -> f (t a)

The default implementation is based on traverse.

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.

traverse(applicative, func)

Map each element to an action and collect the results

For Traversable t:

Applicative f => t a -> (a -> f b) -> f (t b)

The default implementation is based on sequence.