Prelude

deepseq: fully evaluates the first argument, before returning the second.

The name deepseq is used to illustrate the relationship to seq: where seq is shallow in the sense that it only evaluates the top level of its argument, deepseq traverses the entire data structure evaluating it completely.

deepseq can be useful for forcing pending exceptions, eradicating space leaks, or forcing lazy I/O to happen. It is also useful in conjunction with parallel Strategies (see the parallel package).

There is no guarantee about the ordering of evaluation. The implementation may evaluate the components of the structure in any order or in parallel. To impose an actual order on evaluation, use pseq from Control.Parallel in the parallel package.

Case analysis for the Either type. If the value is Left a, apply the first function to a; if it is Right b, apply the second function to b.

Examples

We create two values of type Either String Int, one using the Left constructor and another using the Right constructor. Then we apply "either" the length function (if we have a String) or the "times-two" function (if we have an Int):

>>> let s = Left "foo" :: Either String Int>>> let n = Right 3 :: Either String Int>>> either length (*2) s3>>> either length (*2) n6

void value discards or ignores the result of evaluation, such as the return value of an System.IO.IO action.

Examples

Replace the contents of a Maybe Int with unit:

>>> void NothingNothing

>>> void (Just 3)Just ()

Replace the contents of an Either Int Int with unit, resulting in an Either Int ():

>>> void (Left 8675309)Left 8675309

>>> void (Right 8675309)Right ()

Replace every element of a list with unit:

>>> void [1,2,3][(),(),()]

Replace the second element of a pair with unit:

>>> void (1,2)(1,())

Discard the result of an System.IO.IO action:

>>> mapM print [1,2]12[(),()]

>>> void $ mapM print [1,2]12

The associator for Profunctor composition.

This provides an Iso for the lens package that witnesses the isomorphism between Procompose p (Procompose q r) a b and Procompose (Procompose p q) r a b, which arises because Prof is only a bicategory, rather than a strict 2-category.

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

The group function takes a list and returns a list of lists such that the concatenation of the result is equal to the argument. Moreover, each sublist in the result is non-empty, all elements are equal to the first one, and consecutive equal elements of the input end up in the same element of the output list.

group is a special case of groupBy, which allows the programmer to supply their own equality test.

It's often preferable to use Data.List.NonEmpty.group, which provides type-level guarantees of non-emptiness of inner lists. A common idiom to squash repeating elements map head . group is better served by map Data.List.NonEmpty.head . Data.List.NonEmpty.group because it avoids partial functions.

Examples

>>> group "Mississippi"["M","i","ss","i","ss","i","pp","i"]

>>> group [1, 1, 1, 2, 2, 3, 4, 5, 5][[1,1,1],[2,2],[3],[4],[5,5]]

Introduces a recursive binding to the continuation. Due to the use of callCC, calling the continuation will interrupt execution of the current block creating an effect similar to goto/setjmp in C.

Allow asynchronous exceptions to be raised even inside mask, making the operation interruptible (see the discussion of "Interruptible operations" in Control.Exception).

When called outside mask, or inside uninterruptibleMask, this function has no effect.

Laws:

unit . counit ≡ id
counit . unit ≡ id

Unicode General Categories (column 2 of the UnicodeData table) in the order they are listed in the Unicode standard (the Unicode Character Database, in particular).

Examples

Basic usage:

>>> :t OtherLetterOtherLetter :: GeneralCategory

Eq instance:

>>> UppercaseLetter == UppercaseLetterTrue>>> UppercaseLetter == LowercaseLetterFalse

Ord instance:

>>> NonSpacingMark <= MathSymbolTrue

Enum instance:

>>> enumFromTo ModifierLetter SpacingCombiningMark[ModifierLetter,OtherLetter,NonSpacingMark,SpacingCombiningMark]

Text.Read.Read instance:

>>> read "DashPunctuation" :: GeneralCategoryDashPunctuation>>> read "17" :: GeneralCategory*** Exception: Prelude.read: no parse

Show instance:

>>> show EnclosingMark"EnclosingMark"

Bounded instance:

>>> minBound :: GeneralCategoryUppercaseLetter>>> maxBound :: GeneralCategoryNotAssigned

Ix instance:

>>> import GHC.Internal.Data.Ix ( index )>>> index (OtherLetter,Control) FinalQuote12>>> index (OtherLetter,Control) Format*** Exception: Error in array index

A class for categories. Instances should satisfy the laws

Right identity

f . id = f

Left identity

id . f = f

Associativity

f . (g . h) = (f . g) . h

A functor with application, providing operations to

• embed pure expressions (pure), and

• sequence computations and combine their results (<*> and liftA2).

A minimal complete definition must include implementations of pure and of either <*> or liftA2. If it defines both, then they must behave the same as their default definitions:

(<*>) = liftA2 id

liftA2 f x y = f <$> x <*> y

Further, any definition must satisfy the following:

Identity

pure id <*> v = v

Composition

pure (.) <*> u <*> v <*> w = u <*> (v <*> w)

Homomorphism

pure f <*> pure x = pure (f x)

Interchange

u <*> pure y = pure ($ y) <*> u

The other methods have the following default definitions, which may be overridden with equivalent specialized implementations:

• u *> v = (id <$ u) <*> v

• u <* v = liftA2 const u v

As a consequence of these laws, the Functor instance for f will satisfy

• fmap f x = pure f <*> x

It may be useful to note that supposing

forall x y. p (q x y) = f x . g y

it follows from the above that

liftA2 p (liftA2 q u v) = liftA2 f u . liftA2 g v

If f is also a Monad, it should satisfy

• pure = return

• m1 <*> m2 = m1 >>= (\x1 -> m2 >>= (\x2 -> return (x1 x2)))

• (*>) = (>>)

(which implies that pure and <*> satisfy the applicative functor laws).

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.

There are two ways to define a comonad:

I. Provide definitions for extract and extend satisfying these laws:

extend extract      = id
extract . extend f  = f
extend f . extend g = extend (f . extend g)

In this case, you may simply set fmap = liftW.

These laws are directly analogous to the laws for monads and perhaps can be made clearer by viewing them as laws stating that Cokleisli composition must be associative, and has extract for a unit:

f =>= extract   = f
extract =>= f   = f
(f =>= g) =>= h = f =>= (g =>= h)

II. Alternately, you may choose to provide definitions for fmap, extract, and duplicate satisfying these laws:

extract . duplicate      = id
fmap extract . duplicate = id
duplicate . duplicate    = fmap duplicate . duplicate

In this case you may not rely on the ability to define fmap in terms of liftW.

You may of course, choose to define both duplicate and extend. In that case you must also satisfy these laws:

extend f  = fmap f . duplicate
duplicate = extend id
fmap f    = extend (f . extract)

These are the default definitions of extend and duplicate and the definition of liftW respectively.

Chan is an abstract type representing an unbounded FIFO channel.

An MVar (pronounced "em-var") is a synchronising variable, used for communication between concurrent threads. It can be thought of as a box, which may be empty or full.

QSem is a quantity semaphore in which the resource is acquired and released in units of one. It provides guaranteed FIFO ordering for satisfying blocked waitQSem calls.

The pattern

bracket_ waitQSem signalQSem (...)

is safe; it never loses a unit of the resource.

QSemN is a quantity semaphore in which the resource is acquired and released in arbitrary amounts. It provides guaranteed FIFO ordering for satisfying blocked waitQSemN calls.

The pattern

bracket_ (waitQSemN n) (signalQSemN n) (...)

is safe; it never loses any of the resource.

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.

Any type that you wish to throw or catch as an exception must be an instance of the Exception class. The simplest case is a new exception type directly below the root:

data MyException = ThisException | ThatException
    deriving Show

instance Exception MyException

The default method definitions in the Exception class do what we need in this case. You can now throw and catch ThisException and ThatException as exceptions:

*Main> throw ThisException `catch` \e -> putStrLn ("Caught " ++ show (e :: MyException))
Caught ThisException

In more complicated examples, you may wish to define a whole hierarchy of exceptions:

---------------------------------------------------------------------
-- Make the root exception type for all the exceptions in a compiler

data SomeCompilerException = forall e . Exception e => SomeCompilerException e

instance Show SomeCompilerException where
    show (SomeCompilerException e) = show e

instance Exception SomeCompilerException

compilerExceptionToException :: Exception e => e -> SomeException
compilerExceptionToException = toException . SomeCompilerException

compilerExceptionFromException :: Exception e => SomeException -> Maybe e
compilerExceptionFromException x = do
    SomeCompilerException a <- fromException x
    cast a

---------------------------------------------------------------------
-- Make a subhierarchy for exceptions in the frontend of the compiler

data SomeFrontendException = forall e . Exception e => SomeFrontendException e

instance Show SomeFrontendException where
    show (SomeFrontendException e) = show e

instance Exception SomeFrontendException where
    toException = compilerExceptionToException
    fromException = compilerExceptionFromException

frontendExceptionToException :: Exception e => e -> SomeException
frontendExceptionToException = toException . SomeFrontendException

frontendExceptionFromException :: Exception e => SomeException -> Maybe e
frontendExceptionFromException x = do
    SomeFrontendException a <- fromException x
    cast a

---------------------------------------------------------------------
-- Make an exception type for a particular frontend compiler exception

data MismatchedParentheses = MismatchedParentheses
    deriving Show

instance Exception MismatchedParentheses where
    toException   = frontendExceptionToException
    fromException = frontendExceptionFromException

We can now catch a MismatchedParentheses exception as MismatchedParentheses, SomeFrontendException or SomeCompilerException, but not other types, e.g. IOException:

*Main> throw MismatchedParentheses `catch` \e -> putStrLn ("Caught " ++ show (e :: MismatchedParentheses))
Caught MismatchedParentheses
*Main> throw MismatchedParentheses `catch` \e -> putStrLn ("Caught " ++ show (e :: SomeFrontendException))
Caught MismatchedParentheses
*Main> throw MismatchedParentheses `catch` \e -> putStrLn ("Caught " ++ show (e :: SomeCompilerException))
Caught MismatchedParentheses
*Main> throw MismatchedParentheses `catch` \e -> putStrLn ("Caught " ++ show (e :: IOException))
*** Exception: MismatchedParentheses

The Monad class defines the basic operations over a monad, a concept from a branch of mathematics known as category theory. From the perspective of a Haskell programmer, however, it is best to think of a monad as an abstract datatype of actions. Haskell's do expressions provide a convenient syntax for writing monadic expressions.

Instances of Monad should satisfy the following:

Left identity

return a >>= k = k a

Right identity

m >>= return = m

Associativity

m >>= (\x -> k x >>= h) = (m >>= k) >>= h

Furthermore, the Monad and Applicative operations should relate as follows:

• pure = return

• m1 <*> m2 = m1 >>= (\x1 -> m2 >>= (\x2 -> return (x1 x2)))

The above laws imply:

• fmap f xs  =  xs >>= return . f

• (>>) = (*>)

and that pure and (<*>) satisfy the applicative functor laws.

The instances of Monad for GHC.List.List, Maybe and System.IO.IO defined in the Prelude satisfy these laws.

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.

Identity functor and monad. (a non-strict monad)

Examples

>>> fmap (+1) (Identity 0)Identity 1

>>> Identity [1, 2, 3] <> Identity [4, 5, 6]Identity [1,2,3,4,5,6]

>>> do
      x <- Identity 10
      y <- Identity (x + 5)
      pure (x + y)
Identity 25

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

The strict ST monad. The ST monad allows for destructive updates, but is escapable (unlike IO). A computation of type ST s a returns a value of type a, and execute in "thread" s. The s parameter is either

• an uninstantiated type variable (inside invocations of runST), or

• RealWorld (inside invocations of stToIO).

It serves to keep the internal states of different invocations of runST separate from each other and from invocations of stToIO.

The >>= and >> operations are strict in the state (though not in values stored in the state). For example,

runST (writeSTRef _|_ v >>= f) = _|_

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.

The Maybe type encapsulates an optional value. A value of type Maybe a either contains a value of type a (represented as Just a), or it is empty (represented as Nothing). Using Maybe is a good way to deal with errors or exceptional cases without resorting to drastic measures such as error.

The Maybe type is also a monad. It is a simple kind of error monad, where all errors are represented by Nothing. A richer error monad can be built using the Either type.

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.

The Data class comprehends a fundamental primitive gfoldl for folding over constructor applications, say terms. This primitive can be instantiated in several ways to map over the immediate subterms of a term; see the gmap combinators later in this class. Indeed, a generic programmer does not necessarily need to use the ingenious gfoldl primitive but rather the intuitive gmap combinators. The gfoldl primitive is completed by means to query top-level constructors, to turn constructor representations into proper terms, and to list all possible datatype constructors. This completion allows us to serve generic programming scenarios like read, show, equality, term generation.

The combinators gmapT, gmapQ, gmapM, etc are all provided with default definitions in terms of gfoldl, leaving open the opportunity to provide datatype-specific definitions. (The inclusion of the gmap combinators as members of class Data allows the programmer or the compiler to derive specialised, and maybe more efficient code per datatype. Note: gfoldl is more higher-order than the gmap combinators. This is subject to ongoing benchmarking experiments. It might turn out that the gmap combinators will be moved out of the class Data.)

Conceptually, the definition of the gmap combinators in terms of the primitive gfoldl requires the identification of the gfoldl function arguments. Technically, we also need to identify the type constructor c for the construction of the result type from the folded term type.

In the definition of gmapQx combinators, we use phantom type constructors for the c in the type of gfoldl because the result type of a query does not involve the (polymorphic) type of the term argument. In the definition of gmapQl we simply use the plain constant type constructor because gfoldl is left-associative anyway and so it is readily suited to fold a left-associative binary operation over the immediate subterms. In the definition of gmapQr, extra effort is needed. We use a higher-order accumulation trick to mediate between left-associative constructor application vs. right-associative binary operation (e.g., (:)). When the query is meant to compute a value of type r, then the result type within generic folding is r -> r. So the result of folding is a function to which we finally pass the right unit.

With the -XDeriveDataTypeable option, GHC can generate instances of the Data class automatically. For example, given the declaration

data T a b = C1 a b | C2 deriving (Typeable, Data)

GHC will generate an instance that is equivalent to

instance (Data a, Data b) => Data (T a b) where
    gfoldl k z (C1 a b) = z C1 `k` a `k` b
    gfoldl k z C2       = z C2

    gunfold k z c = case constrIndex c of
                        1 -> k (k (z C1))
                        2 -> z C2

    toConstr (C1 _ _) = con_C1
    toConstr C2       = con_C2

    dataTypeOf _ = ty_T

con_C1 = mkConstr ty_T "C1" [] Prefix
con_C2 = mkConstr ty_T "C2" [] Prefix
ty_T   = mkDataType "Module.T" [con_C1, con_C2]

This is suitable for datatypes that are exported transparently.