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