%**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