Prime -> 2010
[haskell-report.git] / report / list.verb
1 %**<title>The Haskell 98 Library Report: List Utilities</title>
2 %**~header
3 \section{List Utilities}
4
5 \outline{
6 \inputHS{lib-hdrs/List}
7 }
8 \outline{
9 \inputHS{lib-hdrs/List1}
10 }
11
12 This library defines some lesser-used operations over lists.
13
14 \subsection{Indexing lists}
15
16 \begin{itemize}
17 \item @elemIndex val list@\indextt{elemIndex} returns the index of
18 the first occurrence, if any, of @val@  
19 in @list@ as @Just index@.  @Nothing@ is returned if @not (val `elem` list)@.
20
21 \item @elemIndices val list@\indextt{elemIndices} returns an
22 in-order list of indices, giving the occurrences of @val@ in @list@.
23
24 \item  @find@\indextt{find} 
25 returns the first element of a list that satisfies a predicate,
26 or Nothing, if there is no such element.
27 @findIndex@ returns the corresponding index.
28 @findIndices@ returns a list of all such indices.
29 \end{itemize}
30
31 \subsection{``Set'' operations}
32
33 There are a number of ``set'' operations defined over the @List@ type.
34 @nub@ (meaning ``essence'') removes duplicates elements from a list.
35 @delete@, @(\\)@, @union@ and @intersect@ (and their @By@ variants) 
36 preserve the invariant that their result
37 does not contain duplicates, provided that their first argument
38 contains no duplicates.
39
40 \begin{itemize}
41 \item 
42 @nub@\indextt{nub} removes duplicate elements from a list. For example:
43 \bprog
44 @
45   nub [1,3,1,4,3,3] = [1,3,4]
46 @
47 \eprog
48 \item
49 @delete x@\indextt{delete} 
50 removes the first occurrence of @x@ from its list argument,
51 e.g.,  
52 \bprog
53 @
54   delete 'a' "banana" == "bnana"
55 @
56 \eprog
57
58 \item
59 @(\\)@\index{\\\\@@{\tt  {\char'134}{\char'134}}} is list
60 difference (non-associative).  In the result of @xs \\ ys@,
61 the first occurrence of each element of @ys@ in turn (if any)
62 has been removed from @xs@.  Thus, @(xs ++ ys) \\ xs == ys@.
63
64 \item 
65 @union@\indextt{union} is list union, e.g., 
66 \bprog
67 @
68   "dog" `union` "cow" == "dogcw"
69 @
70 \eprog
71
72 \item
73 @intersect@\indextt{intersect} is list intersection, e.g.,  
74 \bprog
75 @
76   [1,2,3,4] `intersect` [2,4,6,8] == [2,4]
77 @
78 \eprog
79 \end{itemize}
80
81 \subsection{List transformations}
82
83 \begin{itemize}
84 \item
85 @intersperse sep@\indextt{intersperse} 
86 inserts @sep@ between the elements of its list argument,
87 e.g.,  
88 \bprog
89 @
90   intersperse ',' "abcde" == "a,b,c,d,e"
91 @
92 \eprog
93
94 \item
95 @transpose@\indextt{transpose} transposes the rows and columns of its argument,
96 e.g., 
97 \bprog
98 @
99   transpose [[1,2,3],[4,5,6]] == [[1,4],[2,5],[3,6]]
100 @
101 \eprog
102
103 \item
104 @partition@\indextt{partition} 
105 takes a predicate and a list and returns a pair of lists:
106 those elements of the argument list that do and do not satisfy the
107 predicate, respectively; i.e.,
108 \bprog
109 @
110   partition p xs == (filter p xs, filter (not . p) xs)
111 @
112 \eprog
113
114 \item
115 @sort@\indextt{sort}
116 implement a stable sorting algorithm, here specified
117 in terms of the @insertBy@ function, which inserts objects into a list
118 according to the specified ordering relation.
119
120 \item
121 @insert@\indextt{insert}
122 inserts a new element into an {\em ordered} list (arranged in increasing order).
123
124 \item
125 @group@\indextt{group} splits its list argument into a list of lists of equal, adjacent
126 elements. For example
127 \bprog
128 @
129   group "Mississippi" == ["M","i","ss","i","ss","i","pp","i"]
130 @
131 \eprog
132
133 \item
134 @inits@\indextt{inits} returns the list of initial segments of its argument list, shortest first.
135 \bprog
136 @
137   inits "abc" == ["","a","ab","abc"]
138 @
139 \eprog
140
141 \item
142 @tails@\indextt{tails} 
143 returns the list of all final segments of its argument list, longest first.
144 \bprog
145 @
146   tails "abc" == ["abc", "bc", "c",""]
147 @
148
149 \eprog
150 \item
151 @mapAccumL f s l@\indextt{mapAccumL} 
152 applies @f@ to an accumulating ``state'' parameter @s@
153 and to each element of @l@ in turn.
154
155 \item
156 @mapAccumR@\indextt{mapAccumR}
157 is similar to @mapAccumL@ except that the list
158 is processed from right-to-left rather than left-to-right.
159 \end{itemize}
160
161 \subsection{@unfoldr@}
162
163 The @unfoldr@ function is a ``dual'' to @foldr@: while @foldr@ reduces a list
164 to a summary value, @unfoldr@ builds a list from a seed value.  For 
165 example:
166 \bprog
167 @
168   iterate f == unfoldr (\x -> Just (x, f x))
169 @
170 \eprog
171 In some cases, @unfoldr@ can undo a @foldr@ operation:
172 \bprog
173 @
174   unfoldr f' (foldr f z xs) == xs
175 @
176 \eprog
177 if the following holds:
178 \bprog
179 @
180   f' (f x y) = Just (x,y)
181   f' z       = Nothing
182 @
183 \eprog
184
185 \subsection{Predicates}
186
187 @isPrefixOf@ and @isSuffixOf@ check whether the first argument is a prefix (resp. suffix)
188 of the second argument.
189
190
191 \subsection{The ``@By@'' operations}
192
193 By convention, overloaded functions have a non-overloaded
194 counterpart whose name is suffixed with ``@By@''.  For example, the
195 function @nub@ could be defined as follows:
196 \bprog
197 @
198   nub              :: (Eq a) => [a] -> [a]
199   nub []           =  []
200   nub (x:xs)       =  x : nub (filter (\y -> not (x == y)) xs)
201 @
202 \eprog
203 However, the equality method may not be appropriate in all situations.
204 The function:
205 \bprog
206 @
207   nubBy            :: (a -> a -> Bool) -> [a] -> [a]
208   nubBy eq []      =  []
209   nubBy eq (x:xs)  =  x : nubBy eq (filter (\y -> not (eq x y)) xs)
210 @
211 \eprog
212 allows the programmer to supply their own equality test.
213 When the ``@By@'' function replaces an @Eq@ context by a binary predicate,
214 the predicate is assumed to define an equivalence; when the ``@By@''
215 function replaces an @Ord@ context by a binary predicate, the
216 predicate is assumed to define a total ordering.
217
218 The ``@By@'' variants are as follows:
219 @nubBy@, @deleteBy@, @deleteFirstsBy@ (the "@By@" variant of @\\@),
220 @unionBy@, @intersectBy@, @groupBy@,
221 @sortBy@, @insertBy@, @maximumBy@, @minimumBy@.  
222 \indextt{nubBy} 
223 \indextt{deleteBy} 
224 \indextt{deleteFirstsBy} 
225 \indextt{unionBy} 
226 \indextt{intersectBy} 
227 \indextt{groupBy} 
228 \indextt{sortBy} 
229 \indextt{insertBy} 
230 \indextt{maximumBy} 
231 \indextt{minimumBy} 
232
233 The library does not
234 provide @elemBy@, because @any (eq x)@ does the same job as @elemBy eq x@ would.
235 A handful of overloaded functions (@elemIndex@, @elemIndices@, @isPrefixOf@, @isSuffixOf@)
236 were not considered important enough to have ``@By@'' variants.
237
238 % Several of the functions defined here are derivatives of, or
239 % related to, Prelude functions.  These functions are
240 % @elem@, @maximum@, @minimum@, @zip@, @zip3@, @zipWith@,
241 % @zipWith3@, @unzip@, @unzip3@, 
242 % [according to Keith] @take@, @drop@, @splitAt@, @index@, @replicate@.
243
244 \subsection{The ``@generic@'' operations}
245
246 The prefix ``@generic@'' indicates an overloaded function that is
247 a generalised version of a @Prelude@ function.  For example,
248 \bprog
249 @
250   genericLength       :: Integral a => [b] -> a
251
252 \eprog
253 is a generalised version of @length@.
254
255 The ``@generic@'' operations are as follows:
256 @genericLength@, @genericTake@, @genericDrop@,
257     @genericSplitAt@, @genericIndex@ (the generic version of @!!@), @genericReplicate@.
258
259
260 \subsection{Further ``@zip@'' operations}
261
262 The Prelude provides @zip@, @zip3@, @unzip@, @unzip3@, @zipWith@, and @zipWith3@.
263 The List library provides these same three operations for 4, 5, 6, and 7 arguments.
264 \indextt{zip4}
265 \indextt{unzip4}
266 \indextt{zipWith4}
267
268 \clearpage
269 \subsection{Library {\tt List}}
270 \label{List}
271 \inputHS{lib-code/List}
272
273 %**~footer