emgm-0.2: Extensible and Modular Generics for the MassesSource codeContentsIndex
Generics.EMGM.Functions.Crush
Portabilitynon-portable
Stabilityexperimental
Maintainergenerics@haskell.org
Contents
Crush functions
Left- and right-associative derived functions
Other derived functions
Description

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.

Synopsis
newtype Crush b a = Crush {
selCrush :: Assoc -> a -> b -> b
}
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 :: FRep (Crush [a]) f => Assoc -> f a -> Maybe 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
newtype Crush b a Source
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.
Constructors
Crush
selCrush :: Assoc -> a -> b -> b
show/hide Instances
data Assoc Source
Associativity of the binary operator used for crush
Constructors
AssocLeftLeft-associative
AssocRightRight-associative
crushSource
:: FRep (Crush b) f
=> AssocAssociativity of the binary operator (left or right).
-> a -> b -> bBinary operator on a-elements with an accumulator.
-> bThe initial b-value for the binary operator.
-> f aContainer of a-values.
-> bThe result after applying the above operator on all a-values.

Apply a function (a -> b -> b) to each element (a) of a container (f a) and an accumulator value (b) to produce an accumulated result (b).

This is the most general form in which you must specify the associativity. You may prefer to use crushr or crushl.

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.
flatten :: FRep (Crush [a]) f => Assoc -> f a -> [a]Source

Flatten the elements of a container into a list.

This is the most general form in which you must specify the associativity. You may prefer to use flattenr or flattenl.

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.

first :: FRep (Crush [a]) f => Assoc -> f a -> Maybe aSource

Extract the first element of a container. If the container is empty, return Nothing.

This is the most general form in which you must specify the associativity. You may prefer to use firstr or firstl.

firstl :: FRep (Crush [a]) f => f a -> Maybe aSource

A left-associative variant of first.

Note that, for a list ls :: [a], fromJust (firstl ls) == last ls.

firstr :: FRep (Crush [a]) f => f a -> Maybe aSource

A right-associative variant of first.

Note that, for a list ls :: [a], fromJust (firstr ls) == head 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.
elem :: (Rep Compare a, FRep (Crush Bool) f) => a -> f a -> BoolSource
Determine if an element is a member of a container. This is a generalization of the Prelude function of the same name.
notElem :: (Rep Compare a, FRep (Crush Bool) f) => a -> f a -> BoolSource
Determine if an element is not a member of a container. This is a generalization of the Prelude function of the same name.
Produced by Haddock version 2.4.2