%**The Haskell 98 Library Report: List Utilities
%**~header
\section{List Utilities}
\outline{
\inputHS{lib-hdrs/List}
}
\outline{
\inputHS{lib-hdrs/List1}
}
This library defines some lesser-used operations over lists.
\subsection{Indexing lists}
\begin{itemize}
\item @elemIndex val list@\indextt{elemIndex} returns the index of
the first occurrence, if any, of @val@
in @list@ as @Just index@. @Nothing@ is returned if @not (val `elem` list)@.
\item @elemIndices val list@\indextt{elemIndices} returns an
in-order list of indices, giving the occurrences of @val@ in @list@.
\item @find@\indextt{find}
returns the first element of a list that satisfies a predicate,
or Nothing, if there is no such element.
@findIndex@ returns the corresponding index.
@findIndices@ returns a list of all such indices.
\end{itemize}
\subsection{``Set'' operations}
There are a number of ``set'' operations defined over the @List@ type.
@nub@ (meaning ``essence'') removes duplicates elements from a list.
@delete@, @(\\)@, @union@ and @intersect@ (and their @By@ variants)
preserve the invariant that their result
does not contain duplicates, provided that their first argument
contains no duplicates.
\begin{itemize}
\item
@nub@\indextt{nub} removes duplicate elements from a list. For example:
\bprog
@
nub [1,3,1,4,3,3] = [1,3,4]
@
\eprog
\item
@delete x@\indextt{delete}
removes the first occurrence of @x@ from its list argument,
e.g.,
\bprog
@
delete 'a' "banana" == "bnana"
@
\eprog
\item
@(\\)@\index{\\\\@@{\tt {\char'134}{\char'134}}} 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@.
\item
@union@\indextt{union} is list union, e.g.,
\bprog
@
"dog" `union` "cow" == "dogcw"
@
\eprog
\item
@intersect@\indextt{intersect} is list intersection, e.g.,
\bprog
@
[1,2,3,4] `intersect` [2,4,6,8] == [2,4]
@
\eprog
\end{itemize}
\subsection{List transformations}
\begin{itemize}
\item
@intersperse sep@\indextt{intersperse}
inserts @sep@ between the elements of its list argument,
e.g.,
\bprog
@
intersperse ',' "abcde" == "a,b,c,d,e"
@
\eprog
\item
@transpose@\indextt{transpose} transposes the rows and columns of its argument,
e.g.,
\bprog
@
transpose [[1,2,3],[4,5,6]] == [[1,4],[2,5],[3,6]]
@
\eprog
\item
@partition@\indextt{partition}
takes a predicate and a list and returns a pair of lists:
those elements of the argument list that do and do not satisfy the
predicate, respectively; i.e.,
\bprog
@
partition p xs == (filter p xs, filter (not . p) xs)
@
\eprog
\item
@sort@\indextt{sort}
implement a stable sorting algorithm, here specified
in terms of the @insertBy@ function, which inserts objects into a list
according to the specified ordering relation.
\item
@insert@\indextt{insert}
inserts a new element into an {\em ordered} list (arranged in increasing order).
\item
@group@\indextt{group} splits its list argument into a list of lists of equal, adjacent
elements. For example
\bprog
@
group "Mississippi" == ["M","i","ss","i","ss","i","pp","i"]
@
\eprog
\item
@inits@\indextt{inits} returns the list of initial segments of its argument list, shortest first.
\bprog
@
inits "abc" == ["","a","ab","abc"]
@
\eprog
\item
@tails@\indextt{tails}
returns the list of all final segments of its argument list, longest first.
\bprog
@
tails "abc" == ["abc", "bc", "c",""]
@
\eprog
\item
@mapAccumL f s l@\indextt{mapAccumL}
applies @f@ to an accumulating ``state'' parameter @s@
and to each element of @l@ in turn.
\item
@mapAccumR@\indextt{mapAccumR}
is similar to @mapAccumL@ except that the list
is processed from right-to-left rather than left-to-right.
\end{itemize}
\subsection{@unfoldr@}
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. For
example:
\bprog
@
iterate f == unfoldr (\x -> Just (x, f x))
@
\eprog
In some cases, @unfoldr@ can undo a @foldr@ operation:
\bprog
@
unfoldr f' (foldr f z xs) == xs
@
\eprog
if the following holds:
\bprog
@
f' (f x y) = Just (x,y)
f' z = Nothing
@
\eprog
\subsection{Predicates}
@isPrefixOf@ and @isSuffixOf@ check whether the first argument is a prefix (resp. suffix)
of the second argument.
\subsection{The ``@By@'' operations}
By convention, overloaded functions have a non-overloaded
counterpart whose name is suffixed with ``@By@''. For example, the
function @nub@ could be defined as follows:
\bprog
@
nub :: (Eq a) => [a] -> [a]
nub [] = []
nub (x:xs) = x : nub (filter (\y -> not (x == y)) xs)
@
\eprog
However, the equality method may not be appropriate in all situations.
The function:
\bprog
@
nubBy :: (a -> a -> Bool) -> [a] -> [a]
nubBy eq [] = []
nubBy eq (x:xs) = x : nubBy eq (filter (\y -> not (eq x y)) xs)
@
\eprog
allows the programmer to supply their own equality test.
When the ``@By@'' function replaces an @Eq@ context by a binary predicate,
the predicate is assumed to define an equivalence; when the ``@By@''
function replaces an @Ord@ context by a binary predicate, the
predicate is assumed to define a total ordering.
The ``@By@'' variants are as follows:
@nubBy@, @deleteBy@, @deleteFirstsBy@ (the "@By@" variant of @\\@),
@unionBy@, @intersectBy@, @groupBy@,
@sortBy@, @insertBy@, @maximumBy@, @minimumBy@.
\indextt{nubBy}
\indextt{deleteBy}
\indextt{deleteFirstsBy}
\indextt{unionBy}
\indextt{intersectBy}
\indextt{groupBy}
\indextt{sortBy}
\indextt{insertBy}
\indextt{maximumBy}
\indextt{minimumBy}
The library does not
provide @elemBy@, because @any (eq x)@ does the same job as @elemBy eq x@ would.
A handful of overloaded functions (@elemIndex@, @elemIndices@, @isPrefixOf@, @isSuffixOf@)
were not considered important enough to have ``@By@'' variants.
% Several of the functions defined here are derivatives of, or
% related to, Prelude functions. These functions are
% @elem@, @maximum@, @minimum@, @zip@, @zip3@, @zipWith@,
% @zipWith3@, @unzip@, @unzip3@,
% [according to Keith] @take@, @drop@, @splitAt@, @index@, @replicate@.
\subsection{The ``@generic@'' operations}
The prefix ``@generic@'' indicates an overloaded function that is
a generalised version of a @Prelude@ function. For example,
\bprog
@
genericLength :: Integral a => [b] -> a
@
\eprog
is a generalised version of @length@.
The ``@generic@'' operations are as follows:
@genericLength@, @genericTake@, @genericDrop@,
@genericSplitAt@, @genericIndex@ (the generic version of @!!@), @genericReplicate@.
\subsection{Further ``@zip@'' operations}
The Prelude provides @zip@, @zip3@, @unzip@, @unzip3@, @zipWith@, and @zipWith3@.
The List library provides these same three operations for 4, 5, 6, and 7 arguments.
\indextt{zip4}
\indextt{unzip4}
\indextt{zipWith4}
\clearpage
\subsection{Library {\tt List}}
\label{List}
\inputHS{lib-code/List}
%**~footer