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