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