Rebase.Prelude

Embed a list of values into Cases using the trivial but slow membership test based on elem.

The basic arrow class.

Instances should satisfy the following laws:

• arr id = id

• arr (f >>> g) = arr f >>> arr g

• first (arr f) = arr (first f)

• first (f >>> g) = first f >>> first g

• first f >>> arr fst = arr fst >>> f

• first f >>> arr (id *** g) = arr (id *** g) >>> first f

• first (first f) >>> arr assoc = arr assoc >>> first f

where

assoc ((a,b),c) = (a,(b,c))

The other combinators have sensible default definitions, which may be overridden for efficiency.

A monad supporting atomic memory transactions.

TArray is a transactional array, supporting the usual MArray interface for mutable arrays.

It is conceptually implemented as Array i (TVar e).

TBQueue is an abstract type representing a bounded FIFO channel.

TChan is an abstract type representing an unbounded FIFO channel.

A TMVar is a synchronising variable, used for communication between concurrent threads. It can be thought of as a box, which may be empty or full.

TQueue is an abstract type representing an unbounded FIFO channel.

Shared memory locations that support atomic memory transactions.

Continuation monad. Cont r a is a CPS ("continuation-passing style") computation that produces an intermediate result of type a within a CPS computation whose final result type is r.

The return function simply creates a continuation which passes the value on.

The >>= operator adds the bound function into the continuation chain.

The parameterizable reader monad.

Computations are functions of a shared environment.

The return function ignores the environment, while m >>= k passes the inherited environment to both subcomputations:

image: images/bind-ReaderT.svg

A state monad parameterized by the type s of the state to carry.

The return function leaves the state unchanged, while >>= uses the final state of the first computation as the initial state of the second.

The parameterizable exception monad.

Computations are either exceptions or normal values.

The return function returns a normal value, while >>= exits on the first exception. For a variant that continues after an error and collects all the errors, see Errors.

A writer monad parameterized by the type w of output to accumulate.

The return function produces the output mempty, while m >>= k combines the outputs of the subcomputations using mappend (also known as <>):

image: images/bind-WriterT.svg

Selective applicative functors. You can think of select as a selective function application: when given a value of type Left a, you must apply the given function, but when given a Right b, you may skip the function and associated effects, and simply return the b.

Note that it is not a requirement for selective functors to skip unnecessary effects. It may be counterintuitive, but this makes them more useful. Why? Typically, when executing a selective computation, you would want to skip the effects (saving work); but on the other hand, if your goal is to statically analyse a given selective computation and extract the set of all possible effects (without actually executing them), then you do not want to skip any effects, because that defeats the purpose of static analysis.

The type signature of select is reminiscent of both <*> and >>=, and indeed a selective functor is in some sense a composition of an applicative functor and the Either monad.

Laws:

• Identity:

x <*? pure id = either id id <$> x

• Distributivity; note that y and z have the same type f (a -> b):

pure x <*? (y *> z) = (pure x <*? y) *> (pure x <*? z)

• Associativity:

x <*? (y <*? z) = (f <$> x) <*? (g <$> y) <*? (h <$> z)
  where
    f x = Right <$> x
    g y = a -> bimap (,a) ($a) y
    h z = uncurry z

• Monadic select (for selective functors that are also monads):

select = selectM

There are also a few useful theorems:

• Apply a pure function to the result:

f <$> select x y = select (fmap f <$> x) (fmap f <$> y)

• Apply a pure function to the Left case of the first argument:

select (first f <$> x) y = select x ((. f) <$> y)

• Apply a pure function to the second argument:

select x (f <$> y) = select (first (flip f) <$> x) ((&) <$> y)

• Generalised identity:

x <*? pure y = either y id <$> x

• A selective functor is rigid if it satisfies <*> = apS. The following interchange law holds for rigid selective functors:

x *> (y <*? z) = (x *> y) <*? z

If f is also a Monad, we require that select = selectM, from which one can prove <*> = apS.

A strong lax semi-monoidal endofunctor. This is equivalent to an Applicative without pure.

Laws:

(.) <$> u <.> v <.> w = u <.> (v <.> w)
x <.> (f <$> y) = (. f) <$> x <.> y
f <$> (x <.> y) = (f .) <$> x <.> y

The laws imply that .> and <. really ignore their left and right results, respectively, and really return their right and left results, respectively. Specifically,

(mf <$> m) .> (nf <$> n) = nf <$> (m .> n)
(mf <$> m) <. (nf <$> n) = mf <$> (m <. n)

A space-efficient representation of a Word8 vector, supporting many efficient operations.

A ByteString contains 8-bit bytes, or by using the operations from Data.ByteString.Char8 it can be interpreted as containing 8-bit characters.

An arbitrary-precision number represented using scientific notation.

This type describes the set of all Reals which have a finite decimal expansion.

A scientific number with coefficient c and base10Exponent e corresponds to the Fractional number: fromInteger c * 10 ^^ e

A difference list is an abstraction representing a list that supports \mathcal{O}(1) append and snoc operations, making it useful for replacing frequent applications of ++ such as logging and pretty printing (esp. if those uses of ++ are left-nested).

Selective instance for the standard applicative functor Validation. This is a good example of a non-trivial selective functor which is not a monad.

The Eq class defines equality (==) and inequality (/=). All the basic datatypes exported by the Prelude are instances of Eq, and Eq may be derived for any datatype whose constituents are also instances of Eq.

The Haskell Report defines no laws for Eq. However, instances are encouraged to follow these properties:

Reflexivity

x == x

=

True

Symmetry

x == y

=

y == x

Transitivity

if

x == y && y == z

=

True

, then

x == z

=

True

Extensionality

if

x == y

=

True

and

f

is a function whose return type is an instance of

Eq

, then

f x == f y

=

True

Negation

x /= y

=

not (x == y)

The Foldable class represents data structures that can be reduced to a summary value one element at a time. Strict left-associative folds are a good fit for space-efficient reduction, while lazy right-associative folds are a good fit for corecursive iteration, or for folds that short-circuit after processing an initial subsequence of the structure's elements.

Instances can be derived automatically by enabling the DeriveFoldable extension. For example, a derived instance for a binary tree might be:

{-# LANGUAGE DeriveFoldable #-}
data Tree a = Empty
            | Leaf a
            | Node (Tree a) a (Tree a)
    deriving Foldable

A more detailed description can be found in the Overview section of Data.Foldable#overview.

For the class laws see the Laws section of Data.Foldable#laws.

Laws:

<!> is associative:             (a <!> b) <!> c = a <!> (b <!> c)
<$> left-distributes over <!>:  f <$> (a <!> b) = (f <$> a) <!> (f <$> b)

If extended to an Alternative then <!> should equal <|>.

Ideally, an instance of Alt also satisfies the "left distribution" law of MonadPlus with respect to <.>:

<.> right-distributes over <!>: (a <!> b) <.> c = (a <.> c) <!> (b <.> c)

IO, Either a, ExceptT e m and GHC.Conc.STM instead satisfy the "left catch" law:

pure a <!> b = pure a

Maybe and Identity satisfy both "left distribution" and "left catch".

These variations cannot be stated purely in terms of the dependencies of Alt.

When and if MonadPlus is successfully refactored, this class should also be refactored to remove these instances.

The right distributive law should extend in the cases where the a Bind or Monad is provided to yield variations of the right distributive law:

(m <!> n) >>- f = (m >>- f) <!> (m >>- f)
(m <!> n) >>= f = (m >>= f) <!> (m >>= f)