emgm-0.4: Extensible and Modular Generics for the Masses

Portabilitynon-portable
Stabilityexperimental
Maintainergenerics@haskell.org

Generics.EMGM.Functions.Crush

Contents

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

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 

Fields

selCrush :: Assoc -> a -> b -> b
 

Instances

data Assoc Source

Associativity of the binary operator used for crush

Constructors

AssocLeft

Left-associative

AssocRight

Right-associative

crushSource

Arguments

:: FRep (Crush b) f 
=> Assoc

Associativity of the binary operator (left or right).

-> (a -> b -> b)

Binary operator on a-elements with an accumulator.

-> b

The initial b-value for the binary operator.

-> f a

Container of a-values.

-> b

The 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 :: (Monad m, FRep (Crush [a]) f) => Assoc -> f a -> m aSource

Extract the first element of a container. fail if the container is empty.

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

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

A left-associative Maybe 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 Maybe 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.