clarify shortcutting behaviour of all/any/elem
[haskell-report.git] / report / libs / Data-List.tex
1 \haddockmoduleheading{Data.List}
2 \label{module:Data.List}
3 \haddockbeginheader
4 {\haddockverb\begin{verbatim}
5 module Data.List (
6 (++), head, last, tail, init, null, length, map, reverse,
7 intersperse, intercalate, transpose, subsequences, permutations,
8 foldl, foldl', foldl1, foldl1', foldr, foldr1, concat, concatMap,
9 and, or, any, all, sum, product, maximum, minimum, scanl, scanl1,
10 scanr, scanr1, mapAccumL, mapAccumR, iterate, repeat, replicate,
11 cycle, unfoldr, take, drop, splitAt, takeWhile, dropWhile, span,
12 break, stripPrefix, group, inits, tails, isPrefixOf, isSuffixOf,
13 isInfixOf, elem, notElem, lookup, find, filter, partition, (!!),
14 elemIndex, elemIndices, findIndex, findIndices, zip, zip3, zip4,
15 zip5, zip6, zip7, zipWith, zipWith3, zipWith4, zipWith5, zipWith6,
16 zipWith7, unzip, unzip3, unzip4, unzip5, unzip6, unzip7, lines,
17 words, unlines, unwords, nub, delete, (\\), union, intersect, sort,
18 insert, nubBy, deleteBy, deleteFirstsBy, unionBy, intersectBy,
19 groupBy, sortBy, insertBy, maximumBy, minimumBy, genericLength,
20 genericTake, genericDrop, genericSplitAt, genericIndex, genericReplicate
21 ) where\end{verbatim}}
22 \haddockendheader
23
24 \section{Basic functions
25 }
26 \begin{haddockdesc}
27 \item[\begin{tabular}{@{}l}
28 (++)\ ::\ {\char 91}a{\char 93}\ ->\ {\char 91}a{\char 93}\ ->\ {\char 91}a{\char 93}
29 \end{tabular}]\haddockbegindoc
30 Append two lists, i.e.,
31 \par
32 \begin{quote}
33 {\haddockverb\begin{verbatim}
34 [x1, ..., xm] ++ [y1, ..., yn] == [x1, ..., xm, y1, ..., yn]
35 [x1, ..., xm] ++ [y1, ...] == [x1, ..., xm, y1, ...]
36 \end{verbatim}}
37 \end{quote}
38 If the first list is not finite, the result is the first list.
39 \par
40
41 \end{haddockdesc}
42 \begin{haddockdesc}
43 \item[\begin{tabular}{@{}l}
44 head\ ::\ {\char 91}a{\char 93}\ ->\ a
45 \end{tabular}]\haddockbegindoc
46 Extract the first element of a list, which must be non-empty.
47 \par
48
49 \end{haddockdesc}
50 \begin{haddockdesc}
51 \item[\begin{tabular}{@{}l}
52 last\ ::\ {\char 91}a{\char 93}\ ->\ a
53 \end{tabular}]\haddockbegindoc
54 Extract the last element of a list, which must be finite and non-empty.
55 \par
56
57 \end{haddockdesc}
58 \begin{haddockdesc}
59 \item[\begin{tabular}{@{}l}
60 tail\ ::\ {\char 91}a{\char 93}\ ->\ {\char 91}a{\char 93}
61 \end{tabular}]\haddockbegindoc
62 Extract the elements after the head of a list, which must be non-empty.
63 \par
64
65 \end{haddockdesc}
66 \begin{haddockdesc}
67 \item[\begin{tabular}{@{}l}
68 init\ ::\ {\char 91}a{\char 93}\ ->\ {\char 91}a{\char 93}
69 \end{tabular}]\haddockbegindoc
70 Return all the elements of a list except the last one.
71 The list must be non-empty.
72 \par
73
74 \end{haddockdesc}
75 \begin{haddockdesc}
76 \item[\begin{tabular}{@{}l}
77 null\ ::\ {\char 91}a{\char 93}\ ->\ Bool
78 \end{tabular}]\haddockbegindoc
79 Test whether a list is empty.
80 \par
81
82 \end{haddockdesc}
83 \begin{haddockdesc}
84 \item[\begin{tabular}{@{}l}
85 length\ ::\ {\char 91}a{\char 93}\ ->\ Int
86 \end{tabular}]\haddockbegindoc
87 \emph{O(n)}. \haddockid{length} returns the length of a finite list as an \haddockid{Int}.
88 It is an instance of the more general \haddocktt{Data.List.genericLength},
89 the result type of which may be any kind of number.
90 \par
91
92 \end{haddockdesc}
93 \section{List transformations
94 }
95 \begin{haddockdesc}
96 \item[\begin{tabular}{@{}l}
97 map\ ::\ (a\ ->\ b)\ ->\ {\char 91}a{\char 93}\ ->\ {\char 91}b{\char 93}
98 \end{tabular}]\haddockbegindoc
99 \haddockid{map} \haddocktt{f\ xs} is the list obtained by applying \haddocktt{f} to each element
100 of \haddocktt{xs}, i.e.,
101 \par
102 \begin{quote}
103 {\haddockverb\begin{verbatim}
104 map f [x1, x2, ..., xn] == [f x1, f x2, ..., f xn]
105 map f [x1, x2, ...] == [f x1, f x2, ...]
106 \end{verbatim}}
107 \end{quote}
108
109 \end{haddockdesc}
110 \begin{haddockdesc}
111 \item[\begin{tabular}{@{}l}
112 reverse\ ::\ {\char 91}a{\char 93}\ ->\ {\char 91}a{\char 93}
113 \end{tabular}]\haddockbegindoc
114 \haddockid{reverse} \haddocktt{xs} returns the elements of \haddocktt{xs} in reverse order.
115 \haddocktt{xs} must be finite.
116 \par
117
118 \end{haddockdesc}
119 \begin{haddockdesc}
120 \item[\begin{tabular}{@{}l}
121 intersperse\ ::\ a\ ->\ {\char 91}a{\char 93}\ ->\ {\char 91}a{\char 93}
122 \end{tabular}]\haddockbegindoc
123 The \haddockid{intersperse} function takes an element and a list and
124 `intersperses' that element between the elements of the list.
125 For example,
126 \par
127 \begin{quote}
128 {\haddockverb\begin{verbatim}
129 intersperse ',' "abcde" == "a,b,c,d,e"
130 \end{verbatim}}
131 \end{quote}
132
133 \end{haddockdesc}
134 \begin{haddockdesc}
135 \item[\begin{tabular}{@{}l}
136 intercalate\ ::\ {\char 91}a{\char 93}\ ->\ {\char 91}{\char 91}a{\char 93}{\char 93}\ ->\ {\char 91}a{\char 93}
137 \end{tabular}]\haddockbegindoc
138 \haddockid{intercalate} \haddocktt{xs\ xss} is equivalent to \haddocktt{(concat\ (intersperse\ xs\ xss))}.
139 It inserts the list \haddocktt{xs} in between the lists in \haddocktt{xss} and concatenates the
140 result.
141 \par
142
143 \end{haddockdesc}
144 \begin{haddockdesc}
145 \item[\begin{tabular}{@{}l}
146 transpose\ ::\ {\char 91}{\char 91}a{\char 93}{\char 93}\ ->\ {\char 91}{\char 91}a{\char 93}{\char 93}
147 \end{tabular}]\haddockbegindoc
148 The \haddockid{transpose} function transposes the rows and columns of its argument.
149 For example,
150 \par
151 \begin{quote}
152 {\haddockverb\begin{verbatim}
153 transpose [[1,2,3],[4,5,6]] == [[1,4],[2,5],[3,6]]
154 \end{verbatim}}
155 \end{quote}
156
157 \end{haddockdesc}
158 \begin{haddockdesc}
159 \item[\begin{tabular}{@{}l}
160 subsequences\ ::\ {\char 91}a{\char 93}\ ->\ {\char 91}{\char 91}a{\char 93}{\char 93}
161 \end{tabular}]\haddockbegindoc
162 The \haddockid{subsequences} function returns the list of all subsequences of the argument.
163 \par
164 \begin{quote}
165 {\haddockverb\begin{verbatim}
166 subsequences "abc" == ["","a","b","ab","c","ac","bc","abc"]
167 \end{verbatim}}
168 \end{quote}
169
170 \end{haddockdesc}
171 \begin{haddockdesc}
172 \item[\begin{tabular}{@{}l}
173 permutations\ ::\ {\char 91}a{\char 93}\ ->\ {\char 91}{\char 91}a{\char 93}{\char 93}
174 \end{tabular}]\haddockbegindoc
175 The \haddockid{permutations} function returns the list of all permutations of the argument.
176 \par
177 \begin{quote}
178 {\haddockverb\begin{verbatim}
179 permutations "abc" == ["abc","bac","cba","bca","cab","acb"]
180 \end{verbatim}}
181 \end{quote}
182
183 \end{haddockdesc}
184 \section{Reducing lists (folds)
185 }
186 \begin{haddockdesc}
187 \item[\begin{tabular}{@{}l}
188 foldl\ ::\ (a\ ->\ b\ ->\ a)\ ->\ a\ ->\ {\char 91}b{\char 93}\ ->\ a
189 \end{tabular}]\haddockbegindoc
190 \haddockid{foldl}, applied to a binary operator, a starting value (typically
191 the left-identity of the operator), and a list, reduces the list
192 using the binary operator, from left to right:
193 \par
194 \begin{quote}
195 {\haddockverb\begin{verbatim}
196 foldl f z [x1, x2, ..., xn] == (...((z `f` x1) `f` x2) `f`...) `f` xn
197 \end{verbatim}}
198 \end{quote}
199 The list must be finite.
200 \par
201
202 \end{haddockdesc}
203 \begin{haddockdesc}
204 \item[\begin{tabular}{@{}l}
205 foldl'\ ::\ (a\ ->\ b\ ->\ a)\ ->\ a\ ->\ {\char 91}b{\char 93}\ ->\ a
206 \end{tabular}]\haddockbegindoc
207 A strict version of \haddockid{foldl}.
208 \par
209
210 \end{haddockdesc}
211 \begin{haddockdesc}
212 \item[\begin{tabular}{@{}l}
213 foldl1\ ::\ (a\ ->\ a\ ->\ a)\ ->\ {\char 91}a{\char 93}\ ->\ a
214 \end{tabular}]\haddockbegindoc
215 \haddockid{foldl1} is a variant of \haddockid{foldl} that has no starting value argument,
216 and thus must be applied to non-empty lists.
217 \par
218
219 \end{haddockdesc}
220 \begin{haddockdesc}
221 \item[\begin{tabular}{@{}l}
222 foldl1'\ ::\ (a\ ->\ a\ ->\ a)\ ->\ {\char 91}a{\char 93}\ ->\ a
223 \end{tabular}]\haddockbegindoc
224 A strict version of \haddockid{foldl1}
225 \par
226
227 \end{haddockdesc}
228 \begin{haddockdesc}
229 \item[\begin{tabular}{@{}l}
230 foldr\ ::\ (a\ ->\ b\ ->\ b)\ ->\ b\ ->\ {\char 91}a{\char 93}\ ->\ b
231 \end{tabular}]\haddockbegindoc
232 \haddockid{foldr}, applied to a binary operator, a starting value (typically
233 the right-identity of the operator), and a list, reduces the list
234 using the binary operator, from right to left:
235 \par
236 \begin{quote}
237 {\haddockverb\begin{verbatim}
238 foldr f z [x1, x2, ..., xn] == x1 `f` (x2 `f` ... (xn `f` z)...)
239 \end{verbatim}}
240 \end{quote}
241
242 \end{haddockdesc}
243 \begin{haddockdesc}
244 \item[\begin{tabular}{@{}l}
245 foldr1\ ::\ (a\ ->\ a\ ->\ a)\ ->\ {\char 91}a{\char 93}\ ->\ a
246 \end{tabular}]\haddockbegindoc
247 \haddockid{foldr1} is a variant of \haddockid{foldr} that has no starting value argument,
248 and thus must be applied to non-empty lists.
249 \par
250
251 \end{haddockdesc}
252 \subsection{Special folds
253 }
254 \begin{haddockdesc}
255 \item[\begin{tabular}{@{}l}
256 concat\ ::\ {\char 91}{\char 91}a{\char 93}{\char 93}\ ->\ {\char 91}a{\char 93}
257 \end{tabular}]\haddockbegindoc
258 Concatenate a list of lists.
259 \par
260
261 \end{haddockdesc}
262 \begin{haddockdesc}
263 \item[\begin{tabular}{@{}l}
264 concatMap\ ::\ (a\ ->\ {\char 91}b{\char 93})\ ->\ {\char 91}a{\char 93}\ ->\ {\char 91}b{\char 93}
265 \end{tabular}]\haddockbegindoc
266 Map a function over a list and concatenate the results.
267 \par
268
269 \end{haddockdesc}
270 \begin{haddockdesc}
271 \item[\begin{tabular}{@{}l}
272 and\ ::\ {\char 91}Bool{\char 93}\ ->\ Bool
273 \end{tabular}]\haddockbegindoc
274 \haddockid{and} returns the conjunction of a Boolean list. For the result to be
275 \haddockid{True}, the list must be finite; \haddockid{False}, however, results from a \haddockid{False}
276 value at a finite index of a finite or infinite list.
277 \par
278
279 \end{haddockdesc}
280 \begin{haddockdesc}
281 \item[\begin{tabular}{@{}l}
282 or\ ::\ {\char 91}Bool{\char 93}\ ->\ Bool
283 \end{tabular}]\haddockbegindoc
284 \haddockid{or} returns the disjunction of a Boolean list. For the result to be
285 \haddockid{False}, the list must be finite; \haddockid{True}, however, results from a \haddockid{True}
286 value at a finite index of a finite or infinite list.
287 \par
288
289 \end{haddockdesc}
290 \begin{haddockdesc}
291 \item[\begin{tabular}{@{}l}
292 any\ ::\ (a\ ->\ Bool)\ ->\ {\char 91}a{\char 93}\ ->\ Bool
293 \end{tabular}]\haddockbegindoc
294 Applied to a predicate and a list, \haddockid{any} determines if any element
295 of the list satisfies the predicate. For the result to be
296 \haddockid{False}, the list must be finite; \haddockid{True}, however, results from a \haddockid{True}
297 value for the predicate applied to an element at a finite index of a finite or infinite list.
298 \par
299
300 \end{haddockdesc}
301 \begin{haddockdesc}
302 \item[\begin{tabular}{@{}l}
303 all\ ::\ (a\ ->\ Bool)\ ->\ {\char 91}a{\char 93}\ ->\ Bool
304 \end{tabular}]\haddockbegindoc
305 Applied to a predicate and a list, \haddockid{all} determines if all elements
306 of the list satisfy the predicate. For the result to be
307 \haddockid{True}, the list must be finite; \haddockid{False}, however, results from a \haddockid{False}
308 value for the predicate applied to an element at a finite index of a finite or infinite list.
309 \par
310
311 \end{haddockdesc}
312 \begin{haddockdesc}
313 \item[\begin{tabular}{@{}l}
314 sum\ ::\ Num\ a\ =>\ {\char 91}a{\char 93}\ ->\ a
315 \end{tabular}]\haddockbegindoc
316 The \haddockid{sum} function computes the sum of a finite list of numbers.
317 \par
318
319 \end{haddockdesc}
320 \begin{haddockdesc}
321 \item[\begin{tabular}{@{}l}
322 product\ ::\ Num\ a\ =>\ {\char 91}a{\char 93}\ ->\ a
323 \end{tabular}]\haddockbegindoc
324 The \haddockid{product} function computes the product of a finite list of numbers.
325 \par
326
327 \end{haddockdesc}
328 \begin{haddockdesc}
329 \item[\begin{tabular}{@{}l}
330 maximum\ ::\ Ord\ a\ =>\ {\char 91}a{\char 93}\ ->\ a
331 \end{tabular}]\haddockbegindoc
332 \haddockid{maximum} returns the maximum value from a list,
333 which must be non-empty, finite, and of an ordered type.
334 It is a special case of \haddockid{maximumBy}, which allows the
335 programmer to supply their own comparison function.
336 \par
337
338 \end{haddockdesc}
339 \begin{haddockdesc}
340 \item[\begin{tabular}{@{}l}
341 minimum\ ::\ Ord\ a\ =>\ {\char 91}a{\char 93}\ ->\ a
342 \end{tabular}]\haddockbegindoc
343 \haddockid{minimum} returns the minimum value from a list,
344 which must be non-empty, finite, and of an ordered type.
345 It is a special case of \haddockid{minimumBy}, which allows the
346 programmer to supply their own comparison function.
347 \par
348
349 \end{haddockdesc}
350 \section{Building lists
351 }
352 \subsection{Scans
353 }
354 \begin{haddockdesc}
355 \item[\begin{tabular}{@{}l}
356 scanl\ ::\ (a\ ->\ b\ ->\ a)\ ->\ a\ ->\ {\char 91}b{\char 93}\ ->\ {\char 91}a{\char 93}
357 \end{tabular}]\haddockbegindoc
358 \haddockid{scanl} is similar to \haddockid{foldl}, but returns a list of successive
359 reduced values from the left:
360 \par
361 \begin{quote}
362 {\haddockverb\begin{verbatim}
363 scanl f z [x1, x2, ...] == [z, z `f` x1, (z `f` x1) `f` x2, ...]
364 \end{verbatim}}
365 \end{quote}
366 Note that
367 \par
368 \begin{quote}
369 {\haddockverb\begin{verbatim}
370 last (scanl f z xs) == foldl f z xs.
371 \end{verbatim}}
372 \end{quote}
373
374 \end{haddockdesc}
375 \begin{haddockdesc}
376 \item[\begin{tabular}{@{}l}
377 scanl1\ ::\ (a\ ->\ a\ ->\ a)\ ->\ {\char 91}a{\char 93}\ ->\ {\char 91}a{\char 93}
378 \end{tabular}]\haddockbegindoc
379 \haddockid{scanl1} is a variant of \haddockid{scanl} that has no starting value argument:
380 \par
381 \begin{quote}
382 {\haddockverb\begin{verbatim}
383 scanl1 f [x1, x2, ...] == [x1, x1 `f` x2, ...]
384 \end{verbatim}}
385 \end{quote}
386
387 \end{haddockdesc}
388 \begin{haddockdesc}
389 \item[\begin{tabular}{@{}l}
390 scanr\ ::\ (a\ ->\ b\ ->\ b)\ ->\ b\ ->\ {\char 91}a{\char 93}\ ->\ {\char 91}b{\char 93}
391 \end{tabular}]\haddockbegindoc
392 \haddockid{scanr} is the right-to-left dual of \haddockid{scanl}.
393 Note that
394 \par
395 \begin{quote}
396 {\haddockverb\begin{verbatim}
397 head (scanr f z xs) == foldr f z xs.
398 \end{verbatim}}
399 \end{quote}
400
401 \end{haddockdesc}
402 \begin{haddockdesc}
403 \item[\begin{tabular}{@{}l}
404 scanr1\ ::\ (a\ ->\ a\ ->\ a)\ ->\ {\char 91}a{\char 93}\ ->\ {\char 91}a{\char 93}
405 \end{tabular}]\haddockbegindoc
406 \haddockid{scanr1} is a variant of \haddockid{scanr} that has no starting value argument.
407 \par
408
409 \end{haddockdesc}
410 \subsection{Accumulating maps
411 }
412 \begin{haddockdesc}
413 \item[\begin{tabular}{@{}l}
414 mapAccumL\ ::\ (acc\ ->\ x\ ->\ (acc,\ y))\ ->\ acc\ ->\ {\char 91}x{\char 93}\ ->\ (acc,\ {\char 91}y{\char 93})
415 \end{tabular}]\haddockbegindoc
416 The \haddockid{mapAccumL} function behaves like a combination of \haddockid{map} and
417 \haddockid{foldl}; it applies a function to each element of a list, passing
418 an accumulating parameter from left to right, and returning a final
419 value of this accumulator together with the new list.
420 \par
421
422 \end{haddockdesc}
423 \begin{haddockdesc}
424 \item[\begin{tabular}{@{}l}
425 mapAccumR\ ::\ (acc\ ->\ x\ ->\ (acc,\ y))\ ->\ acc\ ->\ {\char 91}x{\char 93}\ ->\ (acc,\ {\char 91}y{\char 93})
426 \end{tabular}]\haddockbegindoc
427 The \haddockid{mapAccumR} function behaves like a combination of \haddockid{map} and
428 \haddockid{foldr}; it applies a function to each element of a list, passing
429 an accumulating parameter from right to left, and returning a final
430 value of this accumulator together with the new list.
431 \par
432
433 \end{haddockdesc}
434 \subsection{Infinite lists
435 }
436 \begin{haddockdesc}
437 \item[\begin{tabular}{@{}l}
438 iterate\ ::\ (a\ ->\ a)\ ->\ a\ ->\ {\char 91}a{\char 93}
439 \end{tabular}]\haddockbegindoc
440 \haddockid{iterate} \haddocktt{f\ x} returns an infinite list of repeated applications
441 of \haddocktt{f} to \haddocktt{x}:
442 \par
443 \begin{quote}
444 {\haddockverb\begin{verbatim}
445 iterate f x == [x, f x, f (f x), ...]
446 \end{verbatim}}
447 \end{quote}
448
449 \end{haddockdesc}
450 \begin{haddockdesc}
451 \item[\begin{tabular}{@{}l}
452 repeat\ ::\ a\ ->\ {\char 91}a{\char 93}
453 \end{tabular}]\haddockbegindoc
454 \haddockid{repeat} \haddocktt{x} is an infinite list, with \haddocktt{x} the value of every element.
455 \par
456
457 \end{haddockdesc}
458 \begin{haddockdesc}
459 \item[\begin{tabular}{@{}l}
460 replicate\ ::\ Int\ ->\ a\ ->\ {\char 91}a{\char 93}
461 \end{tabular}]\haddockbegindoc
462 \haddockid{replicate} \haddocktt{n\ x} is a list of length \haddocktt{n} with \haddocktt{x} the value of
463 every element.
464 It is an instance of the more general \haddocktt{Data.List.genericReplicate},
465 in which \haddocktt{n} may be of any integral type.
466 \par
467
468 \end{haddockdesc}
469 \begin{haddockdesc}
470 \item[\begin{tabular}{@{}l}
471 cycle\ ::\ {\char 91}a{\char 93}\ ->\ {\char 91}a{\char 93}
472 \end{tabular}]\haddockbegindoc
473 \haddockid{cycle} ties a finite list into a circular one, or equivalently,
474 the infinite repetition of the original list. It is the identity
475 on infinite lists.
476 \par
477
478 \end{haddockdesc}
479 \subsection{Unfolding
480 }
481 \begin{haddockdesc}
482 \item[\begin{tabular}{@{}l}
483 unfoldr\ ::\ (b\ ->\ Maybe\ (a,\ b))\ ->\ b\ ->\ {\char 91}a{\char 93}
484 \end{tabular}]\haddockbegindoc
485 The \haddockid{unfoldr} function is a `dual' to \haddockid{foldr}: while \haddockid{foldr}
486 reduces a list to a summary value, \haddockid{unfoldr} builds a list from
487 a seed value. The function takes the element and returns \haddockid{Nothing}
488 if it is done producing the list or returns \haddockid{Just} \haddocktt{(a,b)}, in which
489 case, \haddocktt{a} is a prepended to the list and \haddocktt{b} is used as the next
490 element in a recursive call. For example,
491 \par
492 \begin{quote}
493 {\haddockverb\begin{verbatim}
494 iterate f == unfoldr (\x -> Just (x, f x))
495 \end{verbatim}}
496 \end{quote}
497 In some cases, \haddockid{unfoldr} can undo a \haddockid{foldr} operation:
498 \par
499 \begin{quote}
500 {\haddockverb\begin{verbatim}
501 unfoldr f' (foldr f z xs) == xs
502 \end{verbatim}}
503 \end{quote}
504 if the following holds:
505 \par
506 \begin{quote}
507 {\haddockverb\begin{verbatim}
508 f' (f x y) = Just (x,y)
509 f' z = Nothing
510 \end{verbatim}}
511 \end{quote}
512 A simple use of unfoldr:
513 \par
514 \begin{quote}
515 {\haddockverb\begin{verbatim}
516 unfoldr (\b -> if b == 0 then Nothing else Just (b, b-1)) 10
517 [10,9,8,7,6,5,4,3,2,1]
518 \end{verbatim}}
519 \end{quote}
520
521 \end{haddockdesc}
522 \section{Sublists
523 }
524 \subsection{Extracting sublists
525 }
526 \begin{haddockdesc}
527 \item[\begin{tabular}{@{}l}
528 take\ ::\ Int\ ->\ {\char 91}a{\char 93}\ ->\ {\char 91}a{\char 93}
529 \end{tabular}]\haddockbegindoc
530 \haddockid{take} \haddocktt{n}, applied to a list \haddocktt{xs}, returns the prefix of \haddocktt{xs}
531 of length \haddocktt{n}, or \haddocktt{xs} itself if \haddocktt{n\ >\ length\ xs}:
532 \par
533 \begin{quote}
534 {\haddockverb\begin{verbatim}
535 take 5 "Hello World!" == "Hello"
536 take 3 [1,2,3,4,5] == [1,2,3]
537 take 3 [1,2] == [1,2]
538 take 3 [] == []
539 take (-1) [1,2] == []
540 take 0 [1,2] == []
541 \end{verbatim}}
542 \end{quote}
543 It is an instance of the more general \haddocktt{Data.List.genericTake},
544 in which \haddocktt{n} may be of any integral type.
545 \par
546
547 \end{haddockdesc}
548 \begin{haddockdesc}
549 \item[\begin{tabular}{@{}l}
550 drop\ ::\ Int\ ->\ {\char 91}a{\char 93}\ ->\ {\char 91}a{\char 93}
551 \end{tabular}]\haddockbegindoc
552 \haddockid{drop} \haddocktt{n\ xs} returns the suffix of \haddocktt{xs}
553 after the first \haddocktt{n} elements, or \haddocktt{{\char 91}{\char 93}} if \haddocktt{n\ >\ length\ xs}:
554 \par
555 \begin{quote}
556 {\haddockverb\begin{verbatim}
557 drop 6 "Hello World!" == "World!"
558 drop 3 [1,2,3,4,5] == [4,5]
559 drop 3 [1,2] == []
560 drop 3 [] == []
561 drop (-1) [1,2] == [1,2]
562 drop 0 [1,2] == [1,2]
563 \end{verbatim}}
564 \end{quote}
565 It is an instance of the more general \haddocktt{Data.List.genericDrop},
566 in which \haddocktt{n} may be of any integral type.
567 \par
568
569 \end{haddockdesc}
570 \begin{haddockdesc}
571 \item[\begin{tabular}{@{}l}
572 splitAt\ ::\ Int\ ->\ {\char 91}a{\char 93}\ ->\ ({\char 91}a{\char 93},\ {\char 91}a{\char 93})
573 \end{tabular}]\haddockbegindoc
574 \haddockid{splitAt} \haddocktt{n\ xs} returns a tuple where first element is \haddocktt{xs} prefix of
575 length \haddocktt{n} and second element is the remainder of the list:
576 \par
577 \begin{quote}
578 {\haddockverb\begin{verbatim}
579 splitAt 6 "Hello World!" == ("Hello ","World!")
580 splitAt 3 [1,2,3,4,5] == ([1,2,3],[4,5])
581 splitAt 1 [1,2,3] == ([1],[2,3])
582 splitAt 3 [1,2,3] == ([1,2,3],[])
583 splitAt 4 [1,2,3] == ([1,2,3],[])
584 splitAt 0 [1,2,3] == ([],[1,2,3])
585 splitAt (-1) [1,2,3] == ([],[1,2,3])
586 \end{verbatim}}
587 \end{quote}
588 It is equivalent to \haddocktt{(take\ n\ xs,\ drop\ n\ xs)}.
589 \haddockid{splitAt} is an instance of the more general \haddocktt{Data.List.genericSplitAt},
590 in which \haddocktt{n} may be of any integral type.
591 \par
592
593 \end{haddockdesc}
594 \begin{haddockdesc}
595 \item[\begin{tabular}{@{}l}
596 takeWhile\ ::\ (a\ ->\ Bool)\ ->\ {\char 91}a{\char 93}\ ->\ {\char 91}a{\char 93}
597 \end{tabular}]\haddockbegindoc
598 \haddockid{takeWhile}, applied to a predicate \haddocktt{p} and a list \haddocktt{xs}, returns the
599 longest prefix (possibly empty) of \haddocktt{xs} of elements that satisfy \haddocktt{p}:
600 \par
601 \begin{quote}
602 {\haddockverb\begin{verbatim}
603 takeWhile (< 3) [1,2,3,4,1,2,3,4] == [1,2]
604 takeWhile (< 9) [1,2,3] == [1,2,3]
605 takeWhile (< 0) [1,2,3] == []
606 \end{verbatim}}
607 \end{quote}
608
609 \end{haddockdesc}
610 \begin{haddockdesc}
611 \item[\begin{tabular}{@{}l}
612 dropWhile\ ::\ (a\ ->\ Bool)\ ->\ {\char 91}a{\char 93}\ ->\ {\char 91}a{\char 93}
613 \end{tabular}]\haddockbegindoc
614 \haddockid{dropWhile} \haddocktt{p\ xs} returns the suffix remaining after \haddockid{takeWhile} \haddocktt{p\ xs}:
615 \par
616 \begin{quote}
617 {\haddockverb\begin{verbatim}
618 dropWhile (< 3) [1,2,3,4,5,1,2,3] == [3,4,5,1,2,3]
619 dropWhile (< 9) [1,2,3] == []
620 dropWhile (< 0) [1,2,3] == [1,2,3]
621 \end{verbatim}}
622 \end{quote}
623
624 \end{haddockdesc}
625 \begin{haddockdesc}
626 \item[\begin{tabular}{@{}l}
627 span\ ::\ (a\ ->\ Bool)\ ->\ {\char 91}a{\char 93}\ ->\ ({\char 91}a{\char 93},\ {\char 91}a{\char 93})
628 \end{tabular}]\haddockbegindoc
629 \haddockid{span}, applied to a predicate \haddocktt{p} and a list \haddocktt{xs}, returns a tuple where
630 first element is longest prefix (possibly empty) of \haddocktt{xs} of elements that
631 satisfy \haddocktt{p} and second element is the remainder of the list:
632 \par
633 \begin{quote}
634 {\haddockverb\begin{verbatim}
635 span (< 3) [1,2,3,4,1,2,3,4] == ([1,2],[3,4,1,2,3,4])
636 span (< 9) [1,2,3] == ([1,2,3],[])
637 span (< 0) [1,2,3] == ([],[1,2,3])
638 \end{verbatim}}
639 \end{quote}
640 \haddockid{span} \haddocktt{p\ xs} is equivalent to \haddocktt{(takeWhile\ p\ xs,\ dropWhile\ p\ xs)}
641 \par
642
643 \end{haddockdesc}
644 \begin{haddockdesc}
645 \item[\begin{tabular}{@{}l}
646 break\ ::\ (a\ ->\ Bool)\ ->\ {\char 91}a{\char 93}\ ->\ ({\char 91}a{\char 93},\ {\char 91}a{\char 93})
647 \end{tabular}]\haddockbegindoc
648 \haddockid{break}, applied to a predicate \haddocktt{p} and a list \haddocktt{xs}, returns a tuple where
649 first element is longest prefix (possibly empty) of \haddocktt{xs} of elements that
650 \emph{do not satisfy} \haddocktt{p} and second element is the remainder of the list:
651 \par
652 \begin{quote}
653 {\haddockverb\begin{verbatim}
654 break (> 3) [1,2,3,4,1,2,3,4] == ([1,2,3],[4,1,2,3,4])
655 break (< 9) [1,2,3] == ([],[1,2,3])
656 break (> 9) [1,2,3] == ([1,2,3],[])
657 \end{verbatim}}
658 \end{quote}
659 \haddockid{break} \haddocktt{p} is equivalent to \haddocktt{span\ (not\ .\ p)}.
660 \par
661
662 \end{haddockdesc}
663 \begin{haddockdesc}
664 \item[\begin{tabular}{@{}l}
665 stripPrefix\ ::\ Eq\ a\ =>\ {\char 91}a{\char 93}\ ->\ {\char 91}a{\char 93}\ ->\ Maybe\ {\char 91}a{\char 93}
666 \end{tabular}]\haddockbegindoc
667 The \haddockid{stripPrefix} function drops the given prefix from a list.
668 It returns \haddockid{Nothing} if the list did not start with the prefix
669 given, or \haddockid{Just} the list after the prefix, if it does.
670 \par
671 \begin{quote}
672 {\haddockverb\begin{verbatim}
673 stripPrefix "foo" "foobar" == Just "bar"
674 stripPrefix "foo" "foo" == Just ""
675 stripPrefix "foo" "barfoo" == Nothing
676 stripPrefix "foo" "barfoobaz" == Nothing
677 \end{verbatim}}
678 \end{quote}
679
680 \end{haddockdesc}
681 \begin{haddockdesc}
682 \item[\begin{tabular}{@{}l}
683 group\ ::\ Eq\ a\ =>\ {\char 91}a{\char 93}\ ->\ {\char 91}{\char 91}a{\char 93}{\char 93}
684 \end{tabular}]\haddockbegindoc
685 The \haddockid{group} function takes a list and returns a list of lists such
686 that the concatenation of the result is equal to the argument. Moreover,
687 each sublist in the result contains only equal elements. For example,
688 \par
689 \begin{quote}
690 {\haddockverb\begin{verbatim}
691 group "Mississippi" = ["M","i","ss","i","ss","i","pp","i"]
692 \end{verbatim}}
693 \end{quote}
694 It is a special case of \haddockid{groupBy}, which allows the programmer to supply
695 their own equality test.
696 \par
697
698 \end{haddockdesc}
699 \begin{haddockdesc}
700 \item[\begin{tabular}{@{}l}
701 inits\ ::\ {\char 91}a{\char 93}\ ->\ {\char 91}{\char 91}a{\char 93}{\char 93}
702 \end{tabular}]\haddockbegindoc
703 The \haddockid{inits} function returns all initial segments of the argument,
704 shortest first. For example,
705 \par
706 \begin{quote}
707 {\haddockverb\begin{verbatim}
708 inits "abc" == ["","a","ab","abc"]
709 \end{verbatim}}
710 \end{quote}
711
712 \end{haddockdesc}
713 \begin{haddockdesc}
714 \item[\begin{tabular}{@{}l}
715 tails\ ::\ {\char 91}a{\char 93}\ ->\ {\char 91}{\char 91}a{\char 93}{\char 93}
716 \end{tabular}]\haddockbegindoc
717 The \haddockid{tails} function returns all final segments of the argument,
718 longest first. For example,
719 \par
720 \begin{quote}
721 {\haddockverb\begin{verbatim}
722 tails "abc" == ["abc", "bc", "c",""]
723 \end{verbatim}}
724 \end{quote}
725
726 \end{haddockdesc}
727 \subsection{Predicates
728 }
729 \begin{haddockdesc}
730 \item[\begin{tabular}{@{}l}
731 isPrefixOf\ ::\ Eq\ a\ =>\ {\char 91}a{\char 93}\ ->\ {\char 91}a{\char 93}\ ->\ Bool
732 \end{tabular}]\haddockbegindoc
733 The \haddockid{isPrefixOf} function takes two lists and returns \haddockid{True}
734 iff the first list is a prefix of the second.
735 \par
736
737 \end{haddockdesc}
738 \begin{haddockdesc}
739 \item[\begin{tabular}{@{}l}
740 isSuffixOf\ ::\ Eq\ a\ =>\ {\char 91}a{\char 93}\ ->\ {\char 91}a{\char 93}\ ->\ Bool
741 \end{tabular}]\haddockbegindoc
742 The \haddockid{isSuffixOf} function takes two lists and returns \haddockid{True}
743 iff the first list is a suffix of the second.
744 Both lists must be finite.
745 \par
746
747 \end{haddockdesc}
748 \begin{haddockdesc}
749 \item[\begin{tabular}{@{}l}
750 isInfixOf\ ::\ Eq\ a\ =>\ {\char 91}a{\char 93}\ ->\ {\char 91}a{\char 93}\ ->\ Bool
751 \end{tabular}]\haddockbegindoc
752 The \haddockid{isInfixOf} function takes two lists and returns \haddockid{True}
753 iff the first list is contained, wholly and intact,
754 anywhere within the second.
755 \par
756 Example:
757 \par
758 \begin{quote}
759 {\haddockverb\begin{verbatim}
760 isInfixOf "Haskell" "I really like Haskell." == True
761 isInfixOf "Ial" "I really like Haskell." == False
762 \end{verbatim}}
763 \end{quote}
764
765 \end{haddockdesc}
766 \section{Searching lists
767 }
768 \subsection{Searching by equality
769 }
770 \begin{haddockdesc}
771 \item[\begin{tabular}{@{}l}
772 elem\ ::\ Eq\ a\ =>\ a\ ->\ {\char 91}a{\char 93}\ ->\ Bool
773 \end{tabular}]\haddockbegindoc
774 \haddockid{elem} is the list membership predicate, usually written in infix form,
775 e.g., \haddocktt{x\ `elem`\ xs}. For the result to be
776 \haddockid{False}, the list must be finite; \haddockid{True}, however, results from an element equal to \haddocktt{x} found at a finite index of a finite or infinite list.
777 \par
778
779 \end{haddockdesc}
780 \begin{haddockdesc}
781 \item[\begin{tabular}{@{}l}
782 notElem\ ::\ Eq\ a\ =>\ a\ ->\ {\char 91}a{\char 93}\ ->\ Bool
783 \end{tabular}]\haddockbegindoc
784 \haddockid{notElem} is the negation of \haddockid{elem}.
785 \par
786
787 \end{haddockdesc}
788 \begin{haddockdesc}
789 \item[\begin{tabular}{@{}l}
790 lookup\ ::\ Eq\ a\ =>\ a\ ->\ {\char 91}(a,\ b){\char 93}\ ->\ Maybe\ b
791 \end{tabular}]\haddockbegindoc
792 \haddockid{lookup} \haddocktt{key\ assocs} looks up a key in an association list.
793 \par
794
795 \end{haddockdesc}
796 \subsection{Searching with a predicate
797 }
798 \begin{haddockdesc}
799 \item[\begin{tabular}{@{}l}
800 find\ ::\ (a\ ->\ Bool)\ ->\ {\char 91}a{\char 93}\ ->\ Maybe\ a
801 \end{tabular}]\haddockbegindoc
802 The \haddockid{find} function takes a predicate and a list and returns the
803 first element in the list matching the predicate, or \haddockid{Nothing} if
804 there is no such element.
805 \par
806
807 \end{haddockdesc}
808 \begin{haddockdesc}
809 \item[\begin{tabular}{@{}l}
810 filter\ ::\ (a\ ->\ Bool)\ ->\ {\char 91}a{\char 93}\ ->\ {\char 91}a{\char 93}
811 \end{tabular}]\haddockbegindoc
812 \haddockid{filter}, applied to a predicate and a list, returns the list of
813 those elements that satisfy the predicate; i.e.,
814 \par
815 \begin{quote}
816 {\haddockverb\begin{verbatim}
817 filter p xs = [ x | x <- xs, p x]
818 \end{verbatim}}
819 \end{quote}
820
821 \end{haddockdesc}
822 \begin{haddockdesc}
823 \item[\begin{tabular}{@{}l}
824 partition\ ::\ (a\ ->\ Bool)\ ->\ {\char 91}a{\char 93}\ ->\ ({\char 91}a{\char 93},\ {\char 91}a{\char 93})
825 \end{tabular}]\haddockbegindoc
826 The \haddockid{partition} function takes a predicate a list and returns
827 the pair of lists of elements which do and do not satisfy the
828 predicate, respectively; i.e.,
829 \par
830 \begin{quote}
831 {\haddockverb\begin{verbatim}
832 partition p xs == (filter p xs, filter (not . p) xs)
833 \end{verbatim}}
834 \end{quote}
835
836 \end{haddockdesc}
837 \section{Indexing lists
838 }
839 These functions treat a list \haddocktt{xs} as a indexed collection,
840 with indices ranging from 0 to \haddocktt{length\ xs\ -\ 1}.
841 \par
842
843 \begin{haddockdesc}
844 \item[\begin{tabular}{@{}l}
845 (!!)\ ::\ {\char 91}a{\char 93}\ ->\ Int\ ->\ a
846 \end{tabular}]\haddockbegindoc
847 List index (subscript) operator, starting from 0.
848 It is an instance of the more general \haddocktt{Data.List.genericIndex},
849 which takes an index of any integral type.
850 \par
851
852 \end{haddockdesc}
853 \begin{haddockdesc}
854 \item[\begin{tabular}{@{}l}
855 elemIndex\ ::\ Eq\ a\ =>\ a\ ->\ {\char 91}a{\char 93}\ ->\ Maybe\ Int
856 \end{tabular}]\haddockbegindoc
857 The \haddockid{elemIndex} function returns the index of the first element
858 in the given list which is equal (by \haddockid{==}) to the query element,
859 or \haddockid{Nothing} if there is no such element.
860 \par
861
862 \end{haddockdesc}
863 \begin{haddockdesc}
864 \item[\begin{tabular}{@{}l}
865 elemIndices\ ::\ Eq\ a\ =>\ a\ ->\ {\char 91}a{\char 93}\ ->\ {\char 91}Int{\char 93}
866 \end{tabular}]\haddockbegindoc
867 The \haddockid{elemIndices} function extends \haddockid{elemIndex}, by returning the
868 indices of all elements equal to the query element, in ascending order.
869 \par
870
871 \end{haddockdesc}
872 \begin{haddockdesc}
873 \item[\begin{tabular}{@{}l}
874 findIndex\ ::\ (a\ ->\ Bool)\ ->\ {\char 91}a{\char 93}\ ->\ Maybe\ Int
875 \end{tabular}]\haddockbegindoc
876 The \haddockid{findIndex} function takes a predicate and a list and returns
877 the index of the first element in the list satisfying the predicate,
878 or \haddockid{Nothing} if there is no such element.
879 \par
880
881 \end{haddockdesc}
882 \begin{haddockdesc}
883 \item[\begin{tabular}{@{}l}
884 findIndices\ ::\ (a\ ->\ Bool)\ ->\ {\char 91}a{\char 93}\ ->\ {\char 91}Int{\char 93}
885 \end{tabular}]\haddockbegindoc
886 The \haddockid{findIndices} function extends \haddockid{findIndex}, by returning the
887 indices of all elements satisfying the predicate, in ascending order.
888 \par
889
890 \end{haddockdesc}
891 \section{Zipping and unzipping lists
892 }
893 \begin{haddockdesc}
894 \item[\begin{tabular}{@{}l}
895 zip\ ::\ {\char 91}a{\char 93}\ ->\ {\char 91}b{\char 93}\ ->\ {\char 91}(a,\ b){\char 93}
896 \end{tabular}]\haddockbegindoc
897 \haddockid{zip} takes two lists and returns a list of corresponding pairs.
898 If one input list is short, excess elements of the longer list are
899 discarded.
900 \par
901
902 \end{haddockdesc}
903 \begin{haddockdesc}
904 \item[\begin{tabular}{@{}l}
905 zip3\ ::\ {\char 91}a{\char 93}\ ->\ {\char 91}b{\char 93}\ ->\ {\char 91}c{\char 93}\ ->\ {\char 91}(a,\ b,\ c){\char 93}
906 \end{tabular}]\haddockbegindoc
907 \haddockid{zip3} takes three lists and returns a list of triples, analogous to
908 \haddockid{zip}.
909 \par
910
911 \end{haddockdesc}
912 \begin{haddockdesc}
913 \item[\begin{tabular}{@{}l}
914 zip4\ ::\ {\char 91}a{\char 93}\ ->\ {\char 91}b{\char 93}\ ->\ {\char 91}c{\char 93}\ ->\ {\char 91}d{\char 93}\ ->\ {\char 91}(a,\ b,\ c,\ d){\char 93}
915 \end{tabular}]\haddockbegindoc
916 The \haddockid{zip4} function takes four lists and returns a list of
917 quadruples, analogous to \haddockid{zip}.
918 \par
919
920 \end{haddockdesc}
921 \begin{haddockdesc}
922 \item[\begin{tabular}{@{}l}
923 zip5\ ::\ {\char 91}a{\char 93}\ ->\ {\char 91}b{\char 93}\ ->\ {\char 91}c{\char 93}\ ->\ {\char 91}d{\char 93}\ ->\ {\char 91}e{\char 93}\ ->\ {\char 91}(a,\ b,\ c,\ d,\ e){\char 93}
924 \end{tabular}]\haddockbegindoc
925 The \haddockid{zip5} function takes five lists and returns a list of
926 five-tuples, analogous to \haddockid{zip}.
927 \par
928
929 \end{haddockdesc}
930 \begin{haddockdesc}
931 \item[\begin{tabular}{@{}l}
932 zip6\ ::\ {\char 91}a{\char 93}\\\ \ \ \ \ \ \ \ ->\ {\char 91}b{\char 93}\ ->\ {\char 91}c{\char 93}\ ->\ {\char 91}d{\char 93}\ ->\ {\char 91}e{\char 93}\ ->\ {\char 91}f{\char 93}\ ->\ {\char 91}(a,\ b,\ c,\ d,\ e,\ f){\char 93}
933 \end{tabular}]\haddockbegindoc
934 The \haddockid{zip6} function takes six lists and returns a list of six-tuples,
935 analogous to \haddockid{zip}.
936 \par
937
938 \end{haddockdesc}
939 \begin{haddockdesc}
940 \item[\begin{tabular}{@{}l}
941 zip7\ ::\ {\char 91}a{\char 93}\\\ \ \ \ \ \ \ \ ->\ {\char 91}b{\char 93}\\\ \ \ \ \ \ \ \ \ \ \ ->\ {\char 91}c{\char 93}\ ->\ {\char 91}d{\char 93}\ ->\ {\char 91}e{\char 93}\ ->\ {\char 91}f{\char 93}\ ->\ {\char 91}g{\char 93}\ ->\ {\char 91}(a,\ b,\ c,\ d,\ e,\ f,\ g){\char 93}
942 \end{tabular}]\haddockbegindoc
943 The \haddockid{zip7} function takes seven lists and returns a list of
944 seven-tuples, analogous to \haddockid{zip}.
945 \par
946
947 \end{haddockdesc}
948 \begin{haddockdesc}
949 \item[\begin{tabular}{@{}l}
950 zipWith\ ::\ (a\ ->\ b\ ->\ c)\ ->\ {\char 91}a{\char 93}\ ->\ {\char 91}b{\char 93}\ ->\ {\char 91}c{\char 93}
951 \end{tabular}]\haddockbegindoc
952 \haddockid{zipWith} generalises \haddockid{zip} by zipping with the function given
953 as the first argument, instead of a tupling function.
954 For example, \haddocktt{zipWith\ (+)} is applied to two lists to produce the
955 list of corresponding sums.
956 \par
957
958 \end{haddockdesc}
959 \begin{haddockdesc}
960 \item[\begin{tabular}{@{}l}
961 zipWith3\ ::\ (a\ ->\ b\ ->\ c\ ->\ d)\ ->\ {\char 91}a{\char 93}\ ->\ {\char 91}b{\char 93}\ ->\ {\char 91}c{\char 93}\ ->\ {\char 91}d{\char 93}
962 \end{tabular}]\haddockbegindoc
963 The \haddockid{zipWith3} function takes a function which combines three
964 elements, as well as three lists and returns a list of their point-wise
965 combination, analogous to \haddockid{zipWith}.
966 \par
967
968 \end{haddockdesc}
969 \begin{haddockdesc}
970 \item[\begin{tabular}{@{}l}
971 zipWith4\ ::\ (a\ ->\ b\ ->\ c\ ->\ d\ ->\ e)\\\ \ \ \ \ \ \ \ \ \ \ \ ->\ {\char 91}a{\char 93}\ ->\ {\char 91}b{\char 93}\ ->\ {\char 91}c{\char 93}\ ->\ {\char 91}d{\char 93}\ ->\ {\char 91}e{\char 93}
972 \end{tabular}]\haddockbegindoc
973 The \haddockid{zipWith4} function takes a function which combines four
974 elements, as well as four lists and returns a list of their point-wise
975 combination, analogous to \haddockid{zipWith}.
976 \par
977
978 \end{haddockdesc}
979 \begin{haddockdesc}
980 \item[\begin{tabular}{@{}l}
981 zipWith5\ ::\ (a\ ->\ b\ ->\ c\ ->\ d\ ->\ e\ ->\ f)\\\ \ \ \ \ \ \ \ \ \ \ \ ->\ {\char 91}a{\char 93}\ ->\ {\char 91}b{\char 93}\ ->\ {\char 91}c{\char 93}\ ->\ {\char 91}d{\char 93}\ ->\ {\char 91}e{\char 93}\ ->\ {\char 91}f{\char 93}
982 \end{tabular}]\haddockbegindoc
983 The \haddockid{zipWith5} function takes a function which combines five
984 elements, as well as five lists and returns a list of their point-wise
985 combination, analogous to \haddockid{zipWith}.
986 \par
987
988 \end{haddockdesc}
989 \begin{haddockdesc}
990 \item[\begin{tabular}{@{}l}
991 zipWith6\ ::\ (a\ ->\ b\ ->\ c\ ->\ d\ ->\ e\ ->\ f\ ->\ g)\\\ \ \ \ \ \ \ \ \ \ \ \ ->\ {\char 91}a{\char 93}\ ->\ {\char 91}b{\char 93}\ ->\ {\char 91}c{\char 93}\ ->\ {\char 91}d{\char 93}\ ->\ {\char 91}e{\char 93}\ ->\ {\char 91}f{\char 93}\ ->\ {\char 91}g{\char 93}
992 \end{tabular}]\haddockbegindoc
993 The \haddockid{zipWith6} function takes a function which combines six
994 elements, as well as six lists and returns a list of their point-wise
995 combination, analogous to \haddockid{zipWith}.
996 \par
997
998 \end{haddockdesc}
999 \begin{haddockdesc}
1000 \item[\begin{tabular}{@{}l}
1001 zipWith7\ ::\ (a\ ->\ b\ ->\ c\ ->\ d\ ->\ e\ ->\ f\ ->\ g\ ->\ h)\\\ \ \ \ \ \ \ \ \ \ \ \ ->\ {\char 91}a{\char 93}\ ->\ {\char 91}b{\char 93}\ ->\ {\char 91}c{\char 93}\ ->\ {\char 91}d{\char 93}\ ->\ {\char 91}e{\char 93}\ ->\ {\char 91}f{\char 93}\ ->\ {\char 91}g{\char 93}\ ->\ {\char 91}h{\char 93}
1002 \end{tabular}]\haddockbegindoc
1003 The \haddockid{zipWith7} function takes a function which combines seven
1004 elements, as well as seven lists and returns a list of their point-wise
1005 combination, analogous to \haddockid{zipWith}.
1006 \par
1007
1008 \end{haddockdesc}
1009 \begin{haddockdesc}
1010 \item[\begin{tabular}{@{}l}
1011 unzip\ ::\ {\char 91}(a,\ b){\char 93}\ ->\ ({\char 91}a{\char 93},\ {\char 91}b{\char 93})
1012 \end{tabular}]\haddockbegindoc
1013 \haddockid{unzip} transforms a list of pairs into a list of first components
1014 and a list of second components.
1015 \par
1016
1017 \end{haddockdesc}
1018 \begin{haddockdesc}
1019 \item[\begin{tabular}{@{}l}
1020 unzip3\ ::\ {\char 91}(a,\ b,\ c){\char 93}\ ->\ ({\char 91}a{\char 93},\ {\char 91}b{\char 93},\ {\char 91}c{\char 93})
1021 \end{tabular}]\haddockbegindoc
1022 The \haddockid{unzip3} function takes a list of triples and returns three
1023 lists, analogous to \haddockid{unzip}.
1024 \par
1025
1026 \end{haddockdesc}
1027 \begin{haddockdesc}
1028 \item[\begin{tabular}{@{}l}
1029 unzip4\ ::\ {\char 91}(a,\ b,\ c,\ d){\char 93}\ ->\ ({\char 91}a{\char 93},\ {\char 91}b{\char 93},\ {\char 91}c{\char 93},\ {\char 91}d{\char 93})
1030 \end{tabular}]\haddockbegindoc
1031 The \haddockid{unzip4} function takes a list of quadruples and returns four
1032 lists, analogous to \haddockid{unzip}.
1033 \par
1034
1035 \end{haddockdesc}
1036 \begin{haddockdesc}
1037 \item[\begin{tabular}{@{}l}
1038 unzip5\ ::\ {\char 91}(a,\ b,\ c,\ d,\ e){\char 93}\ ->\ ({\char 91}a{\char 93},\ {\char 91}b{\char 93},\ {\char 91}c{\char 93},\ {\char 91}d{\char 93},\ {\char 91}e{\char 93})
1039 \end{tabular}]\haddockbegindoc
1040 The \haddockid{unzip5} function takes a list of five-tuples and returns five
1041 lists, analogous to \haddockid{unzip}.
1042 \par
1043
1044 \end{haddockdesc}
1045 \begin{haddockdesc}
1046 \item[\begin{tabular}{@{}l}
1047 unzip6\ ::\ {\char 91}(a,\ b,\ c,\ d,\ e,\ f){\char 93}\ ->\ ({\char 91}a{\char 93},\ {\char 91}b{\char 93},\ {\char 91}c{\char 93},\ {\char 91}d{\char 93},\ {\char 91}e{\char 93},\ {\char 91}f{\char 93})
1048 \end{tabular}]\haddockbegindoc
1049 The \haddockid{unzip6} function takes a list of six-tuples and returns six
1050 lists, analogous to \haddockid{unzip}.
1051 \par
1052
1053 \end{haddockdesc}
1054 \begin{haddockdesc}
1055 \item[\begin{tabular}{@{}l}
1056 unzip7\ ::\ {\char 91}(a,\ b,\ c,\ d,\ e,\ f,\ g){\char 93}\\\ \ \ \ \ \ \ \ \ \ ->\ ({\char 91}a{\char 93},\ {\char 91}b{\char 93},\ {\char 91}c{\char 93},\ {\char 91}d{\char 93},\ {\char 91}e{\char 93},\ {\char 91}f{\char 93},\ {\char 91}g{\char 93})
1057 \end{tabular}]\haddockbegindoc
1058 The \haddockid{unzip7} function takes a list of seven-tuples and returns
1059 seven lists, analogous to \haddockid{unzip}.
1060 \par
1061
1062 \end{haddockdesc}
1063 \section{Special lists
1064 }
1065 \subsection{Functions on strings
1066 }
1067 \begin{haddockdesc}
1068 \item[\begin{tabular}{@{}l}
1069 lines\ ::\ String\ ->\ {\char 91}String{\char 93}
1070 \end{tabular}]\haddockbegindoc
1071 \haddockid{lines} breaks a string up into a list of strings at newline
1072 characters. The resulting strings do not contain newlines.
1073 \par
1074
1075 \end{haddockdesc}
1076 \begin{haddockdesc}
1077 \item[\begin{tabular}{@{}l}
1078 words\ ::\ String\ ->\ {\char 91}String{\char 93}
1079 \end{tabular}]\haddockbegindoc
1080 \haddockid{words} breaks a string up into a list of words, which were delimited
1081 by white space.
1082 \par
1083
1084 \end{haddockdesc}
1085 \begin{haddockdesc}
1086 \item[\begin{tabular}{@{}l}
1087 unlines\ ::\ {\char 91}String{\char 93}\ ->\ String
1088 \end{tabular}]\haddockbegindoc
1089 \haddockid{unlines} is an inverse operation to \haddockid{lines}.
1090 It joins lines, after appending a terminating newline to each.
1091 \par
1092
1093 \end{haddockdesc}
1094 \begin{haddockdesc}
1095 \item[\begin{tabular}{@{}l}
1096 unwords\ ::\ {\char 91}String{\char 93}\ ->\ String
1097 \end{tabular}]\haddockbegindoc
1098 \haddockid{unwords} is an inverse operation to \haddockid{words}.
1099 It joins words with separating spaces.
1100 \par
1101
1102 \end{haddockdesc}
1103 \subsection{"Set" operations
1104 }
1105 \begin{haddockdesc}
1106 \item[\begin{tabular}{@{}l}
1107 nub\ ::\ Eq\ a\ =>\ {\char 91}a{\char 93}\ ->\ {\char 91}a{\char 93}
1108 \end{tabular}]\haddockbegindoc
1109 \emph{O(n{\char '136}2)}. The \haddockid{nub} function removes duplicate elements from a list.
1110 In particular, it keeps only the first occurrence of each element.
1111 (The name \haddockid{nub} means `essence'.)
1112 It is a special case of \haddockid{nubBy}, which allows the programmer to supply
1113 their own equality test.
1114 \par
1115
1116 \end{haddockdesc}
1117 \begin{haddockdesc}
1118 \item[\begin{tabular}{@{}l}
1119 delete\ ::\ Eq\ a\ =>\ a\ ->\ {\char 91}a{\char 93}\ ->\ {\char 91}a{\char 93}
1120 \end{tabular}]\haddockbegindoc
1121 \haddockid{delete} \haddocktt{x} removes the first occurrence of \haddocktt{x} from its list argument.
1122 For example,
1123 \par
1124 \begin{quote}
1125 {\haddockverb\begin{verbatim}
1126 delete 'a' "banana" == "bnana"
1127 \end{verbatim}}
1128 \end{quote}
1129 It is a special case of \haddockid{deleteBy}, which allows the programmer to
1130 supply their own equality test.
1131 \par
1132
1133 \end{haddockdesc}
1134 \begin{haddockdesc}
1135 \item[\begin{tabular}{@{}l}
1136 ({\char '134}{\char '134})\ ::\ Eq\ a\ =>\ {\char 91}a{\char 93}\ ->\ {\char 91}a{\char 93}\ ->\ {\char 91}a{\char 93}
1137 \end{tabular}]\haddockbegindoc
1138 The \haddockid{{\char '134}{\char '134}} function is list difference ((non-associative).
1139 In the result of \haddocktt{xs} \haddockid{{\char '134}{\char '134}} \haddocktt{ys}, the first occurrence of each element of
1140 \haddocktt{ys} in turn (if any) has been removed from \haddocktt{xs}. Thus
1141 \par
1142 \begin{quote}
1143 {\haddockverb\begin{verbatim}
1144 (xs ++ ys) \\ xs == ys.
1145 \end{verbatim}}
1146 \end{quote}
1147 It is a special case of \haddockid{deleteFirstsBy}, which allows the programmer
1148 to supply their own equality test.
1149 \par
1150
1151 \end{haddockdesc}
1152 \begin{haddockdesc}
1153 \item[\begin{tabular}{@{}l}
1154 union\ ::\ Eq\ a\ =>\ {\char 91}a{\char 93}\ ->\ {\char 91}a{\char 93}\ ->\ {\char 91}a{\char 93}
1155 \end{tabular}]\haddockbegindoc
1156 The \haddockid{union} function returns the list union of the two lists.
1157 For example,
1158 \par
1159 \begin{quote}
1160 {\haddockverb\begin{verbatim}
1161 "dog" `union` "cow" == "dogcw"
1162 \end{verbatim}}
1163 \end{quote}
1164 Duplicates, and elements of the first list, are removed from the
1165 the second list, but if the first list contains duplicates, so will
1166 the result.
1167 It is a special case of \haddockid{unionBy}, which allows the programmer to supply
1168 their own equality test.
1169 \par
1170
1171 \end{haddockdesc}
1172 \begin{haddockdesc}
1173 \item[\begin{tabular}{@{}l}
1174 intersect\ ::\ Eq\ a\ =>\ {\char 91}a{\char 93}\ ->\ {\char 91}a{\char 93}\ ->\ {\char 91}a{\char 93}
1175 \end{tabular}]\haddockbegindoc
1176 The \haddockid{intersect} function takes the list intersection of two lists.
1177 For example,
1178 \par
1179 \begin{quote}
1180 {\haddockverb\begin{verbatim}
1181 [1,2,3,4] `intersect` [2,4,6,8] == [2,4]
1182 \end{verbatim}}
1183 \end{quote}
1184 If the first list contains duplicates, so will the result.
1185 \par
1186 \begin{quote}
1187 {\haddockverb\begin{verbatim}
1188 [1,2,2,3,4] `intersect` [6,4,4,2] == [2,2,4]
1189 \end{verbatim}}
1190 \end{quote}
1191 It is a special case of \haddockid{intersectBy}, which allows the programmer to
1192 supply their own equality test.
1193 \par
1194
1195 \end{haddockdesc}
1196 \subsection{Ordered lists
1197 }
1198 \begin{haddockdesc}
1199 \item[\begin{tabular}{@{}l}
1200 sort\ ::\ Ord\ a\ =>\ {\char 91}a{\char 93}\ ->\ {\char 91}a{\char 93}
1201 \end{tabular}]\haddockbegindoc
1202 The \haddockid{sort} function implements a stable sorting algorithm.
1203 It is a special case of \haddockid{sortBy}, which allows the programmer to supply
1204 their own comparison function.
1205 \par
1206
1207 \end{haddockdesc}
1208 \begin{haddockdesc}
1209 \item[\begin{tabular}{@{}l}
1210 insert\ ::\ Ord\ a\ =>\ a\ ->\ {\char 91}a{\char 93}\ ->\ {\char 91}a{\char 93}
1211 \end{tabular}]\haddockbegindoc
1212 The \haddockid{insert} function takes an element and a list and inserts the
1213 element into the list at the last position where it is still less
1214 than or equal to the next element. In particular, if the list
1215 is sorted before the call, the result will also be sorted.
1216 It is a special case of \haddockid{insertBy}, which allows the programmer to
1217 supply their own comparison function.
1218 \par
1219
1220 \end{haddockdesc}
1221 \section{Generalized functions
1222 }
1223 \subsection{The "\haddocktt{By}" operations
1224 }
1225 By convention, overloaded functions have a non-overloaded
1226 counterpart whose name is suffixed with `\haddocktt{By}'.
1227 \par
1228
1229 \subsubsection{User-supplied equality (replacing an \haddocktt{Eq} context)
1230 }
1231 The predicate is assumed to define an equivalence.
1232 \par
1233
1234 \begin{haddockdesc}
1235 \item[\begin{tabular}{@{}l}
1236 nubBy\ ::\ (a\ ->\ a\ ->\ Bool)\ ->\ {\char 91}a{\char 93}\ ->\ {\char 91}a{\char 93}
1237 \end{tabular}]\haddockbegindoc
1238 The \haddockid{nubBy} function behaves just like \haddockid{nub}, except it uses a
1239 user-supplied equality predicate instead of the overloaded \haddockid{==}
1240 function.
1241 \par
1242
1243 \end{haddockdesc}
1244 \begin{haddockdesc}
1245 \item[\begin{tabular}{@{}l}
1246 deleteBy\ ::\ (a\ ->\ a\ ->\ Bool)\ ->\ a\ ->\ {\char 91}a{\char 93}\ ->\ {\char 91}a{\char 93}
1247 \end{tabular}]\haddockbegindoc
1248 The \haddockid{deleteBy} function behaves like \haddockid{delete}, but takes a
1249 user-supplied equality predicate.
1250 \par
1251
1252 \end{haddockdesc}
1253 \begin{haddockdesc}
1254 \item[\begin{tabular}{@{}l}
1255 deleteFirstsBy\ ::\ (a\ ->\ a\ ->\ Bool)\ ->\ {\char 91}a{\char 93}\ ->\ {\char 91}a{\char 93}\ ->\ {\char 91}a{\char 93}
1256 \end{tabular}]\haddockbegindoc
1257 The \haddockid{deleteFirstsBy} function takes a predicate and two lists and
1258 returns the first list with the first occurrence of each element of
1259 the second list removed.
1260 \par
1261
1262 \end{haddockdesc}
1263 \begin{haddockdesc}
1264 \item[\begin{tabular}{@{}l}
1265 unionBy\ ::\ (a\ ->\ a\ ->\ Bool)\ ->\ {\char 91}a{\char 93}\ ->\ {\char 91}a{\char 93}\ ->\ {\char 91}a{\char 93}
1266 \end{tabular}]\haddockbegindoc
1267 The \haddockid{unionBy} function is the non-overloaded version of \haddockid{union}.
1268 \par
1269
1270 \end{haddockdesc}
1271 \begin{haddockdesc}
1272 \item[\begin{tabular}{@{}l}
1273 intersectBy\ ::\ (a\ ->\ a\ ->\ Bool)\ ->\ {\char 91}a{\char 93}\ ->\ {\char 91}a{\char 93}\ ->\ {\char 91}a{\char 93}
1274 \end{tabular}]\haddockbegindoc
1275 The \haddockid{intersectBy} function is the non-overloaded version of \haddockid{intersect}.
1276 \par
1277
1278 \end{haddockdesc}
1279 \begin{haddockdesc}
1280 \item[\begin{tabular}{@{}l}
1281 groupBy\ ::\ (a\ ->\ a\ ->\ Bool)\ ->\ {\char 91}a{\char 93}\ ->\ {\char 91}{\char 91}a{\char 93}{\char 93}
1282 \end{tabular}]\haddockbegindoc
1283 The \haddockid{groupBy} function is the non-overloaded version of \haddockid{group}.
1284 \par
1285
1286 \end{haddockdesc}
1287 \subsubsection{User-supplied comparison (replacing an \haddocktt{Ord} context)
1288 }
1289 The function is assumed to define a total ordering.
1290 \par
1291
1292 \begin{haddockdesc}
1293 \item[\begin{tabular}{@{}l}
1294 sortBy\ ::\ (a\ ->\ a\ ->\ Ordering)\ ->\ {\char 91}a{\char 93}\ ->\ {\char 91}a{\char 93}
1295 \end{tabular}]\haddockbegindoc
1296 The \haddockid{sortBy} function is the non-overloaded version of \haddockid{sort}.
1297 \par
1298
1299 \end{haddockdesc}
1300 \begin{haddockdesc}
1301 \item[\begin{tabular}{@{}l}
1302 insertBy\ ::\ (a\ ->\ a\ ->\ Ordering)\ ->\ a\ ->\ {\char 91}a{\char 93}\ ->\ {\char 91}a{\char 93}
1303 \end{tabular}]\haddockbegindoc
1304 The non-overloaded version of \haddockid{insert}.
1305 \par
1306
1307 \end{haddockdesc}
1308 \begin{haddockdesc}
1309 \item[\begin{tabular}{@{}l}
1310 maximumBy\ ::\ (a\ ->\ a\ ->\ Ordering)\ ->\ {\char 91}a{\char 93}\ ->\ a
1311 \end{tabular}]\haddockbegindoc
1312 The \haddockid{maximumBy} function takes a comparison function and a list
1313 and returns the greatest element of the list by the comparison function.
1314 The list must be finite and non-empty.
1315 \par
1316
1317 \end{haddockdesc}
1318 \begin{haddockdesc}
1319 \item[\begin{tabular}{@{}l}
1320 minimumBy\ ::\ (a\ ->\ a\ ->\ Ordering)\ ->\ {\char 91}a{\char 93}\ ->\ a
1321 \end{tabular}]\haddockbegindoc
1322 The \haddockid{minimumBy} function takes a comparison function and a list
1323 and returns the least element of the list by the comparison function.
1324 The list must be finite and non-empty.
1325 \par
1326
1327 \end{haddockdesc}
1328 \subsection{The "\haddocktt{generic}" operations
1329 }
1330 The prefix `\haddocktt{generic}' indicates an overloaded function that
1331 is a generalized version of a \haddocktt{Prelude} function.
1332 \par
1333
1334 \begin{haddockdesc}
1335 \item[\begin{tabular}{@{}l}
1336 genericLength\ ::\ Num\ i\ =>\ {\char 91}b{\char 93}\ ->\ i
1337 \end{tabular}]\haddockbegindoc
1338 The \haddockid{genericLength} function is an overloaded version of \haddockid{length}. In
1339 particular, instead of returning an \haddockid{Int}, it returns any type which is
1340 an instance of \haddockid{Num}. It is, however, less efficient than \haddockid{length}.
1341 \par
1342
1343 \end{haddockdesc}
1344 \begin{haddockdesc}
1345 \item[\begin{tabular}{@{}l}
1346 genericTake\ ::\ Integral\ i\ =>\ i\ ->\ {\char 91}a{\char 93}\ ->\ {\char 91}a{\char 93}
1347 \end{tabular}]\haddockbegindoc
1348 The \haddockid{genericTake} function is an overloaded version of \haddockid{take}, which
1349 accepts any \haddockid{Integral} value as the number of elements to take.
1350 \par
1351
1352 \end{haddockdesc}
1353 \begin{haddockdesc}
1354 \item[\begin{tabular}{@{}l}
1355 genericDrop\ ::\ Integral\ i\ =>\ i\ ->\ {\char 91}a{\char 93}\ ->\ {\char 91}a{\char 93}
1356 \end{tabular}]\haddockbegindoc
1357 The \haddockid{genericDrop} function is an overloaded version of \haddockid{drop}, which
1358 accepts any \haddockid{Integral} value as the number of elements to drop.
1359 \par
1360
1361 \end{haddockdesc}
1362 \begin{haddockdesc}
1363 \item[\begin{tabular}{@{}l}
1364 genericSplitAt\ ::\ Integral\ i\ =>\ i\ ->\ {\char 91}b{\char 93}\ ->\ ({\char 91}b{\char 93},\ {\char 91}b{\char 93})
1365 \end{tabular}]\haddockbegindoc
1366 The \haddockid{genericSplitAt} function is an overloaded version of \haddockid{splitAt}, which
1367 accepts any \haddockid{Integral} value as the position at which to split.
1368 \par
1369
1370 \end{haddockdesc}
1371 \begin{haddockdesc}
1372 \item[\begin{tabular}{@{}l}
1373 genericIndex\ ::\ Integral\ a\ =>\ {\char 91}b{\char 93}\ ->\ a\ ->\ b
1374 \end{tabular}]\haddockbegindoc
1375 The \haddockid{genericIndex} function is an overloaded version of \haddockid{!!}, which
1376 accepts any \haddockid{Integral} value as the index.
1377 \par
1378
1379 \end{haddockdesc}
1380 \begin{haddockdesc}
1381 \item[\begin{tabular}{@{}l}
1382 genericReplicate\ ::\ Integral\ i\ =>\ i\ ->\ a\ ->\ {\char 91}a{\char 93}
1383 \end{tabular}]\haddockbegindoc
1384 The \haddockid{genericReplicate} function is an overloaded version of \haddockid{replicate},
1385 which accepts any \haddockid{Integral} value as the number of repetitions to make.
1386 \par
1387
1388 \end{haddockdesc}