Portability | non-portable |
---|---|

Stability | experimental |

Maintainer | generics@haskell.org |

Summary: Generic functions that crush a container into an iteration over its elements.

Crush is a datatype-generic operation on container types. It is a generalization of folds, but it is not a catamorphism. To understand how crush works, one can think of it as generating a list of all elements and mapping an accumulating function over each one. With this image in mind, it is evident that (unlike a catamorphism) very little information can be determined about the structure of the container.

The EMGM implementation of `crush`

can not inherently know the associativity
of the binary operator. Consequently, associativity is left as an argument,
but there are variants specific to left- and right-associativity for
convenience.

Many standard Haskell datatypes (e.g. `[]`

, `Data.Tree`

) are designed such
that a constructor with more than one argument (i.e. a product structurally
represented by `(:*:)`

) has the element on the left and any recursive points
towards the right. Due to this, the right-associative functions would
typically produce the expected values. See examples in the comments for
`flattenr`

and `firstr`

.

- newtype Crush b a = Crush {}
- data Assoc
- = AssocLeft
- | AssocRight

- crush :: FRep (Crush b) f => Assoc -> (a -> b -> b) -> b -> f a -> b
- crushl :: FRep (Crush b) f => (a -> b -> b) -> b -> f a -> b
- crushr :: FRep (Crush b) f => (a -> b -> b) -> b -> f a -> b
- flatten :: FRep (Crush [a]) f => Assoc -> f a -> [a]
- flattenl :: FRep (Crush [a]) f => f a -> [a]
- flattenr :: FRep (Crush [a]) f => f a -> [a]
- first :: (Monad m, FRep (Crush [a]) f) => Assoc -> f a -> m a
- firstl :: FRep (Crush [a]) f => f a -> Maybe a
- firstr :: FRep (Crush [a]) f => f a -> Maybe a
- and :: FRep (Crush Bool) f => f Bool -> Bool
- or :: FRep (Crush Bool) f => f Bool -> Bool
- any :: FRep (Crush Bool) f => (a -> Bool) -> f a -> Bool
- all :: FRep (Crush Bool) f => (a -> Bool) -> f a -> Bool
- sum :: (Num a, FRep (Crush a) f) => f a -> a
- product :: (Num a, FRep (Crush a) f) => f a -> a
- minimum :: (Rep Compare a, FRep (Crush (Maybe a)) f) => f a -> Maybe a
- maximum :: (Rep Compare a, FRep (Crush (Maybe a)) f) => f a -> Maybe a
- elem :: (Rep Compare a, FRep (Crush Bool) f) => a -> f a -> Bool
- notElem :: (Rep Compare a, FRep (Crush Bool) f) => a -> f a -> Bool

# Crush functions

The type of a generic function that takes an associativity and two arguments of different types and returns a value of the type of the second.

Associativity of the binary operator used for `crush`

AssocLeft | Left-associative |

AssocRight | Right-associative |

crushl :: FRep (Crush b) f => (a -> b -> b) -> b -> f a -> bSource

A left-associative variant of `crush`

.

crushr :: FRep (Crush b) f => (a -> b -> b) -> b -> f a -> bSource

A right-associative variant of `crush`

.

# Left- and right-associative derived functions

The operation of these functions changes depending on the associativity of the binary operator.

flattenl :: FRep (Crush [a]) f => f a -> [a]Source

A left-associative variant of `flatten`

.

Note that, for a list `ls :: [a]`

, `flattenl ls == reverse ls`

.

flattenr :: FRep (Crush [a]) f => f a -> [a]Source

A right-associative variant of `flatten`

.

Note that, for a list `ls :: [a]`

, `flattenr ls == ls`

.

# Other derived functions

The operation of these functions is independent of the associativity of
the binary operator. Many of these functions are generalizations of the
`Prelude`

functions of the same name

and :: FRep (Crush Bool) f => f Bool -> BoolSource

Compute the conjunction of all elements in a container. This is a
generalization of the `Prelude`

function of the same name.

or :: FRep (Crush Bool) f => f Bool -> BoolSource

Compute the disjunction of all elements in a container. This is a
generalization of the `Prelude`

function of the same name.

any :: FRep (Crush Bool) f => (a -> Bool) -> f a -> BoolSource

Determine if any element in a container satisfies the predicate `p`

. This
is a generalization of the `Prelude`

function of the same name.

all :: FRep (Crush Bool) f => (a -> Bool) -> f a -> BoolSource

Determine if all elements in a container satisfy the predicate `p`

. This
is a generalization the `Prelude`

function of the same name.

sum :: (Num a, FRep (Crush a) f) => f a -> aSource

Compute the sum of all elements in a container. This is a generalization of
the `Prelude`

function of the same name.

product :: (Num a, FRep (Crush a) f) => f a -> aSource

Compute the product of all elements in a container. This is a
generalization of the `Prelude`

function of the same name.

minimum :: (Rep Compare a, FRep (Crush (Maybe a)) f) => f a -> Maybe aSource

Determine the minimum element of a container. If the container is empty,
return `Nothing`

. This is a generalization of the `Prelude`

function of the
same name.

maximum :: (Rep Compare a, FRep (Crush (Maybe a)) f) => f a -> Maybe aSource

Determine the maximum element of a container. If the container is empty,
return `Nothing`

. This is a generalization of the `Prelude`

function of the
same name.