Prelude.Compat

Right to left function composition.

prop> (f . g) x = f (g x)

prop> f . id = f = id . f

Examples

>>> map ((*2) . length) [[], [0, 1, 2], [0]][0,6,2]

>>> foldr (.) id [(+1), (*3), (^3)] 225

>>> let (...) = (.).(.) in ((*2)...(+)) 5 1030

When a value is bound in do-notation, the pattern on the left hand side of <- might not match. In this case, this class provides a function to recover.

A Monad without a MonadFail instance may only be used in conjunction with pattern that always match, such as newtypes, tuples, data types with only a single data constructor, and irrefutable patterns (~pat).

Instances of MonadFail should satisfy the following law: fail s should be a left zero for >>=,

fail s >>= f  =  fail s

If your Monad is also MonadPlus, a popular definition is

fail _ = mzero

fail s should be an action that runs in the monad itself, not an exception (except in instances of MonadIO). In particular, fail should not be implemented in terms of error.

Basic numeric class.

The Haskell Report defines no laws for Num. However, (+) and (*) are customarily expected to define a ring and have the following properties:

Associativity of (+)

(x + y) + z

=

x + (y + z)

Commutativity of (+)

x + y

=

y + x

fromInteger 0 is the additive identity

x + fromInteger 0

=

x

negate gives the additive inverse

x + negate x

=

fromInteger 0

Associativity of (*)

(x * y) * z

=

x * (y * z)

fromInteger 1 is the multiplicative identity

x * fromInteger 1

=

x

and

fromInteger 1 * x

=

x

Distributivity of (*) with respect to (+)

a * (b + c)

=

(a * b) + (a * c)

and

(b + c) * a

=

(b * a) + (c * a)

Coherence with toInteger

if the type also implements

GHC.Real.Integral

, then

fromInteger

is a left inverse for

toInteger

, i.e.

fromInteger (toInteger i) == i

Note that it isn't customarily expected that a type instance of both Num and Ord implement an ordered ring. Indeed, in base only Integer and Rational do.

\mathcal{O}(n). map f xs is the list obtained by applying f to each element of xs, i.e.,

map f [x1, x2, ..., xn] == [f x1, f x2, ..., f xn]
map f [x1, x2, ...] == [f x1, f x2, ...]

this means that map id == id

Examples

>>> map (+1) [1, 2, 3][2,3,4]

>>> map id [1, 2, 3][1,2,3]

>>> map (\n -> 3 * n + 1) [1, 2, 3][4,7,10]

\mathcal{O}(n). scanl is similar to foldl, but returns a list of successive reduced values from the left:

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

Note that

last (scanl f z xs) == foldl f z xs

Examples

>>> scanl (+) 0 [1..4][0,1,3,6,10]

>>> scanl (+) 42 [][42]

>>> scanl (-) 100 [1..4][100,99,97,94,90]

>>> scanl (\reversedString nextChar -> nextChar : reversedString) "foo" ['a', 'b', 'c', 'd']["foo","afoo","bafoo","cbafoo","dcbafoo"]

>>> take 10 (scanl (+) 0 [1..])[0,1,3,6,10,15,21,28,36,45]

>>> take 1 (scanl undefined 'a' undefined)"a"

\mathcal{O}(n). scanr is the right-to-left dual of scanl. Note that the order of parameters on the accumulating function are reversed compared to scanl. Also note that

head (scanr f z xs) == foldr f z xs.

Examples

>>> scanr (+) 0 [1..4][10,9,7,4,0]

>>> scanr (+) 42 [][42]

>>> scanr (-) 100 [1..4][98,-97,99,-96,100]

>>> scanr (\nextChar reversedString -> nextChar : reversedString) "foo" ['a', 'b', 'c', 'd']["abcdfoo","bcdfoo","cdfoo","dfoo","foo"]

>>> force $ scanr (+) 0 [1..]*** Exception: stack overflow

\mathcal{O}(n). scanl1 is a variant of scanl that has no starting value argument:

scanl1 f [x1, x2, ...] == [x1, x1 `f` x2, ...]

Examples

>>> scanl1 (+) [1..4][1,3,6,10]

>>> scanl1 (+) [][]

>>> scanl1 (-) [1..4][1,-1,-4,-8]

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

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

>>> take 10 (scanl1 (+) [1..])[1,3,6,10,15,21,28,36,45,55]

>>> take 1 (scanl1 undefined ('a' : undefined))"a"

\mathcal{O}(n). scanr1 is a variant of scanr that has no starting value argument.

Examples

>>> scanr1 (+) [1..4][10,9,7,4]

>>> scanr1 (+) [][]

>>> scanr1 (-) [1..4][-2,3,-1,4]

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

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

>>> force $ scanr1 (+) [1..]*** Exception: stack overflow

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.

\mathcal{O}(1). Extract the first element of a list, which must be non-empty.

To disable the warning about partiality put {-# OPTIONS_GHC -Wno-x-partial -Wno-unrecognised-warning-flags #-} at the top of the file. To disable it throughout a package put the same options into ghc-options section of Cabal file. To disable it in GHCi put :set -Wno-x-partial -Wno-unrecognised-warning-flags into ~/.ghci config file. See also the migration guide.

Examples

>>> head [1, 2, 3]1

>>> head [1..]1

>>> head []*** Exception: Prelude.head: empty list

\mathcal{O}(1). Extract the elements after the head of a list, which must be non-empty.

To disable the warning about partiality put {-# OPTIONS_GHC -Wno-x-partial -Wno-unrecognised-warning-flags #-} at the top of the file. To disable it throughout a package put the same options into ghc-options section of Cabal file. To disable it in GHCi put :set -Wno-x-partial -Wno-unrecognised-warning-flags into ~/.ghci config file. See also the migration guide.

Examples

>>> tail [1, 2, 3][2,3]

>>> tail [1][]

>>> tail []*** Exception: Prelude.tail: empty list

\mathcal{O}(n). Extract the last element of a list, which must be finite and non-empty.

WARNING: This function is partial. Consider using unsnoc instead.

Examples

>>> last [1, 2, 3]3

>>> last [1..]* Hangs forever *

>>> last []*** Exception: Prelude.last: empty list

\mathcal{O}(n). Return all the elements of a list except the last one. The list must be non-empty.

WARNING: This function is partial. Consider using unsnoc instead.

Examples

>>> init [1, 2, 3][1,2]

>>> init [1][]

>>> init []*** Exception: Prelude.init: empty list

\mathcal{O}(n). reverse xs returns the elements of xs in reverse order. xs must be finite.

Laziness

reverse is lazy in its elements.

>>> head (reverse [undefined, 1])1

>>> reverse (1 : 2 : undefined)*** Exception: Prelude.undefined

Examples

>>> reverse [][]

>>> reverse [42][42]

>>> reverse [2,5,7][7,5,2]

>>> reverse [1..]* Hangs forever *

iterate f x returns an infinite list of repeated applications of f to x:

iterate f x == [x, f x, f (f x), ...]

Laziness

Note that iterate is lazy, potentially leading to thunk build-up if the consumer doesn't force each iterate. See iterate' for a strict variant of this function.

>>> take 1 $ iterate undefined 42[42]

Examples

>>> take 10 $ iterate not True[True,False,True,False,True,False,True,False,True,False]

>>> take 10 $ iterate (+3) 42[42,45,48,51,54,57,60,63,66,69]

iterate id == repeat:

>>> take 10 $ iterate id 1[1,1,1,1,1,1,1,1,1,1]

repeat x is an infinite list, with x the value of every element.

Examples

>>> take 10 $ repeat 17[17,17,17,17,17,17,17,17,17, 17]

>>> repeat undefined[*** Exception: Prelude.undefined

cycle ties a finite list into a circular one, or equivalently, the infinite repetition of the original list. It is the identity on infinite lists.

Examples

>>> cycle []*** Exception: Prelude.cycle: empty list

>>> take 10 (cycle [42])[42,42,42,42,42,42,42,42,42,42]

>>> take 10 (cycle [2, 5, 7])[2,5,7,2,5,7,2,5,7,2]

>>> take 1 (cycle (42 : undefined))[42]

take n, applied to a list xs, returns the prefix of xs of length n, or xs itself if n >= length xs.

It is an instance of the more general genericTake, in which n may be of any integral type.

Laziness

>>> take 0 undefined[]>>> take 2 (1 : 2 : undefined)[1,2]

Examples

>>> take 5 "Hello World!""Hello"

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

>>> take 3 [1,2][1,2]

>>> take 3 [][]

>>> take (-1) [1,2][]

>>> take 0 [1,2][]

drop n xs returns the suffix of xs after the first n elements, or [] if n >= length xs.

It is an instance of the more general genericDrop, in which n may be of any integral type.

Examples

>>> drop 6 "Hello World!""World!"

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

>>> drop 3 [1,2][]

>>> drop 3 [][]

>>> drop (-1) [1,2][1,2]

>>> drop 0 [1,2][1,2]

splitAt n xs returns a tuple where first element is xs prefix of length n and second element is the remainder of the list:

splitAt is an instance of the more general genericSplitAt, in which n may be of any integral type.

Laziness

It is equivalent to (take n xs, drop n xs) unless n is _|_: splitAt _|_ xs = _|_, not (_|_, _|_)).

The first component of the tuple is produced lazily:

>>> fst (splitAt 0 undefined)[]

>>> take 1 (fst (splitAt 10 (1 : undefined)))[1]

Examples

>>> splitAt 6 "Hello World!"("Hello ","World!")

>>> splitAt 3 [1,2,3,4,5]([1,2,3],[4,5])

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

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

>>> splitAt 4 [1,2,3]([1,2,3],[])

>>> splitAt 0 [1,2,3]([],[1,2,3])

>>> splitAt (-1) [1,2,3]([],[1,2,3])

takeWhile, applied to a predicate p and a list xs, returns the longest prefix (possibly empty) of xs of elements that satisfy p.

Laziness

>>> takeWhile (const False) undefined*** Exception: Prelude.undefined

>>> takeWhile (const False) (undefined : undefined)[]

>>> take 1 (takeWhile (const True) (1 : undefined))[1]

Examples

>>> takeWhile (< 3) [1,2,3,4,1,2,3,4][1,2]

>>> takeWhile (< 9) [1,2,3][1,2,3]

>>> takeWhile (< 0) [1,2,3][]

dropWhile p xs returns the suffix remaining after takeWhile p xs.

Examples

>>> dropWhile (< 3) [1,2,3,4,5,1,2,3][3,4,5,1,2,3]

>>> dropWhile (< 9) [1,2,3][]

>>> dropWhile (< 0) [1,2,3][1,2,3]

span, applied to a predicate p and a list xs, returns a tuple where first element is the longest prefix (possibly empty) of xs of elements that satisfy p and second element is the remainder of the list:

span p xs is equivalent to (takeWhile p xs, dropWhile p xs), even if p is _|_.

Laziness

>>> span undefined []([],[])>>> fst (span (const False) undefined)*** Exception: Prelude.undefined>>> fst (span (const False) (undefined : undefined))[]>>> take 1 (fst (span (const True) (1 : undefined)))[1]

span produces the first component of the tuple lazily:

>>> take 10 (fst (span (const True) [1..]))[1,2,3,4,5,6,7,8,9,10]

Examples

>>> span (< 3) [1,2,3,4,1,2,3,4]([1,2],[3,4,1,2,3,4])

>>> span (< 9) [1,2,3]([1,2,3],[])

>>> span (< 0) [1,2,3]([],[1,2,3])

break, applied to a predicate p and a list xs, returns a tuple where first element is longest prefix (possibly empty) of xs of elements that do not satisfy p and second element is the remainder of the list:

break p is equivalent to span (not . p) and consequently to (takeWhile (not . p) xs, dropWhile (not . p) xs), even if p is _|_.

Laziness

>>> break undefined []([],[])

>>> fst (break (const True) undefined)*** Exception: Prelude.undefined

>>> fst (break (const True) (undefined : undefined))[]

>>> take 1 (fst (break (const False) (1 : undefined)))[1]

break produces the first component of the tuple lazily:

>>> take 10 (fst (break (const False) [1..]))[1,2,3,4,5,6,7,8,9,10]

Examples

>>> break (> 3) [1,2,3,4,1,2,3,4]([1,2,3],[4,1,2,3,4])

>>> break (< 9) [1,2,3]([],[1,2,3])

>>> break (> 9) [1,2,3]([1,2,3],[])

\mathcal{O}(n). filter, applied to a predicate and a list, returns the list of those elements that satisfy the predicate; i.e.,

filter p xs = [ x | x <- xs, p x]

Examples

>>> filter odd [1, 2, 3][1,3]

>>> filter (\l -> length l > 3) ["Hello", ", ", "World", "!"]["Hello","World"]

>>> filter (/= 3) [1, 2, 3, 4, 3, 2, 1][1,2,4,2,1]

List index (subscript) operator, starting from 0. It is an instance of the more general genericIndex, which takes an index of any integral type.

WARNING: This function is partial, and should only be used if you are sure that the indexing will not fail. Otherwise, use !?.

WARNING: This function takes linear time in the index.

Examples

>>> ['a', 'b', 'c'] !! 0'a'

>>> ['a', 'b', 'c'] !! 2'c'

>>> ['a', 'b', 'c'] !! 3*** Exception: Prelude.!!: index too large

>>> ['a', 'b', 'c'] !! (-1)*** Exception: Prelude.!!: negative index

\mathcal{O}(\min(m,n)). zip takes two lists and returns a list of corresponding pairs.

zip is right-lazy:

>>> zip [] undefined[]>>> zip undefined []*** Exception: Prelude.undefined...

zip is capable of list fusion, but it is restricted to its first list argument and its resulting list.

Examples

>>> zip [1, 2, 3] ['a', 'b', 'c'][(1,'a'),(2,'b'),(3,'c')]

If one input list is shorter than the other, excess elements of the longer list are discarded, even if one of the lists is infinite:

>>> zip [1] ['a', 'b'][(1,'a')]

>>> zip [1, 2] ['a'][(1,'a')]

>>> zip [] [1..][]

>>> zip [1..] [][]

\mathcal{O}(\min(m,n)). zipWith generalises zip by zipping with the function given as the first argument, instead of a tupling function.

zipWith (,) xs ys == zip xs ys
zipWith f [x1,x2,x3..] [y1,y2,y3..] == [f x1 y1, f x2 y2, f x3 y3..]

zipWith is right-lazy:

>>> let f = undefined>>> zipWith f [] undefined[]

zipWith is capable of list fusion, but it is restricted to its first list argument and its resulting list.

Examples

zipWith (+) can be applied to two lists to produce the list of corresponding sums:

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

>>> zipWith (++) ["hello ", "foo"] ["world!", "bar"]["hello world!","foobar"]

unzip transforms a list of pairs into a list of first components and a list of second components.

Examples

>>> unzip []([],[])

>>> unzip [(1, 'a'), (2, 'b')]([1,2],"ab")

The class of semigroups (types with an associative binary operation).

Instances should satisfy the following:

Associativity

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

You can alternatively define sconcat instead of (<>), in which case the laws are:

Unit

sconcat (pure x) = x

Multiplication

sconcat (join xss) = sconcat (fmap sconcat xss)

Extract the first component of a pair.

Extract the second component of a pair.

Convert an uncurried function to a curried function.

Examples

>>> curry fst 1 21

uncurry converts a curried function to a function on pairs.

Examples

>>> uncurry (+) (1,2)3

>>> uncurry ($) (show, 1)"1"

>>> map (uncurry max) [(1,2), (3,4), (6,8)][2,4,8]

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)

An infix synonym for fmap.

The name of this operator is an allusion to Prelude.$. Note the similarities between their types:

 ($)  ::              (a -> b) ->   a ->   b
(<$>) :: Functor f => (a -> b) -> f a -> f b

Whereas Prelude.$ is function application, <$> is function application lifted over a Functor.

Examples

Convert from a Maybe Int to a Maybe String using show:

>>> show <$> NothingNothing

>>> show <$> Just 3Just "3"

Convert from an Either Int Int to an Either Int String using show:

>>> show <$> Left 17Left 17

>>> show <$> Right 17Right "17"

Double each element of a list:

>>> (*2) <$> [1,2,3][2,4,6]

Apply even to the second element of a pair:

>>> even <$> (2,2)(2,True)

A type f is a Functor if it provides a function fmap which, given any types a and b lets you apply any function from (a -> b) to turn an f a into an f b, preserving the structure of f. Furthermore f needs to adhere to the following:

Identity

fmap id == id

Composition

fmap (f . g) == fmap f . fmap g

Note, that the second law follows from the free theorem of the type fmap and the first law, so you need only check that the former condition holds. See these articles by School of Haskell or David Luposchainsky for an explanation.