2 % (c) The AQUA Project, Glasgow University, 1994-1996
5 \section[List]{Module @Lhar@}
10 This list follows the type signatures for the
11 standard List interface.
13 elemIndex, elemIndices,
14 find, findIndex, findIndices,
16 delete, deleteBy, (\\), deleteFirstsBy,
18 intersect, intersectBy,
21 isPrefixOf, isSuffixOf,
22 intersperse, transpose, partition,
27 genericTake, genericDrop, genericSplitAt,
28 genericIndex, genericReplicate, genericLength,
30 zip4, zip5, zip6, zip7,
31 zipWith4, zipWith5, zipWith6, zipWith7,
32 unzip4, unzip5, unzip6, unzip7
37 import Maybe (listToMaybe)
42 %*********************************************************
44 \subsection{List functions}
46 %*********************************************************
49 elemIndex :: Eq a => a -> [a] -> Maybe Int
50 elemIndex x = findIndex (x==)
52 elemIndices :: Eq a => a -> [a] -> [Int]
53 elemIndices x = findIndices (x==)
55 find :: (a -> Bool) -> [a] -> Maybe a
56 find p = listToMaybe . filter p
58 findIndex :: (a -> Bool) -> [a] -> Maybe Int
59 findIndex p = listToMaybe . findIndices p
61 findIndices :: (a -> Bool) -> [a] -> [Int]
62 findIndices p xs = [ i | (x,i) <- zip xs [0..], p x]
64 isPrefixOf :: (Eq a) => [a] -> [a] -> Bool
65 isPrefixOf [] _ = True
66 isPrefixOf _ [] = False
67 isPrefixOf (x:xs) (y:ys)= x == y && isPrefixOf xs ys
69 isSuffixOf :: (Eq a) => [a] -> [a] -> Bool
70 isSuffixOf x y = reverse x `isPrefixOf` reverse y
72 -- nub (meaning "essence") remove duplicate elements from its list argument.
73 nub :: (Eq a) => [a] -> [a]
74 #ifdef USE_REPORT_PRELUDE
81 nub' (x:xs) l = if x `elem` l then nub' xs l else x : nub' xs (x:l)
84 nubBy :: (a -> a -> Bool) -> [a] -> [a]
85 #ifdef USE_REPORT_PRELUDE
87 nubBy eq (x:xs) = x : nubBy eq (filter (\ y -> not (eq x y)) xs)
89 nubBy eq l = nubBy' l []
92 nubBy' (x:xs) l = if elemBy eq x l then nubBy' xs l else x : nubBy' xs (x:l)
95 elemBy :: (a -> a -> Bool) -> a -> [a] -> Bool
96 elemBy eq _ [] = False
97 elemBy eq x (y:ys) = x `eq` y || elemBy eq x ys
101 -- delete x removes the first occurrence of x from its list argument.
102 delete :: (Eq a) => a -> [a] -> [a]
103 delete = deleteBy (==)
105 deleteBy :: (a -> a -> Bool) -> a -> [a] -> [a]
106 deleteBy eq x [] = []
107 deleteBy eq x (y:ys) = if x `eq` y then ys else y : deleteBy eq x ys
109 -- list difference (non-associative). In the result of xs \\ ys,
110 -- the first occurrence of each element of ys in turn (if any)
111 -- has been removed from xs. Thus, (xs ++ ys) \\ xs == ys.
112 (\\) :: (Eq a) => [a] -> [a] -> [a]
113 (\\) = foldl (flip delete)
115 -- List union, remove the elements of first list from second.
116 union :: (Eq a) => [a] -> [a] -> [a]
119 unionBy :: (a -> a -> Bool) -> [a] -> [a] -> [a]
120 unionBy eq xs ys = xs ++ foldl (flip (deleteBy eq)) ys xs
122 intersect :: (Eq a) => [a] -> [a] -> [a]
123 intersect = intersectBy (==)
125 intersectBy :: (a -> a -> Bool) -> [a] -> [a] -> [a]
126 intersectBy eq xs ys = [x | x <- xs, any (eq x) ys]
128 -- intersperse sep inserts sep between the elements of its list argument.
129 -- e.g. intersperse ',' "abcde" == "a,b,c,d,e"
130 intersperse :: a -> [a] -> [a]
131 intersperse sep [] = []
132 intersperse sep [x] = [x]
133 intersperse sep (x:xs) = x : sep : intersperse sep xs
135 transpose :: [[a]] -> [[a]]
137 (\xs xss -> zipWith (:) xs (xss ++ repeat []))
141 -- partition takes a predicate and a list and returns a pair of lists:
142 -- those elements of the argument list that do and do not satisfy the
143 -- predicate, respectively; i,e,,
144 -- partition p xs == (filter p xs, filter (not . p) xs).
145 partition :: (a -> Bool) -> [a] -> ([a],[a])
146 partition p xs = foldr select ([],[]) xs
147 where select x (ts,fs) | p x = (x:ts,fs)
148 | otherwise = (ts, x:fs)
151 @mapAccumL@ behaves like a combination
152 of @map@ and @foldl@;
153 it applies a function to each element of a list, passing an accumulating
154 parameter from left to right, and returning a final value of this
155 accumulator together with the new list.
159 mapAccumL :: (acc -> x -> (acc, y)) -- Function of elt of input list
160 -- and accumulator, returning new
161 -- accumulator and elt of result list
162 -> acc -- Initial accumulator
164 -> (acc, [y]) -- Final accumulator and result list
165 mapAccumL f s [] = (s, [])
166 mapAccumL f s (x:xs) = (s'',y:ys)
167 where (s', y ) = f s x
168 (s'',ys) = mapAccumL f s' xs
171 @mapAccumR@ does the same, but working from right to left instead. Its type is
172 the same as @mapAccumL@, though.
175 mapAccumR :: (acc -> x -> (acc, y)) -- Function of elt of input list
176 -- and accumulator, returning new
177 -- accumulator and elt of result list
178 -> acc -- Initial accumulator
180 -> (acc, [y]) -- Final accumulator and result list
181 mapAccumR f s [] = (s, [])
182 mapAccumR f s (x:xs) = (s'', y:ys)
183 where (s'',y ) = f s' x
184 (s', ys) = mapAccumR f s xs
188 sort :: (Ord a) => [a] -> [a]
189 sort = sortBy compare
191 sortBy :: (a -> a -> Ordering) -> [a] -> [a]
192 sortBy cmp = foldr (insertBy cmp) []
194 insertBy :: (a -> a -> Ordering) -> a -> [a] -> [a]
195 insertBy cmp x [] = [x]
196 insertBy cmp x ys@(y:ys')
198 GT -> y : insertBy cmp x ys'
201 maximumBy :: (a -> a -> a) -> [a] -> a
202 maximumBy max [] = error "List.maximumBy: empty list"
203 maximumBy max xs = foldl1 max xs
205 minimumBy :: (a -> a -> a) -> [a] -> a
206 minimumBy min [] = error "List.minimumBy: empty list"
207 minimumBy min xs = foldl1 min xs
209 genericLength :: (Num i) => [b] -> i
211 genericLength (_:l) = 1 + genericLength l
213 genericTake :: (Integral i) => i -> [a] -> [a]
215 genericTake _ [] = []
216 genericTake n (x:xs) | n > 0 = x : genericTake (n-1) xs
217 genericTake _ _ = error "List.genericTake: negative argument"
219 genericDrop :: (Integral i) => i -> [a] -> [a]
220 genericDrop 0 xs = xs
221 genericDrop _ [] = []
222 genericDrop n (_:xs) | n > 0 = genericDrop (n-1) xs
223 genericDrop _ _ = error "List.genericDrop: negative argument"
225 genericSplitAt :: (Integral i) => i -> [b] -> ([b],[b])
226 genericSplitAt 0 xs = ([],xs)
227 genericSplitAt _ [] = ([],[])
228 genericSplitAt n (x:xs) | n > 0 = (x:xs',xs'') where
229 (xs',xs'') = genericSplitAt (n-1) xs
230 genericSplitAt _ _ = error "List.genericSplitAt: negative argument"
233 genericIndex :: (Integral a) => [b] -> a -> b
234 genericIndex (x:_) 0 = x
235 genericIndex (_:xs) n
236 | n > 0 = genericIndex xs (n-1)
237 | otherwise = error "List.genericIndex: negative argument."
238 genericIndex _ _ = error "List.genericIndex: index too large."
240 genericReplicate :: (Integral i) => i -> a -> [a]
241 genericReplicate n x = genericTake n (repeat x)
244 zip4 :: [a] -> [b] -> [c] -> [d] -> [(a,b,c,d)]
245 zip4 = zipWith4 (,,,)
247 zip5 :: [a] -> [b] -> [c] -> [d] -> [e] -> [(a,b,c,d,e)]
248 zip5 = zipWith5 (,,,,)
250 zip6 :: [a] -> [b] -> [c] -> [d] -> [e] -> [f] ->
252 zip6 = zipWith6 (,,,,,)
254 zip7 :: [a] -> [b] -> [c] -> [d] -> [e] -> [f] ->
255 [g] -> [(a,b,c,d,e,f,g)]
256 zip7 = zipWith7 (,,,,,,)
258 zipWith4 :: (a->b->c->d->e) -> [a]->[b]->[c]->[d]->[e]
259 zipWith4 z (a:as) (b:bs) (c:cs) (d:ds)
260 = z a b c d : zipWith4 z as bs cs ds
261 zipWith4 _ _ _ _ _ = []
263 zipWith5 :: (a->b->c->d->e->f) ->
264 [a]->[b]->[c]->[d]->[e]->[f]
265 zipWith5 z (a:as) (b:bs) (c:cs) (d:ds) (e:es)
266 = z a b c d e : zipWith5 z as bs cs ds es
267 zipWith5 _ _ _ _ _ _ = []
269 zipWith6 :: (a->b->c->d->e->f->g) ->
270 [a]->[b]->[c]->[d]->[e]->[f]->[g]
271 zipWith6 z (a:as) (b:bs) (c:cs) (d:ds) (e:es) (f:fs)
272 = z a b c d e f : zipWith6 z as bs cs ds es fs
273 zipWith6 _ _ _ _ _ _ _ = []
275 zipWith7 :: (a->b->c->d->e->f->g->h) ->
276 [a]->[b]->[c]->[d]->[e]->[f]->[g]->[h]
277 zipWith7 z (a:as) (b:bs) (c:cs) (d:ds) (e:es) (f:fs) (g:gs)
278 = z a b c d e f g : zipWith7 z as bs cs ds es fs gs
279 zipWith7 _ _ _ _ _ _ _ _ = []
281 unzip4 :: [(a,b,c,d)] -> ([a],[b],[c],[d])
282 unzip4 = foldr (\(a,b,c,d) ~(as,bs,cs,ds) ->
283 (a:as,b:bs,c:cs,d:ds))
286 unzip5 :: [(a,b,c,d,e)] -> ([a],[b],[c],[d],[e])
287 unzip5 = foldr (\(a,b,c,d,e) ~(as,bs,cs,ds,es) ->
288 (a:as,b:bs,c:cs,d:ds,e:es))
291 unzip6 :: [(a,b,c,d,e,f)] -> ([a],[b],[c],[d],[e],[f])
292 unzip6 = foldr (\(a,b,c,d,e,f) ~(as,bs,cs,ds,es,fs) ->
293 (a:as,b:bs,c:cs,d:ds,e:es,f:fs))
296 unzip7 :: [(a,b,c,d,e,f,g)] -> ([a],[b],[c],[d],[e],[f],[g])
297 unzip7 = foldr (\(a,b,c,d,e,f,g) ~(as,bs,cs,ds,es,fs,gs) ->
298 (a:as,b:bs,c:cs,d:ds,e:es,f:fs,g:gs))
299 ([],[],[],[],[],[],[])
303 deleteFirstsBy :: (a -> a -> Bool) -> [a] -> [a] -> [a]
304 deleteFirstsBy eq = foldl (flip (deleteBy eq))
307 -- group splits its list argument into a list of lists of equal, adjacent
309 -- group "Mississippi" == ["M","i","ss","i","ss","i","pp","i"]
310 group :: (Eq a) => [a] -> [[a]]
313 groupBy :: (a -> a -> Bool) -> [a] -> [[a]]
315 groupBy eq (x:xs) = (x:ys) : groupBy eq zs
316 where (ys,zs) = span (eq x) xs
318 -- inits xs returns the list of initial segments of xs, shortest first.
319 -- e.g., inits "abc" == ["","a","ab","abc"]
320 inits :: [a] -> [[a]]
322 inits (x:xs) = [[]] ++ map (x:) (inits xs)
324 -- tails xs returns the list of all final segments of xs, longest first.
325 -- e.g., tails "abc" == ["abc", "bc", "c",""]
326 tails :: [a] -> [[a]]
328 tails xxs@(_:xs) = xxs : tails xs