Append two lists, i.e.,

[x1, ..., xm] ++ [y1, ..., yn] == [x1, ..., xm, y1, ..., yn][x1, ..., xm] ++ [y1, ...] == [x1, ..., xm, y1, ...]

If the first list is not finite, the result is the first list.

Extract the first element of a list, which must be non-empty.

Extract the last element of a list, which must be finite and non-empty.

Extract the elements after the head of a list, which must be non-empty.

Return all the elements of a list except the last one. The list must be non-empty.

Decompose a list into its head and tail. If the list is empty, returnsNothing. If the list is non-empty, returnsJust (x, xs), wherex is the head of the list andxs its tail.

Since: 4.8.0.0

Test whether the structure is empty. The default implementation is optimized for structures that are similar to cons-lists, because there is no general way to do better.

Returns the size/length of a finite structure as anInt. The default implementation is optimized for structures that are similar to cons-lists, because there is no general way to do better.

mapf xs is the list obtained by applyingf to each element ofxs, i.e.,

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

reversexs returns the elements ofxs in reverse order.xs must be finite.

Theintersperse function takes an element and a list and `intersperses' that element between the elements of the list. For example,

>>>intersperse ',' "abcde""a,b,c,d,e"

intercalatexs xss is equivalent to(concat (intersperse xs xss)). It inserts the listxs in between the lists inxss and concatenates the result.

>>>intercalate ", " ["Lorem", "ipsum", "dolor"]"Lorem, ipsum, dolor"

Thetranspose function transposes the rows and columns of its argument. For example,

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

If some of the rows are shorter than the following rows, their elements are skipped:

>>>transpose [[10,11],[20],[],[30,31,32]][[10,20,30],[11,31],[32]]

Thesubsequences function returns the list of all subsequences of the argument.

>>>subsequences "abc"["","a","b","ab","c","ac","bc","abc"]

Thepermutations function returns the list of all permutations of the argument.

>>>permutations "abc"["abc","bac","cba","bca","cab","acb"]

Left-associative fold of a structure.

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. This means thatfoldl' will diverge if given an infinite list.

Also note that if you want an efficient left-fold, you probably want to usefoldl' instead offoldl. The reason for this is that latter does not force the "inner" results (e.g.zf x1 in the above example) before applying them to the operator (e.g. to(f x2)). This results in a thunk chainO(n) elements long, which then must be evaluated from the outside-in.

For a generalFoldable structure this should be semantically identical to,

foldl f z =foldl f z .toList

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 list to a single, monolithic result (e.g.length).

For a generalFoldable structure this should be semantically identical to,

foldl f z =foldl' f z .toList

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

foldl1 f =foldl1 f .toList

A strict version offoldl1

Right-associative fold of a structure.

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,foldr can produce a terminating expression from an infinite list.

For a generalFoldable structure this should be semantically identical to,

foldr f z =foldr f z .toList

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

foldr1 f =foldr1 f .toList

The concatenation of all the elements of a container of lists.

Map a function over all the elements of a container and concatenate the resulting lists.

and returns the conjunction of a container of Bools. For the result to beTrue, the container must be finite;False, however, results from aFalse value finitely far from the left end.

or returns the disjunction of a container of Bools. For the result to beFalse, the container must be finite;True, however, results from aTrue value finitely far from the left end.

Determines whether any element of the structure satisfies the predicate.

Determines whether all elements of the structure satisfy the predicate.

Thesum function computes the sum of the numbers of a structure.

Theproduct function computes the product of the numbers of a structure.

The largest element of a non-empty structure.

The least element of a non-empty structure.

scanl is similar tofoldl, 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.

A strictly accumulating version ofscanl

scanl1 is a variant ofscanl that has no starting value argument:

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

scanr is the right-to-left dual ofscanl. Note that

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

scanr1 is a variant ofscanr that has no starting value argument.

ThemapAccumL function behaves like a combination offmap andfoldl; it applies a function to each element of a structure, passing an accumulating parameter from left to right, and returning a final value of this accumulator together with the new structure.

ThemapAccumR function behaves like a combination offmap andfoldr; it applies a function to each element of a structure, passing an accumulating parameter from right to left, and returning a final value of this accumulator together with the new structure.

iteratef x returns an infinite list of repeated applications off tox:

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

Note thatiterate 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.

'iterate\'' is the strict version ofiterate.

It ensures that the result of each application of force to weak head normal form before proceeding.

repeatx is an infinite list, withx the value of every element.

replicaten x is a list of lengthn withx the value of every element. It is an instance of the more generalgenericReplicate, in whichn may be of any integral type.

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.

Theunfoldr function is a `dual' tofoldr: whilefoldr reduces a list to a summary value,unfoldr builds a list from a seed value. The function takes the element and returnsNothing if it is done producing the list or returnsJust(a,b), in which case,a is a prepended to the list andb is used as the next element in a recursive call. For example,

iterate f == unfoldr (\x -> Just (x, f x))

In some cases,unfoldr can undo afoldr operation:

unfoldr f' (foldr f z xs) == xs

if the following holds:

f' (f x y) = Just (x,y)f' z       = Nothing

A simple use of unfoldr:

>>>unfoldr (\b -> if b == 0 then Nothing else Just (b, b-1)) 10[10,9,8,7,6,5,4,3,2,1]

taken, applied to a listxs, returns the prefix ofxs of lengthn, orxs itself ifn >length xs:

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] == []

It is an instance of the more generalgenericTake, in whichn may be of any integral type.

dropn xs returns the suffix ofxs after the firstn elements, or[] ifn >length xs:

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]

It is an instance of the more generalgenericDrop, in whichn may be of any integral type.

splitAtn xs returns a tuple where first element isxs prefix of lengthn and second element is the remainder of the list:

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])

It is equivalent to(take n xs,drop n xs) whenn is not_|_ (splitAt _|_ xs = _|_).splitAt is an instance of the more generalgenericSplitAt, in whichn may be of any integral type.

takeWhile, applied to a predicatep and a listxs, returns the longest prefix (possibly empty) ofxs of elements that satisfyp:

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] == []

dropWhilep xs returns the suffix remaining aftertakeWhilep xs:

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]

ThedropWhileEnd function drops the largest suffix of a list in which the given predicate holds for all elements. For example:

>>>dropWhileEnd isSpace "foo\n""foo"

>>>dropWhileEnd isSpace "foo bar""foo bar"

dropWhileEnd isSpace ("foo\n" ++ undefined) == "foo" ++ undefined

Since: 4.5.0.0

span, applied to a predicatep and a listxs, returns a tuple where first element is longest prefix (possibly empty) ofxs of elements that satisfyp and second element is the remainder of the list:

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])

spanp xs is equivalent to(takeWhile p xs,dropWhile p xs)

break, applied to a predicatep and a listxs, returns a tuple where first element is longest prefix (possibly empty) ofxs of elements thatdo not satisfyp and second element is the remainder of the list:

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],[])

breakp is equivalent tospan (not . p).

ThestripPrefix function drops the given prefix from a list. It returnsNothing if the list did not start with the prefix given, orJust the list after the prefix, if it does.

>>>stripPrefix "foo" "foobar"Just "bar"

>>>stripPrefix "foo" "foo"Just ""

>>>stripPrefix "foo" "barfoo"Nothing

>>>stripPrefix "foo" "barfoobaz"Nothing

Thegroup 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 contains only equal elements. For example,

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

It is a special case ofgroupBy, which allows the programmer to supply their own equality test.

Theinits function returns all initial segments of the argument, shortest first. For example,

>>>inits "abc"["","a","ab","abc"]

Note thatinits has the following strictness property:inits (xs ++ _|_) = inits xs ++ _|_

In particular,inits _|_ = [] : _|_

Thetails function returns all final segments of the argument, longest first. For example,

>>>tails "abc"["abc","bc","c",""]

Note thattails has the following strictness property:tails _|_ = _|_ : _|_

TheisPrefixOf function takes two lists and returnsTrue iff the first list is a prefix of the second.

>>>"Hello" `isPrefixOf` "Hello World!"True

>>>"Hello" `isPrefixOf` "Wello Horld!"False

TheisSuffixOf function takes two lists and returnsTrue iff the first list is a suffix of the second. The second list must be finite.

>>>"ld!" `isSuffixOf` "Hello World!"True

>>>"World" `isSuffixOf` "Hello World!"False

TheisInfixOf function takes two lists and returnsTrue iff the first list is contained, wholly and intact, anywhere within the second.

>>>isInfixOf "Haskell" "I really like Haskell."True

>>>isInfixOf "Ial" "I really like Haskell."False

TheisSubsequenceOf function takes two lists and returnsTrue if all the elements of the first list occur, in order, in the second. The elements do not have to occur consecutively.

isSubsequenceOf x y is equivalent toelem x (subsequences y).

Examples

>>>isSubsequenceOf "GHC" "The Glorious Haskell Compiler"True>>>isSubsequenceOf ['a','d'..'z'] ['a'..'z']True>>>isSubsequenceOf [1..10] [10,9..0]False

Since: 4.8.0.0

Does the element occur in the structure?

notElem is the negation ofelem.

lookupkey assocs looks up a key in an association list.

Thefind function takes a predicate and a structure and returns the leftmost element of the structure matching the predicate, orNothing if there is no such element.

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]

Thepartition function takes a predicate a list and returns the pair of lists of elements which do and do not satisfy the predicate, respectively; i.e.,

partition p xs == (filter p xs, filter (not . p) xs)

>>>partition (`elem` "aeiou") "Hello World!"("eoo","Hll Wrld!")

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

TheelemIndex function returns the index of the first element in the given list which is equal (by==) to the query element, orNothing if there is no such element.

>>>elemIndex 4 [0..]Just 4

TheelemIndices function extendselemIndex, by returning the indices of all elements equal to the query element, in ascending order.

>>>elemIndices 'o' "Hello World"[4,7]

ThefindIndex function takes a predicate and a list and returns the index of the first element in the list satisfying the predicate, orNothing if there is no such element.

>>>findIndex isSpace "Hello World!"Just 5

ThefindIndices function extendsfindIndex, by returning the indices of all elements satisfying the predicate, in ascending order.

>>>findIndices (`elem` "aeiou") "Hello World!"[1,4,7]

zip takes two lists and returns a list of corresponding pairs.

zip [1, 2] ['a', 'b'] = [(1, 'a'), (2, 'b')]

If one input list is short, excess elements of the longer list are discarded:

zip [1] ['a', 'b'] = [(1, 'a')]zip [1, 2] ['a'] = [(1, 'a')]

zip is right-lazy:

zip [] _|_ = []zip _|_ [] = _|_

zip3 takes three lists and returns a list of triples, analogous tozip.

Thezip4 function takes four lists and returns a list of quadruples, analogous tozip.

Thezip5 function takes five lists and returns a list of five-tuples, analogous tozip.

Thezip6 function takes six lists and returns a list of six-tuples, analogous tozip.

Thezip7 function takes seven lists and returns a list of seven-tuples, analogous tozip.

zipWith generaliseszip by zipping with the function given as the first argument, instead of a tupling function. For example,zipWith (+) is applied to two lists to produce the list of corresponding sums.

zipWith is right-lazy:

zipWith f [] _|_ = []

ThezipWith3 function takes a function which combines three elements, as well as three lists and returns a list of their point-wise combination, analogous tozipWith.

ThezipWith4 function takes a function which combines four elements, as well as four lists and returns a list of their point-wise combination, analogous tozipWith.

ThezipWith5 function takes a function which combines five elements, as well as five lists and returns a list of their point-wise combination, analogous tozipWith.

ThezipWith6 function takes a function which combines six elements, as well as six lists and returns a list of their point-wise combination, analogous tozipWith.

ThezipWith7 function takes a function which combines seven elements, as well as seven lists and returns a list of their point-wise combination, analogous tozipWith.

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

Theunzip3 function takes a list of triples and returns three lists, analogous tounzip.

Theunzip4 function takes a list of quadruples and returns four lists, analogous tounzip.

Theunzip5 function takes a list of five-tuples and returns five lists, analogous tounzip.

Theunzip6 function takes a list of six-tuples and returns six lists, analogous tounzip.

Theunzip7 function takes a list of seven-tuples and returns seven lists, analogous tounzip.

lines breaks a string up into a list of strings at newline characters. The resulting strings do not contain newlines.

Note that after splitting the string at newline characters, the last part of the string is considered a line even if it doesn't end with a newline. For example,

>>>lines ""[]

>>>lines "\n"[""]

>>>lines "one"["one"]

>>>lines "one\n"["one"]

>>>lines "one\n\n"["one",""]

>>>lines "one\ntwo"["one","two"]

>>>lines "one\ntwo\n"["one","two"]

Thuslines s contains at least as many elements as newlines ins.

words breaks a string up into a list of words, which were delimited by white space.

>>>words "Lorem ipsum\ndolor"["Lorem","ipsum","dolor"]

unlines is an inverse operation tolines. It joins lines, after appending a terminating newline to each.

>>>unlines ["Hello", "World", "!"]"Hello\nWorld\n!\n"

unwords is an inverse operation towords. It joins words with separating spaces.

>>>unwords ["Lorem", "ipsum", "dolor"]"Lorem ipsum dolor"

O(n^2). Thenub function removes duplicate elements from a list. In particular, it keeps only the first occurrence of each element. (The namenub means `essence'.) It is a special case ofnubBy, which allows the programmer to supply their own equality test.

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

deletex removes the first occurrence ofx from its list argument. For example,

>>>delete 'a' "banana""bnana"

It is a special case ofdeleteBy, which allows the programmer to supply their own equality test.

The\\ function is list difference (non-associative). In the result ofxs\\ys, the first occurrence of each element ofys in turn (if any) has been removed fromxs. Thus

(xs ++ ys) \\ xs == ys.

>>>"Hello World!" \\ "ell W""Hoorld!"

It is a special case ofdeleteFirstsBy, which allows the programmer to supply their own equality test.

Theunion function returns the list union of the two lists. For example,

>>>"dog" `union` "cow""dogcw"

Duplicates, and elements of the first list, are removed from the the second list, but if the first list contains duplicates, so will the result. It is a special case ofunionBy, which allows the programmer to supply their own equality test.

Theintersect function takes the list intersection of two lists. For example,

>>>[1,2,3,4] `intersect` [2,4,6,8][2,4]

If the first list contains duplicates, so will the result.

>>>[1,2,2,3,4] `intersect` [6,4,4,2][2,2,4]

It is a special case ofintersectBy, which allows the programmer to supply their own equality test. If the element is found in both the first and the second list, the element from the first list will be used.

Thesort function implements a stable sorting algorithm. It is a special case ofsortBy, which allows the programmer to supply their own comparison function.

Elements are arranged from from lowest to highest, keeping duplicates in the order they appeared in the input.

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

Sort a list by comparing the results of a key function applied to each element.sortOn f is equivalent tosortBy (comparing f), but has the performance advantage of only evaluatingf once for each element in the input list. This is called the decorate-sort-undecorate paradigm, or Schwartzian transform.

Elements are arranged from from lowest to highest, keeping duplicates in the order they appeared in the input.

>>>sortOn fst [(2, "world"), (4, "!"), (1, "Hello")][(1,"Hello"),(2,"world"),(4,"!")]

Since: 4.8.0.0

Theinsert function takes an element and a list and inserts the element into the list at the first position where it is less than or equal to the next element. In particular, if the list is sorted before the call, the result will also be sorted. It is a special case ofinsertBy, which allows the programmer to supply their own comparison function.

>>>insert 4 [1,2,3,5,6,7][1,2,3,4,5,6,7]

ThenubBy function behaves just likenub, except it uses a user-supplied equality predicate instead of the overloaded== function.

>>>nubBy (\x y -> mod x 3 == mod y 3) [1,2,4,5,6][1,2,6]

ThedeleteBy function behaves likedelete, but takes a user-supplied equality predicate.

>>>deleteBy (<=) 4 [1..10][1,2,3,5,6,7,8,9,10]

ThedeleteFirstsBy function takes a predicate and two lists and returns the first list with the first occurrence of each element of the second list removed.

TheunionBy function is the non-overloaded version ofunion.

TheintersectBy function is the non-overloaded version ofintersect.

ThegroupBy function is the non-overloaded version ofgroup.

ThesortBy function is the non-overloaded version ofsort.

>>>sortBy (\(a,_) (b,_) -> compare a b) [(2, "world"), (4, "!"), (1, "Hello")][(1,"Hello"),(2,"world"),(4,"!")]

The non-overloaded version ofinsert.

The largest element of a non-empty structure with respect to the given comparison function.

The least element of a non-empty structure with respect to the given comparison function.

ThegenericLength function is an overloaded version oflength. In particular, instead of returning anInt, it returns any type which is an instance ofNum. It is, however, less efficient thanlength.

ThegenericTake function is an overloaded version oftake, which accepts anyIntegral value as the number of elements to take.

ThegenericDrop function is an overloaded version ofdrop, which accepts anyIntegral value as the number of elements to drop.

ThegenericSplitAt function is an overloaded version ofsplitAt, which accepts anyIntegral value as the position at which to split.

ThegenericIndex function is an overloaded version of!!, which accepts anyIntegral value as the index.

ThegenericReplicate function is an overloaded version ofreplicate, which accepts anyIntegral value as the number of repetitions to make.