BasePrelude

Map over both arguments at the same time.

bimap f g ≡ first f . second g

Examples

>>> bimap toUpper (+1) ('j', 3)('J',4)

>>> bimap toUpper (+1) (Left 'j')Left 'J'

>>> bimap toUpper (+1) (Right 3)Right 4

Map covariantly over the first argument.

first f ≡ bimap f id

Examples

>>> first toUpper ('j', 3)('J',3)

>>> first toUpper (Left 'j')Left 'J'

Map covariantly over the second argument.

second ≡ bimap id

Examples

>>> second (+1) ('j', 3)('j',4)

>>> second (+1) (Right 3)Right 4

Map each element of a structure to an action, evaluate these actions from left to right, and collect the results. For a version that ignores the results see traverse_.

Examples

Basic usage:

In the first two examples we show each evaluated action mapping to the output structure.

>>> traverse Just [1,2,3,4]Just [1,2,3,4]

>>> traverse id [Right 1, Right 2, Right 3, Right 4]Right [1,2,3,4]

In the next examples, we show that Nothing and Left values short circuit the created structure.

>>> traverse (const Nothing) [1,2,3,4]Nothing

>>> traverse (\x -> if odd x then Just x else Nothing)  [1,2,3,4]Nothing

>>> traverse id [Right 1, Right 2, Right 3, Right 4, Left 0]Left 0

Evaluate each action in the structure from left to right, and collect the results. For a version that ignores the results see sequenceA_.

Examples

Basic usage:

For the first two examples we show sequenceA fully evaluating a a structure and collecting the results.

>>> sequenceA [Just 1, Just 2, Just 3]Just [1,2,3]

>>> sequenceA [Right 1, Right 2, Right 3]Right [1,2,3]

The next two example show Nothing and Just will short circuit the resulting structure if present in the input. For more context, check the Traversable instances for Either and Maybe.

>>> sequenceA [Just 1, Just 2, Just 3, Nothing]Nothing

>>> sequenceA [Right 1, Right 2, Right 3, Left 4]Left 4

Map each element of a structure to a monadic action, evaluate these actions from left to right, and collect the results. For a version that ignores the results see Data.Foldable.mapM_.

Examples

mapM is literally a traverse with a type signature restricted to Monad. Its implementation may be more efficient due to additional power of Monad.

Evaluate each monadic action in the structure from left to right, and collect the results. For a version that ignores the results see Data.Foldable.sequence_.

Examples

Basic usage:

The first two examples are instances where the input and and output of sequence are isomorphic.

>>> sequence $ Right [1,2,3,4][Right 1,Right 2,Right 3,Right 4]

>>> sequence $ [Right 1,Right 2,Right 3,Right 4]Right [1,2,3,4]

The following examples demonstrate short circuit behavior for sequence.

>>> sequence $ Left [1,2,3,4]Left [1,2,3,4]

>>> sequence $ [Left 0, Right 1,Right 2,Right 3,Right 4]Left 0

The fromList function constructs the structure l from the given list of Item l

The fromListN function takes the input list's length and potentially uses it to construct the structure l more efficiently compared to fromList. If the given number does not equal to the input list's length the behaviour of fromListN is not specified.

prop> fromListN (length xs) xs == fromList xs

The toList function extracts a list of Item l from the structure l. It should satisfy fromList . toList = id.

the identity morphism

morphism composition

Lift a value into the Structure.

Examples

>>> pure 1 :: Maybe IntJust 1

>>> pure 'z' :: [Char]"z"

>>> pure (pure ":D") :: Maybe [String]Just [":D"]

Sequential application.

A few functors support an implementation of <*> that is more efficient than the default one.

Example

Used in combination with (Data.Functor.<$>), (<*>) can be used to build a record.

>>> data MyState = MyState {arg1 :: Foo, arg2 :: Bar, arg3 :: Baz}

>>> produceFoo :: Applicative f => f Foo>>> produceBar :: Applicative f => f Bar>>> produceBaz :: Applicative f => f Baz

>>> mkState :: Applicative f => f MyState>>> mkState = MyState <$> produceFoo <*> produceBar <*> produceBaz

Lift a binary function to actions.

Some functors support an implementation of liftA2 that is more efficient than the default one. In particular, if fmap is an expensive operation, it is likely better to use liftA2 than to fmap over the structure and then use <*>.

This became a typeclass method in 4.10.0.0. Prior to that, it was a function defined in terms of <*> and fmap.

Example

>>> liftA2 (,) (Just 3) (Just 5)Just (3,5)

>>> liftA2 (+) [1, 2, 3] [4, 5, 6][5,6,7,6,7,8,7,8,9]

Sequence actions, discarding the value of the first argument.

Examples

If used in conjunction with the Applicative instance for Maybe, you can chain Maybe computations, with a possible "early return" in case of Nothing.

>>> Just 2 *> Just 3Just 3

>>> Nothing *> Just 3Nothing

Of course a more interesting use case would be to have effectful computations instead of just returning pure values.

>>> import Data.Char>>> import GHC.Internal.Text.ParserCombinators.ReadP>>> let p = string "my name is " *> munch1 isAlpha <* eof>>> readP_to_S p "my name is Simon"[("Simon","")]

Sequence actions, discarding the value of the second argument.

Lift a function to an arrow.

Split the input between the two argument arrows and combine their output. Note that this is in general not a functor.

The default definition may be overridden with a more efficient version if desired.

Fanout: send the input to both argument arrows and combine their output.

The default definition may be overridden with a more efficient version if desired.

toException should produce a SomeException with no attached ExceptionContext.

Render this exception value in a human-friendly manner.

Default implementation: show.

Sequentially compose two actions, passing any value produced by the first as an argument to the second.

'as >>= bs' can be understood as the do expression

do a <- as
   bs a

An alternative name for this function is 'bind', but some people may refer to it as 'flatMap', which results from it being equivialent to

\x f -> join (fmap f x) :: Monad m => m a -> (a -> m b) -> m b

which can be seen as mapping a value with Monad m => m a -> m (m b) and then 'flattening' m (m b) to m b using join.

Sequentially compose two actions, discarding any value produced by the first, like sequencing operators (such as the semicolon) in imperative languages.

'as >> bs' can be understood as the do expression

do as
   bs

or in terms of (>>=) as

as >>= const bs

Inject a value into the monadic type. This function should not be different from its default implementation as pure. The justification for the existence of this function is merely historic.

Left-associative fold operation for constructor applications.

The type of gfoldl is a headache, but operationally it is a simple generalisation of a list fold.

The default definition for gfoldl is const id, which is suitable for abstract datatypes with no substructures.

Unfolding constructor applications

Obtaining the constructor from a given datum. For proper terms, this is meant to be the top-level constructor. Primitive datatypes are here viewed as potentially infinite sets of values (i.e., constructors).

The outer type constructor of the type

Mediate types and unary type constructors.

In Data instances of the form

    instance (Data a, ...) => Data (T a)

dataCast1 should be defined as gcast1.

The default definition is const Nothing, which is appropriate for instances of other forms.

Mediate types and binary type constructors.

In Data instances of the form

    instance (Data a, Data b, ...) => Data (T a b)

dataCast2 should be defined as gcast2.

The default definition is const Nothing, which is appropriate for instances of other forms.

A generic transformation that maps over the immediate subterms

The default definition instantiates the type constructor c in the type of gfoldl to an identity datatype constructor, using the isomorphism pair as injection and projection.

A generic query with a left-associative binary operator

A generic query with a right-associative binary operator

A generic query that processes the immediate subterms and returns a list of results. The list is given in the same order as originally specified in the declaration of the data constructors.

A generic query that processes one child by index (zero-based)

A generic monadic transformation that maps over the immediate subterms

The default definition instantiates the type constructor c in the type of gfoldl to the monad datatype constructor, defining injection and projection using return and >>=.

Transformation of at least one immediate subterm does not fail

Transformation of one immediate subterm with success

Bitwise "and"

Bitwise "or"

Bitwise "xor"

Reverse all the bits in the argument

shift x i shifts x left by i bits if i is positive, or right by -i bits otherwise. Right shifts perform sign extension on signed number types; i.e. they fill the top bits with 1 if the x is negative and with 0 otherwise.

An instance can define either this unified shift or shiftL and shiftR, depending on which is more convenient for the type in question.

rotate x i rotates x left by i bits if i is positive, or right by -i bits otherwise.

For unbounded types like Integer, rotate is equivalent to shift.

An instance can define either this unified rotate or rotateL and rotateR, depending on which is more convenient for the type in question.

zeroBits is the value with all bits unset.

The following laws ought to hold (for all valid bit indices n):

• clearBit zeroBits n == zeroBits

• setBit   zeroBits n == bit n

• testBit  zeroBits n == False

• popCount zeroBits   == 0

This method uses clearBit (bit 0) 0 as its default implementation (which ought to be equivalent to zeroBits for types which possess a 0th bit).

bit i is a value with the ith bit set and all other bits clear.

Can be implemented using bitDefault if a is also an instance of Num.

See also zeroBits.

x `setBit` i is the same as x .|. bit i

x `clearBit` i is the same as x .&. complement (bit i)

x `complementBit` i is the same as x `xor` bit i

x `testBit` i is the same as x .&. bit n /= 0

In other words it returns True if the bit at offset @n is set.

Can be implemented using testBitDefault if a is also an instance of Num.

Return the number of bits in the type of the argument. The actual value of the argument is ignored. Returns Nothing for types that do not have a fixed bitsize, like Integer.

Return the number of bits in the type of the argument. The actual value of the argument is ignored. The function bitSize is undefined for types that do not have a fixed bitsize, like Integer.

Default implementation based upon bitSizeMaybe provided since 4.12.0.0.

Return True if the argument is a signed type. The actual value of the argument is ignored

Shift the argument left by the specified number of bits (which must be non-negative). Some instances may throw an Overflow exception if given a negative input.

An instance can define either this and shiftR or the unified shift, depending on which is more convenient for the type in question.

Shift the argument left by the specified number of bits. The result is undefined for negative shift amounts and shift amounts greater or equal to the bitSize.

Defaults to shiftL unless defined explicitly by an instance.

Shift the first argument right by the specified number of bits. The result is undefined for negative shift amounts and shift amounts greater or equal to the bitSize. Some instances may throw an Overflow exception if given a negative input.

Right shifts perform sign extension on signed number types; i.e. they fill the top bits with 1 if the x is negative and with 0 otherwise.

An instance can define either this and shiftL or the unified shift, depending on which is more convenient for the type in question.

Shift the first argument right by the specified number of bits, which must be non-negative and smaller than the number of bits in the type.

Right shifts perform sign extension on signed number types; i.e. they fill the top bits with 1 if the x is negative and with 0 otherwise.

Defaults to shiftR unless defined explicitly by an instance.

Rotate the argument left by the specified number of bits (which must be non-negative).

An instance can define either this and rotateR or the unified rotate, depending on which is more convenient for the type in question.

Rotate the argument right by the specified number of bits (which must be non-negative).

An instance can define either this and rotateL or the unified rotate, depending on which is more convenient for the type in question.

Return the number of set bits in the argument. This number is known as the population count or the Hamming weight.

Can be implemented using popCountDefault if a is also an instance of Num.

Given a structure with elements whose type is a Monoid, combine them via the monoid's (<>) operator. This fold is right-associative and lazy in the accumulator. When you need a strict left-associative fold, use foldMap' instead, with id as the map.

Examples

Basic usage:

>>> fold [[1, 2, 3], [4, 5], [6], []][1,2,3,4,5,6]

>>> fold $ Node (Leaf (Sum 1)) (Sum 3) (Leaf (Sum 5))Sum {getSum = 9}

Folds of unbounded structures do not terminate when the monoid's (<>) operator is strict:

>>> fold (repeat Nothing)* Hangs forever *

Lazy corecursive folds of unbounded structures are fine:

>>> take 12 $ fold $ map (\i -> [i..i+2]) [0..][0,1,2,1,2,3,2,3,4,3,4,5]>>> sum $ take 4000000 $ fold $ map (\i -> [i..i+2]) [0..]2666668666666

Map each element of the structure into a monoid, and combine the results with (<>). This fold is right-associative and lazy in the accumulator. For strict left-associative folds consider foldMap' instead.

Examples

Basic usage:

>>> foldMap Sum [1, 3, 5]Sum {getSum = 9}

>>> foldMap Product [1, 3, 5]Product {getProduct = 15}

>>> foldMap (replicate 3) [1, 2, 3][1,1,1,2,2,2,3,3,3]

When a Monoid's (<>) is lazy in its second argument, foldMap can return a result even from an unbounded structure. For example, lazy accumulation enables Data.ByteString.Builder to efficiently serialise large data structures and produce the output incrementally:

>>> import qualified Data.ByteString.Lazy as L>>> import qualified Data.ByteString.Builder as B>>> let bld :: Int -> B.Builder; bld i = B.intDec i <> B.word8 0x20>>> let lbs = B.toLazyByteString $ foldMap bld [0..]>>> L.take 64 lbs"0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24"

A left-associative variant of foldMap that is strict in the accumulator. Use this method for strict reduction when partial results are merged via (<>).

Examples

Define a Monoid over finite bit strings under xor. Use it to strictly compute the xor of a list of Int values.

>>> :set -XGeneralizedNewtypeDeriving>>> import Data.Bits (Bits, FiniteBits, xor, zeroBits)>>> import Data.Foldable (foldMap')>>> import Numeric (showHex)>>> >>> newtype X a = X a deriving (Eq, Bounded, Enum, Bits, FiniteBits)>>> instance Bits a => Semigroup (X a) where X a <> X b = X (a `xor` b)>>> instance Bits a => Monoid    (X a) where mempty     = X zeroBits>>> >>> let bits :: [Int]; bits = [0xcafe, 0xfeed, 0xdeaf, 0xbeef, 0x5411]>>> (\ (X a) -> showString "0x" . showHex a $ "") $ foldMap' X bits"0x42"

Right-associative fold of a structure, lazy in the accumulator.

In the case of lists, foldr, when applied to a binary operator, a starting value (typically the right-identity of the operator), and a list, reduces the list using the binary operator, from right to left:

foldr f z [x1, x2, ..., xn] == x1 `f` (x2 `f` ... (xn `f` z)...)

Note that since the head of the resulting expression is produced by an application of the operator to the first element of the list, given an operator lazy in its right argument, foldr can produce a terminating expression from an unbounded list.

For a general Foldable structure this should be semantically identical to,

foldr f z = foldr f z . toList

Examples

Basic usage:

>>> foldr (||) False [False, True, False]True

>>> foldr (||) False []False

>>> foldr (\c acc -> acc ++ [c]) "foo" ['a', 'b', 'c', 'd']"foodcba"

Infinite structures

⚠️ Applying foldr to infinite structures usually doesn't terminate.

It may still terminate under one of the following conditions:

• the folding function is short-circuiting

• the folding function is lazy on its second argument

Short-circuiting

(||) short-circuits on True values, so the following terminates because there is a True value finitely far from the left side:

>>> foldr (||) False (True : repeat False)True

But the following doesn't terminate:

>>> foldr (||) False (repeat False ++ [True])* Hangs forever *

Laziness in the second argument

Applying foldr to infinite structures terminates when the operator is lazy in its second argument (the initial accumulator is never used in this case, and so could be left undefined, but [] is more clear):

>>> take 5 $ foldr (\i acc -> i : fmap (+3) acc) [] (repeat 1)[1,4,7,10,13]

foldr' is a variant of foldr that performs strict reduction from right to left, i.e. starting with the right-most element. The input structure must be finite, otherwise foldr' runs out of space (diverges).

If you want a strict right fold in constant space, you need a structure that supports faster than O(n) access to the right-most element, such as Seq from the containers package.

This method does not run in constant space for structures such as lists that don't support efficient right-to-left iteration and so require O(n) space to perform right-to-left reduction. Use of this method with such a structure is a hint that the chosen structure may be a poor fit for the task at hand. If the order in which the elements are combined is not important, use foldl' instead.

Left-associative fold of a structure, lazy in the accumulator. This is rarely what you want, but can work well for structures with efficient right-to-left sequencing and an operator that is lazy in its left argument.

In the case of lists, foldl, when applied to a binary operator, a starting value (typically the left-identity of the operator), and a list, reduces the list using the binary operator, from left to right:

foldl f z [x1, x2, ..., xn] == (...((z `f` x1) `f` x2) `f`...) `f` xn

Note that to produce the outermost application of the operator the entire input list must be traversed. Like all left-associative folds, foldl will diverge if given an infinite list.

If you want an efficient strict left-fold, you probably want to use foldl' instead of foldl. The reason for this is that the latter does not force the inner results (e.g. z `f` x1 in the above example) before applying them to the operator (e.g. to (`f` x2)). This results in a thunk chain O(n) elements long, which then must be evaluated from the outside-in.

For a general Foldable structure this should be semantically identical to:

foldl f z = foldl f z . toList

Examples

The first example is a strict fold, which in practice is best performed with foldl'.

>>> foldl (+) 42 [1,2,3,4]52

Though the result below is lazy, the input is reversed before prepending it to the initial accumulator, so corecursion begins only after traversing the entire input string.

>>> foldl (\acc c -> c : acc) "abcd" "efgh""hgfeabcd"

A left fold of a structure that is infinite on the right cannot terminate, even when for any finite input the fold just returns the initial accumulator:

>>> foldl (\a _ -> a) 0 $ repeat 1* Hangs forever *

WARNING: When it comes to lists, you always want to use either foldl' or foldr instead.

Left-associative fold of a structure but with strict application of the operator.

This ensures that each step of the fold is forced to Weak Head Normal Form before being applied, avoiding the collection of thunks that would otherwise occur. This is often what you want to strictly reduce a finite structure to a single strict result (e.g. sum).

For a general Foldable structure this should be semantically identical to,

foldl' f z = foldl' f z . toList

A variant of foldr that has no base case, and thus may only be applied to non-empty structures.

This function is non-total and will raise a runtime exception if the structure happens to be empty.

Examples

Basic usage:

>>> foldr1 (+) [1..4]10

>>> foldr1 (+) []Exception: Prelude.foldr1: empty list

>>> foldr1 (+) Nothing*** Exception: foldr1: empty structure

>>> foldr1 (-) [1..4]-2

>>> foldr1 (&&) [True, False, True, True]False

>>> foldr1 (||) [False, False, True, True]True

>>> foldr1 (+) [1..]* Hangs forever *

A variant of foldl that has no base case, and thus may only be applied to non-empty structures.

This function is non-total and will raise a runtime exception if the structure happens to be empty.

foldl1 f = foldl1 f . toList

Examples

Basic usage:

>>> foldl1 (+) [1..4]10

>>> foldl1 (+) []*** Exception: Prelude.foldl1: empty list