- haskpy.typeclasses.traversable.Traversable
Traversable¶
- class Traversable[source]¶
-
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 Haskellf ** x
translates tox.map(f)
andmap(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 onfoldr
). 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 onfold_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 offoldl
)
References
- 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 endofunctionb -> 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
- 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)[source]¶
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.