If the first list is not finite, the result is the first list.
Performance considerations
This function takes linear time in the number of elements of the
first list. Thus it is better to associate repeated
applications of (++) to the right (which is the default behaviour):
xs ++ (ys ++ zs) or simply xs ++ ys ++ zs, but not (xs ++ ys) ++ zs.
For the same reason GHC.Internal.Data.List.concat=GHC.Internal.Data.List.foldr(++)[]
has linear performance, while GHC.Internal.Data.List.foldl(++)[] is prone
to quadratic slowdown
Test whether the structure is empty. The default implementation is
Left-associative and lazy in both the initial element and the
accumulator. Thus optimised for structures where the first element can
be accessed in constant time. Structures where this is not the case
should have a non-default implementation.
Examples
Basic usage:
Example1 expression
>>> null []True
Example1 expression
>>> null [1]False
null is expected to terminate even for infinite structures.
The default implementation terminates provided the structure
is bounded on the left (there is a leftmost element).
Returns the size/length of a finite structure as an Int. The
default implementation just counts elements starting with the leftmost.
Instances for structures that can compute the element count faster
than via element-by-element counting, should provide a specialised
implementation.
The permutations function is maximally lazy:
for each n, the value of permutations xs starts with those permutations
that permute take n xs and keep drop n xs.
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:
The first example is a strict fold, which in practice is best performed
with foldl'.
Example1 expression
>>> 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.
Example1 expression
>>> 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:
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,
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,
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):
Example1 expression
>>> take 5 $ foldr (\i acc -> i : fmap (+3) acc) [] (repeat 1)[1,4,7,10,13]
and returns the conjunction of a container of Bools. For the
result to be True, the container must be finite; False, however,
results from a False value finitely far from the left end.
Examples
Basic usage:
Example1 expression
>>> and []True
Example1 expression
>>> and [True]True
Example1 expression
>>> and [False]False
Example1 expression
>>> and [True, True, False]False
Example1 expression
>>> and (False : repeat True) -- Infinite list [False,True,True,True,...False
or returns the disjunction of a container of Bools. For the
result to be False, the container must be finite; True, however,
results from a True value finitely far from the left end.
Examples
Basic usage:
Example1 expression
>>> or []False
Example1 expression
>>> or [True]True
Example1 expression
>>> or [False]False
Example1 expression
>>> or [True, True, False]True
Example1 expression
>>> or (True : repeat False) -- Infinite list [True,False,False,False,...True
\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
The mapAccumL function behaves like a combination of fmap
and foldl; 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.
Examples
Basic usage:
Example1 expression
>>> mapAccumL (\a b -> (a + b, a)) 0 [1..10](55,[0,1,3,6,10,15,21,28,36,45])
Example1 expression
>>> mapAccumL (\a b -> (a <> show b, a)) "0" [1..5]("012345",["0","01","012","0123","01234"])
The mapAccumR function behaves like a combination of fmap
and foldr; 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.
Examples
Basic usage:
Example1 expression
>>> mapAccumR (\a b -> (a + b, a)) 0 [1..10](55,[54,52,49,45,40,34,27,19,10,0])
Example1 expression
>>> mapAccumR (\a b -> (a <> show b, a)) "0" [1..5]("054321",["05432","0543","054","05","0"])
iteratef 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.
Example1 expression
>>> take 1 $ iterate undefined 42[42]
Examples
Example1 expression
>>> take 10 $ iterate not True[True,False,True,False,True,False,True,False,True,False]
Example1 expression
>>> take 10 $ iterate (+3) 42[42,45,48,51,54,57,60,63,66,69]
replicaten x is a list of length n with x the value of
every element.
It is an instance of the more general genericReplicate,
in which n may be of any integral type.
The unfoldr function is a `dual' to foldr: while foldr
reduces a list to a summary value, unfoldr builds a list from
a seed value. The function takes the element and returns Nothing
if it is done producing the list or returns Just(a,b), in which
case, a is a prepended to the list and b 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 a foldr operation:
unfoldr f' (foldr f z xs) == xs
if the following holds:
f' (f x y) = Just (x,y)
f' z = Nothing
Laziness
Example1 expression
>>> take 1 (unfoldr (\x -> Just (x, undefined)) 'a')"a"
Examples
Example1 expression
>>> unfoldr (\b -> if b == 0 then Nothing else Just (b, b-1)) 10[10,9,8,7,6,5,4,3,2,1]
Example1 expression
>>> take 10 $ unfoldr (\(x, y) -> Just (x, (y, x + y))) (0, 1)[0,1,1,2,3,5,8,13,21,54]
The dropWhileEnd function drops the largest suffix of a list
in which the given predicate holds for all elements.
Laziness
This function is lazy in spine, but strict in elements,
which makes it different from reverse.dropWhilep.reverse,
which is strict in spine, but lazy in elements. For instance:
Example1 expression
>>> take 1 (dropWhileEnd (< 0) (1 : undefined))[1]
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:
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 satisfyp and second element is the remainder of the list:
\mathcal{O}(\min(m,n)). The stripPrefix function drops the given
prefix from a list. It returns Nothing if the list did not start with the
prefix given, or Just the list after the prefix, if it does.
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 maphead.group
is better served by
mapData.List.NonEmpty.head.Data.List.NonEmpty.group
because it avoids partial functions.
Examples
Example1 expression
>>> group "Mississippi"["M","i","ss","i","ss","i","pp","i"]
The isSubsequenceOf function takes two lists and returns True if all
the elements of the first list occur, in order, in the second. The
elements do not have to occur consecutively.
For infinite structures, the default implementation of elem
terminates if the sought-after value exists at a finite distance
from the left side of the structure:
The find function takes a predicate and a structure and returns
the leftmost element of the structure matching the predicate, or
Nothing if there is no such element.
The partition function takes a predicate and 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)
The elemIndex function returns the index of the first element
in the given list which is equal (by ==) to the query element,
or Nothing if there is no such element.
For the result to be Nothing, the list must be finite.
The findIndex function takes a predicate and a list and returns
the index of the first element in the list satisfying the predicate,
or Nothing if there is no such element.
For the result to be Nothing, the list must be finite.
zip3 takes three lists and returns a list of triples, analogous to
zip.
It is capable of list fusion, but it is restricted to its
first list argument and its resulting list.
The zip4 function takes four lists and returns a list of
quadruples, analogous to zip.
It is capable of list fusion, but it is restricted to its
first list argument and its resulting list.
The zip5 function takes five lists and returns a list of
five-tuples, analogous to zip.
It is capable of list fusion, but it is restricted to its
first list argument and its resulting list.
The zip6 function takes six lists and returns a list of six-tuples,
analogous to zip.
It is capable of list fusion, but it is restricted to its
first list argument and its resulting list.
The zip7 function takes seven lists and returns a list of
seven-tuples, analogous to zip.
It is capable of list fusion, but it is restricted to its
first list argument and its resulting list.
vvaluezipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
\mathcal{O}(\min(l,m,n)). The zipWith3 function takes a function which combines three
elements, as well as three lists and returns a list of the function applied
to corresponding elements, analogous to zipWith.
It is capable of list fusion, but it is restricted to its
first list argument and its resulting list.
zipWith3 (,,) xs ys zs == zip3 xs ys zs
zipWith3 f [x1,x2,x3..] [y1,y2,y3..] [z1,z2,z3..] == [f x1 y1 z1, f x2 y2 z2, f x3 y3 z3..]
Examples
Example1 expression
>>> zipWith3 (\x y z -> [x, y, z]) "123" "abc" "xyz"["1ax","2by","3cz"]
Example1 expression
>>> zipWith3 (\x y z -> (x * y) + z) [1, 2, 3] [4, 5, 6] [7, 8, 9][11,18,27]
vvaluezipWith4 :: (a -> b -> c -> d -> e) -> [a] -> [b] -> [c] -> [d] -> [e]
The zipWith4 function takes a function which combines four
elements, as well as four lists and returns a list of their point-wise
combination, analogous to zipWith.
It is capable of list fusion, but it is restricted to its
first list argument and its resulting list.
The zipWith5 function takes a function which combines five
elements, as well as five lists and returns a list of their point-wise
combination, analogous to zipWith.
It is capable of list fusion, but it is restricted to its
first list argument and its resulting list.
The zipWith6 function takes a function which combines six
elements, as well as six lists and returns a list of their point-wise
combination, analogous to zipWith.
It is capable of list fusion, but it is restricted to its
first list argument and its resulting list.
The zipWith7 function takes a function which combines seven
elements, as well as seven lists and returns a list of their point-wise
combination, analogous to zipWith.
It is capable of list fusion, but it is restricted to its
first list argument and its resulting list.
Splits the argument into a list of lines stripped of their terminating
\n characters. The \n terminator is optional in a final non-empty
line of the argument string.
When the argument string is empty, or ends in a \n character, it can be
recovered by passing the result of lines to the unlines function.
Otherwise, unlines appends the missing terminating \n. This makes
unlines . linesidempotent:
linesCR breaks a String up into a list of Strings at newline
Chars. It is very similar to lines, but it also removes any
trailing 'r'Chars. The resulting String values do not contain
newlines or trailing 'r' characters.
words breaks a string up into a list of words, which were delimited
by white space (as defined by isSpace). This function trims any white spaces
at the beginning and at the end.
Examples
Example1 expression
>>> words "Lorem ipsum\ndolor"["Lorem","ipsum","dolor"]
\mathcal{O}(n^2). The nub function removes duplicate elements from a
list. In particular, it keeps only the first occurrence of each element. (The
name nub means `essence'.) It is a special case of nubBy, which allows
the programmer to supply their own equality test.
If there exists instance Ord a, it's faster to use nubOrd from the containers package
(link to the latest online documentation),
which takes only \mathcal{O}(n \log d) time where d is the number of
distinct elements in the list.
Another approach to speed up nub is to use
mapData.List.NonEmpty.head . Data.List.NonEmpty.group . sort,
which takes \mathcal{O}(n \log n) time, requires instance Ord a and doesn't
preserve the order.
The \\ function is list difference (non-associative).
In the result of xs\\ys, the first occurrence of each element of
ys in turn (if any) has been removed from xs. Thus
(xs ++ ys) \\ xs == ys.
It is a special case of deleteFirstsBy, which allows the programmer
to supply their own equality test.
Examples
Example1 expression
>>> "Hello World!" \\ "ell W""Hoorld!"
The second list must be finite, but the first may be infinite.
The union function returns the list union of the two lists.
It is a special case of unionBy, which allows the programmer to supply
their own equality test.
Examples
Example1 expression
>>> "dog" `union` "cow""dogcw"
If equal elements are present in both lists, an element from the first list
will be used. If the second list contains equal elements, only the first one
will be retained:
The intersect function takes the list intersection of two lists.
It is a special case of intersectBy, which allows the programmer to
supply their own equality test.
Examples
Example1 expression
>>> [1,2,3,4] `intersect` [2,4,6,8][2,4]
If equal elements are present in both lists, an element from the first list
will be used, and all duplicates from the second list quashed:
If the second list is infinite, intersect either hangs
or returns its first argument in full. Otherwise if the first list
is infinite, intersect might be productive:
The sort function implements a stable sorting algorithm.
It is a special case of sortBy, which allows the programmer to supply
their own comparison function.
Elements are arranged from lowest to highest, keeping duplicates in
the order they appeared in the input.
Sort a list by comparing the results of a key function applied to each
element. sortOn f is equivalent to sortBy (comparing f), but has the
performance advantage of only evaluating f once for each element in the
input list. This is called the decorate-sort-undecorate paradigm, or
Schwartzian transform.
Elements are arranged from lowest to highest, keeping duplicates in
the order they appeared in the input.
\mathcal{O}(n). The insert 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 of insertBy,
which allows the programmer to supply their own comparison function.
Examples
Example1 expression
>>> insert (-1) [1, 2, 3][-1,1,2,3]
Example1 expression
>>> insert 'd' "abcefg""abcdefg"
Example1 expression
>>> insert 4 [1, 2, 3, 5, 6, 7][1,2,3,4,5,6,7]
Generalized functions
0 declarations
The "By" operations
By convention, overloaded functions have a non-overloaded
counterpart whose name is suffixed with `By'.
It is often convenient to use these functions together with
on, for instance sortBy (compare
`on` fst).
User-supplied equality (replacing an Eq context)
The predicate is assumed to define an equivalence.
The deleteFirstsBy function takes a predicate and two lists and
returns the first list with the first occurrence of each element of
the second list removed. This is the non-overloaded version of (\\).
(\\) == deleteFirstsBy (==)
The second list must be finite, but the first may be infinite.
The intersectBy function is the non-overloaded version of intersect.
It is productive for infinite arguments only if the first one
is a subset of the second.
The groupBy function is the non-overloaded version of group.
When a supplied relation is not transitive, it is important
to remember that equality is checked against the first element in the group,
not against the nearest neighbour:
Example1 expression
>>> groupBy (\a b -> b - a < 5) [0..19][[0,1,2,3,4],[5,6,7,8,9],[10,11,12,13,14],[15,16,17,18,19]]
It's often preferable to use Data.List.NonEmpty.groupBy,
which provides type-level guarantees of non-emptiness of inner lists.
The sortBy function is the non-overloaded version of sort.
The argument must be finite.
The supplied comparison relation is supposed to be reflexive and antisymmetric,
otherwise, e. g., for _ _ -> GT, the ordered list simply does not exist.
The relation is also expected to be transitive: if it is not then sortBy
might fail to find an ordered permutation, even if it exists.
Examples
Example1 expression
>>> sortBy (\(a,_) (b,_) -> compare a b) [(2, "world"), (4, "!"), (1, "Hello")][(1,"Hello"),(2,"world"),(4,"!")]
\mathcal{O}(n). The genericLength function is an overloaded version
of length. In particular, instead of returning an Int, it returns any
type which is an instance of Num. It is, however, less efficient than
length.
Users should take care to pick a return type that is wide enough to contain
the full length of the list. If the width is insufficient, the overflow
behaviour will depend on the (+) implementation in the selected Num
instance. The following example overflows because the actual list length
of 200 lies outside of the Int8 range of -128..127.