Safe Haskell | Safe-Inferred |
---|
- class Foldable t where
- class (Functor t, Foldable t) => Traversable t where
- traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
- sequenceA :: Applicative f => t (f a) -> f (t a)
- mapM :: Monad m => (a -> m b) -> t a -> m (t b)
- sequence :: Monad m => t (m a) -> m (t a)
Documentation
A Foldable
instance for functions, given the input is Finite
, and
a Traversable
instance for functions, given the input is Ord
and
Finite
.
class Foldable t where
Data structures that can be folded.
Minimal complete definition: foldMap
or foldr
.
For example, given a data type
data Tree a = Empty | Leaf a | Node (Tree a) a (Tree a)
a suitable instance would be
instance Foldable Tree where foldMap f Empty = mempty foldMap f (Leaf x) = f x foldMap f (Node l k r) = foldMap f l `mappend` f k `mappend` foldMap f r
This is suitable even for abstract types, as the monoid is assumed
to satisfy the monoid laws. Alternatively, one could define foldr
:
instance Foldable Tree where foldr f z Empty = z foldr f z (Leaf x) = f x z foldr f z (Node l k r) = foldr f (f k (foldr f z r)) l
Combine the elements of a structure using a monoid.
foldMap :: Monoid m => (a -> m) -> t a -> m
Map each element of the structure to a monoid, and combine the results.
foldr :: (a -> b -> b) -> b -> t a -> b
foldr' :: (a -> b -> b) -> b -> t a -> b
Right-associative fold of a structure, but with strict application of the operator.
foldl :: (a -> b -> a) -> a -> t b -> a
foldl' :: (a -> b -> a) -> a -> t b -> a
Left-associative fold of a structure. but with strict application of the operator.
foldl
f z =foldl'
f z .toList
foldr1 :: (a -> a -> a) -> t a -> a
A variant of foldr
that has no base case,
and thus may only be applied to non-empty structures.
foldr1
f =foldr1
f .toList
foldl1 :: (a -> a -> a) -> t a -> a
class (Functor t, Foldable t) => Traversable t where
Functors representing data structures that can be traversed from left to right.
Minimal complete definition: traverse
or sequenceA
.
Instances are similar to Functor
, e.g. given a data type
data Tree a = Empty | Leaf a | Node (Tree a) a (Tree a)
a suitable instance would be
instance Traversable Tree where traverse f Empty = pure Empty traverse f (Leaf x) = Leaf <$> f x traverse f (Node l k r) = Node <$> traverse f l <*> f k <*> traverse f r
This is suitable even for abstract types, as the laws for <*>
imply a form of associativity.
The superclass instances should satisfy the following:
- In the
Functor
instance,fmap
should be equivalent to traversal with the identity applicative functor (fmapDefault
). - In the
Foldable
instance,foldMap
should be equivalent to traversal with a constant applicative functor (foldMapDefault
).
traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
Map each element of a structure to an action, evaluate these actions from left to right, and collect the results.
sequenceA :: Applicative f => t (f a) -> f (t a)
Evaluate each action in the structure from left to right, and collect the results.
mapM :: Monad m => (a -> m b) -> t a -> m (t b)
Map each element of a structure to a monadic action, evaluate these actions from left to right, and collect the results.
sequence :: Monad m => t (m a) -> m (t a)
Evaluate each monadic action in the structure from left to right, and collect the results.
Traversable [] | |
Traversable Maybe | |
(Ord e, Finite e) => Traversable ((->) e) | |
Ix i => Traversable (Array i) | |
Traversable (Map k) |