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.