2 % (c) The AQUA Project, Glasgow University, 1994-1999
5 \section[List]{Module @Lhar@}
15 elemIndex -- :: (Eq a) => a -> [a] -> Maybe Int
16 , elemIndices -- :: (Eq a) => a -> [a] -> [Int]
18 , find -- :: (a -> Bool) -> [a] -> Maybe a
19 , findIndex -- :: (a -> Bool) -> [a] -> Maybe Int
20 , findIndices -- :: (a -> Bool) -> [a] -> [Int]
22 , nub -- :: (Eq a) => [a] -> [a]
23 , nubBy -- :: (a -> a -> Bool) -> [a] -> [a]
25 , delete -- :: (Eq a) => a -> [a] -> [a]
26 , deleteBy -- :: (a -> a -> Bool) -> a -> [a] -> [a]
27 , (\\) -- :: (Eq a) => [a] -> [a] -> [a]
28 , deleteFirstsBy -- :: (a -> a -> Bool) -> [a] -> [a] -> [a]
30 , union -- :: (Eq a) => [a] -> [a] -> [a]
31 , unionBy -- :: (a -> a -> Bool) -> [a] -> [a] -> [a]
33 , intersect -- :: (Eq a) => [a] -> [a] -> [a]
34 , intersectBy -- :: (a -> a -> Bool) -> [a] -> [a] -> [a]
36 , intersperse -- :: a -> [a] -> [a]
37 , transpose -- :: [[a]] -> [[a]]
38 , partition -- :: (a -> Bool) -> [a] -> ([a], [a])
40 , group -- :: Eq a => [a] -> [[a]]
41 , groupBy -- :: (a -> a -> Bool) -> [a] -> [[a]]
43 , inits -- :: [a] -> [[a]]
44 , tails -- :: [a] -> [[a]]
46 , isPrefixOf -- :: (Eq a) => [a] -> [a] -> Bool
47 , isSuffixOf -- :: (Eq a) => [a] -> [a] -> Bool
49 , mapAccumL -- :: (a -> b -> (a,c)) -> a -> [b] -> (a,[c])
50 , mapAccumR -- :: (a -> b -> (a,c)) -> a -> [b] -> (a,[c])
52 , sort -- :: (Ord a) => [a] -> [a]
53 , sortBy -- :: (a -> a -> Ordering) -> [a] -> [a]
55 , insert -- :: (Ord a) => a -> [a] -> [a]
56 , insertBy -- :: (a -> a -> Ordering) -> a -> [a] -> [a]
58 , maximumBy -- :: (a -> a -> Ordering) -> [a] -> a
59 , minimumBy -- :: (a -> a -> Ordering) -> [a] -> a
61 , genericLength -- :: (Integral a) => [b] -> a
62 , genericTake -- :: (Integral a) => a -> [b] -> [b]
63 , genericDrop -- :: (Integral a) => a -> [b] -> [b]
64 , genericSplitAt -- :: (Integral a) => a -> [b] -> ([b], [b])
65 , genericIndex -- :: (Integral a) => [b] -> a -> b
66 , genericReplicate -- :: (Integral a) => a -> b -> [b]
68 , unfoldr -- :: (a -> Maybe (b,a)) -> a -> (a,[b])
70 , zip4, zip5, zip6, zip7
71 , zipWith4, zipWith5, zipWith6, zipWith7
72 , unzip4, unzip5, unzip6, unzip7
74 , map -- :: ( a -> b ) -> [a] -> [b]
75 , (++) -- :: [a] -> [a] -> [a]
76 , concat -- :: [[a]] -> [a]
77 , filter -- :: (a -> Bool) -> [a] -> [a]
80 , tail -- :: [a] -> [a]
81 , init -- :: [a] -> [a]
82 , null -- :: [a] -> Bool
83 , length -- :: [a] -> Int
84 , (!!) -- :: [a] -> Int -> a
85 , foldl -- :: (a -> b -> a) -> a -> [b] -> a
86 , foldl1 -- :: (a -> a -> a) -> [a] -> a
87 , scanl -- :: (a -> b -> a) -> a -> [b] -> [a]
88 , scanl1 -- :: (a -> a -> a) -> [a] -> [a]
89 , foldr -- :: (a -> b -> b) -> b -> [a] -> b
90 , foldr1 -- :: (a -> a -> a) -> [a] -> a
91 , scanr -- :: (a -> b -> b) -> b -> [a] -> [b]
92 , scanr1 -- :: (a -> a -> a) -> [a] -> [a]
93 , iterate -- :: (a -> a) -> a -> [a]
94 , repeat -- :: a -> [a]
95 , replicate -- :: Int -> a -> [a]
96 , cycle -- :: [a] -> [a]
97 , take -- :: Int -> [a] -> [a]
98 , drop -- :: Int -> [a] -> [a]
99 , splitAt -- :: Int -> [a] -> ([a], [a])
100 , takeWhile -- :: (a -> Bool) -> [a] -> [a]
101 , dropWhile -- :: (a -> Bool) -> [a] -> [a]
102 , span -- :: (a -> Bool) -> [a] -> ([a], [a])
103 , break -- :: (a -> Bool) -> [a] -> ([a], [a])
105 , lines -- :: String -> [String]
106 , words -- :: String -> [String]
107 , unlines -- :: [String] -> String
108 , unwords -- :: [String] -> String
109 , reverse -- :: [a] -> [a]
110 , and -- :: [Bool] -> Bool
111 , or -- :: [Bool] -> Bool
112 , any -- :: (a -> Bool) -> [a] -> Bool
113 , all -- :: (a -> Bool) -> [a] -> Bool
114 , elem -- :: a -> [a] -> Bool
115 , notElem -- :: a -> [a] -> Bool
116 , lookup -- :: (Eq a) => a -> [(a,b)] -> Maybe b
117 , sum -- :: (Num a) => [a] -> a
118 , product -- :: (Num a) => [a] -> a
119 , maximum -- :: (Ord a) => [a] -> a
120 , minimum -- :: (Ord a) => [a] -> a
121 , concatMap -- :: (a -> [b]) -> [a] -> [b]
122 , zip -- :: [a] -> [b] -> [(a,b)]
124 , zipWith -- :: (a -> b -> c) -> [a] -> [b] -> [c]
126 , unzip -- :: [(a,b)] -> ([a],[b])
129 -- Implementation checked wrt. Haskell 98 lib report, 1/99.
133 import Maybe ( listToMaybe )
136 import PrelShow ( lines, words, unlines, unwords )
137 import PrelBase ( Int(..), map, (++) )
138 import PrelGHC ( (+#) )
144 %*********************************************************
146 \subsection{List functions}
148 %*********************************************************
151 elemIndex :: Eq a => a -> [a] -> Maybe Int
152 elemIndex x = findIndex (x==)
154 elemIndices :: Eq a => a -> [a] -> [Int]
155 elemIndices x = findIndices (x==)
157 find :: (a -> Bool) -> [a] -> Maybe a
158 find p = listToMaybe . filter p
160 findIndex :: (a -> Bool) -> [a] -> Maybe Int
161 findIndex p = listToMaybe . findIndices p
163 findIndices :: (a -> Bool) -> [a] -> [Int]
165 #ifdef USE_REPORT_PRELUDE
166 findIndices p xs = [ i | (x,i) <- zip xs [0..], p x]
168 -- Efficient definition
169 findIndices p ls = loop 0# ls
172 loop n (x:xs) | p x = I# n : loop (n +# 1#) xs
173 | otherwise = loop (n +# 1#) xs
176 isPrefixOf :: (Eq a) => [a] -> [a] -> Bool
177 isPrefixOf [] _ = True
178 isPrefixOf _ [] = False
179 isPrefixOf (x:xs) (y:ys)= x == y && isPrefixOf xs ys
181 isSuffixOf :: (Eq a) => [a] -> [a] -> Bool
182 isSuffixOf x y = reverse x `isPrefixOf` reverse y
184 -- nub (meaning "essence") remove duplicate elements from its list argument.
185 nub :: (Eq a) => [a] -> [a]
186 #ifdef USE_REPORT_PRELUDE
190 nub l = nub' l [] -- '
194 | x `elem` ls = nub' xs ls -- '
195 | otherwise = x : nub' xs (x:ls) -- '
198 nubBy :: (a -> a -> Bool) -> [a] -> [a]
199 #ifdef USE_REPORT_PRELUDE
201 nubBy eq (x:xs) = x : nubBy eq (filter (\ y -> not (eq x y)) xs)
203 nubBy eq l = nubBy' l []
207 | elemBy eq x ls = nubBy' xs ls
208 | otherwise = x : nubBy' xs (x:ls)
211 elemBy :: (a -> a -> Bool) -> a -> [a] -> Bool
212 elemBy _ _ [] = False
213 elemBy eq x (y:ys) = x `eq` y || elemBy eq x ys
217 -- delete x removes the first occurrence of x from its list argument.
218 delete :: (Eq a) => a -> [a] -> [a]
219 delete = deleteBy (==)
221 deleteBy :: (a -> a -> Bool) -> a -> [a] -> [a]
223 deleteBy eq x (y:ys) = if x `eq` y then ys else y : deleteBy eq x ys
225 -- list difference (non-associative). In the result of xs \\ ys,
226 -- the first occurrence of each element of ys in turn (if any)
227 -- has been removed from xs. Thus, (xs ++ ys) \\ xs == ys.
228 (\\) :: (Eq a) => [a] -> [a] -> [a]
229 (\\) = foldl (flip delete)
231 -- List union, remove the elements of first list from second.
232 union :: (Eq a) => [a] -> [a] -> [a]
235 unionBy :: (a -> a -> Bool) -> [a] -> [a] -> [a]
236 unionBy eq xs ys = xs ++ foldl (flip (deleteBy eq)) (nubBy eq ys) xs
238 intersect :: (Eq a) => [a] -> [a] -> [a]
239 intersect = intersectBy (==)
241 intersectBy :: (a -> a -> Bool) -> [a] -> [a] -> [a]
242 intersectBy eq xs ys = [x | x <- xs, any (eq x) ys]
244 -- intersperse sep inserts sep between the elements of its list argument.
245 -- e.g. intersperse ',' "abcde" == "a,b,c,d,e"
246 intersperse :: a -> [a] -> [a]
247 intersperse _ [] = []
248 intersperse _ [x] = [x]
249 intersperse sep (x:xs) = x : sep : intersperse sep xs
251 transpose :: [[a]] -> [[a]]
253 transpose ([] : xss) = transpose xss
254 transpose ((x:xs) : xss) = (x : [h | (h:t) <- xss]) : transpose (xs : [ t | (h:t) <- xss])
257 -- partition takes a predicate and a list and returns a pair of lists:
258 -- those elements of the argument list that do and do not satisfy the
259 -- predicate, respectively; i,e,,
260 -- partition p xs == (filter p xs, filter (not . p) xs).
261 partition :: (a -> Bool) -> [a] -> ([a],[a])
262 {-# INLINE partition #-}
263 partition p xs = foldr (select p) ([],[]) xs
265 select p x (ts,fs) | p x = (x:ts,fs)
266 | otherwise = (ts, x:fs)
269 @mapAccumL@ behaves like a combination
270 of @map@ and @foldl@;
271 it applies a function to each element of a list, passing an accumulating
272 parameter from left to right, and returning a final value of this
273 accumulator together with the new list.
277 mapAccumL :: (acc -> x -> (acc, y)) -- Function of elt of input list
278 -- and accumulator, returning new
279 -- accumulator and elt of result list
280 -> acc -- Initial accumulator
282 -> (acc, [y]) -- Final accumulator and result list
283 mapAccumL _ s [] = (s, [])
284 mapAccumL f s (x:xs) = (s'',y:ys)
285 where (s', y ) = f s x
286 (s'',ys) = mapAccumL f s' xs
289 @mapAccumR@ does the same, but working from right to left instead. Its type is
290 the same as @mapAccumL@, though.
293 mapAccumR :: (acc -> x -> (acc, y)) -- Function of elt of input list
294 -- and accumulator, returning new
295 -- accumulator and elt of result list
296 -> acc -- Initial accumulator
298 -> (acc, [y]) -- Final accumulator and result list
299 mapAccumR _ s [] = (s, [])
300 mapAccumR f s (x:xs) = (s'', y:ys)
301 where (s'',y ) = f s' x
302 (s', ys) = mapAccumR f s xs
306 insert :: Ord a => a -> [a] -> [a]
307 insert e ls = insertBy (compare) e ls
309 insertBy :: (a -> a -> Ordering) -> a -> [a] -> [a]
310 insertBy _ x [] = [x]
311 insertBy cmp x ys@(y:ys')
313 GT -> y : insertBy cmp x ys'
316 maximumBy :: (a -> a -> a) -> [a] -> a
317 maximumBy _ [] = error "List.maximumBy: empty list"
318 maximumBy max xs = foldl1 max xs
320 minimumBy :: (a -> a -> a) -> [a] -> a
321 minimumBy _ [] = error "List.minimumBy: empty list"
322 minimumBy min xs = foldl1 min xs
324 genericLength :: (Num i) => [b] -> i
326 genericLength (_:l) = 1 + genericLength l
328 genericTake :: (Integral i) => i -> [a] -> [a]
330 genericTake _ [] = []
331 genericTake n (x:xs) | n > 0 = x : genericTake (n-1) xs
332 genericTake _ _ = error "List.genericTake: negative argument"
334 genericDrop :: (Integral i) => i -> [a] -> [a]
335 genericDrop 0 xs = xs
336 genericDrop _ [] = []
337 genericDrop n (_:xs) | n > 0 = genericDrop (n-1) xs
338 genericDrop _ _ = error "List.genericDrop: negative argument"
340 genericSplitAt :: (Integral i) => i -> [b] -> ([b],[b])
341 genericSplitAt 0 xs = ([],xs)
342 genericSplitAt _ [] = ([],[])
343 genericSplitAt n (x:xs) | n > 0 = (x:xs',xs'') where
344 (xs',xs'') = genericSplitAt (n-1) xs
345 genericSplitAt _ _ = error "List.genericSplitAt: negative argument"
348 genericIndex :: (Integral a) => [b] -> a -> b
349 genericIndex (x:_) 0 = x
350 genericIndex (_:xs) n
351 | n > 0 = genericIndex xs (n-1)
352 | otherwise = error "List.genericIndex: negative argument."
353 genericIndex _ _ = error "List.genericIndex: index too large."
355 genericReplicate :: (Integral i) => i -> a -> [a]
356 genericReplicate n x = genericTake n (repeat x)
359 zip4 :: [a] -> [b] -> [c] -> [d] -> [(a,b,c,d)]
360 zip4 = zipWith4 (,,,)
362 zip5 :: [a] -> [b] -> [c] -> [d] -> [e] -> [(a,b,c,d,e)]
363 zip5 = zipWith5 (,,,,)
365 zip6 :: [a] -> [b] -> [c] -> [d] -> [e] -> [f] ->
367 zip6 = zipWith6 (,,,,,)
369 zip7 :: [a] -> [b] -> [c] -> [d] -> [e] -> [f] ->
370 [g] -> [(a,b,c,d,e,f,g)]
371 zip7 = zipWith7 (,,,,,,)
373 zipWith4 :: (a->b->c->d->e) -> [a]->[b]->[c]->[d]->[e]
374 zipWith4 z (a:as) (b:bs) (c:cs) (d:ds)
375 = z a b c d : zipWith4 z as bs cs ds
376 zipWith4 _ _ _ _ _ = []
378 zipWith5 :: (a->b->c->d->e->f) ->
379 [a]->[b]->[c]->[d]->[e]->[f]
380 zipWith5 z (a:as) (b:bs) (c:cs) (d:ds) (e:es)
381 = z a b c d e : zipWith5 z as bs cs ds es
382 zipWith5 _ _ _ _ _ _ = []
384 zipWith6 :: (a->b->c->d->e->f->g) ->
385 [a]->[b]->[c]->[d]->[e]->[f]->[g]
386 zipWith6 z (a:as) (b:bs) (c:cs) (d:ds) (e:es) (f:fs)
387 = z a b c d e f : zipWith6 z as bs cs ds es fs
388 zipWith6 _ _ _ _ _ _ _ = []
390 zipWith7 :: (a->b->c->d->e->f->g->h) ->
391 [a]->[b]->[c]->[d]->[e]->[f]->[g]->[h]
392 zipWith7 z (a:as) (b:bs) (c:cs) (d:ds) (e:es) (f:fs) (g:gs)
393 = z a b c d e f g : zipWith7 z as bs cs ds es fs gs
394 zipWith7 _ _ _ _ _ _ _ _ = []
396 unzip4 :: [(a,b,c,d)] -> ([a],[b],[c],[d])
397 unzip4 = foldr (\(a,b,c,d) ~(as,bs,cs,ds) ->
398 (a:as,b:bs,c:cs,d:ds))
401 unzip5 :: [(a,b,c,d,e)] -> ([a],[b],[c],[d],[e])
402 unzip5 = foldr (\(a,b,c,d,e) ~(as,bs,cs,ds,es) ->
403 (a:as,b:bs,c:cs,d:ds,e:es))
406 unzip6 :: [(a,b,c,d,e,f)] -> ([a],[b],[c],[d],[e],[f])
407 unzip6 = foldr (\(a,b,c,d,e,f) ~(as,bs,cs,ds,es,fs) ->
408 (a:as,b:bs,c:cs,d:ds,e:es,f:fs))
411 unzip7 :: [(a,b,c,d,e,f,g)] -> ([a],[b],[c],[d],[e],[f],[g])
412 unzip7 = foldr (\(a,b,c,d,e,f,g) ~(as,bs,cs,ds,es,fs,gs) ->
413 (a:as,b:bs,c:cs,d:ds,e:es,f:fs,g:gs))
414 ([],[],[],[],[],[],[])
418 deleteFirstsBy :: (a -> a -> Bool) -> [a] -> [a] -> [a]
419 deleteFirstsBy eq = foldl (flip (deleteBy eq))
422 -- group splits its list argument into a list of lists of equal, adjacent
424 -- group "Mississippi" == ["M","i","ss","i","ss","i","pp","i"]
425 group :: (Eq a) => [a] -> [[a]]
428 groupBy :: (a -> a -> Bool) -> [a] -> [[a]]
430 groupBy eq (x:xs) = (x:ys) : groupBy eq zs
431 where (ys,zs) = span (eq x) xs
433 -- inits xs returns the list of initial segments of xs, shortest first.
434 -- e.g., inits "abc" == ["","a","ab","abc"]
435 inits :: [a] -> [[a]]
437 inits (x:xs) = [[]] ++ map (x:) (inits xs)
439 -- tails xs returns the list of all final segments of xs, longest first.
440 -- e.g., tails "abc" == ["abc", "bc", "c",""]
441 tails :: [a] -> [[a]]
443 tails xxs@(_:xs) = xxs : tails xs
447 %-----------------------------------------------------------------------------
448 Quick Sort algorithm taken from HBC's QSort library.
451 sort :: (Ord a) => [a] -> [a]
452 sortBy :: (a -> a -> Ordering) -> [a] -> [a]
454 #ifdef USE_REPORT_PRELUDE
455 sort = sortBy compare
456 sortBy cmp = foldr (insertBy cmp) []
459 sortBy cmp l = qsort cmp l []
460 sort l = qsort compare l []
462 -- rest is not exported:
464 -- qsort is stable and does not concatenate.
465 qsort :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
468 qsort cmp (x:xs) r = qpart cmp x xs [] [] r
470 -- qpart partitions and sorts the sublists
471 qpart :: (a -> a -> Ordering) -> a -> [a] -> [a] -> [a] -> [a] -> [a]
472 qpart cmp x [] rlt rge r =
473 -- rlt and rge are in reverse order and must be sorted with an
474 -- anti-stable sorting
475 rqsort cmp rlt (x:rqsort cmp rge r)
476 qpart cmp x (y:ys) rlt rge r =
478 GT -> qpart cmp x ys (y:rlt) rge r
479 _ -> qpart cmp x ys rlt (y:rge) r
481 -- rqsort is as qsort but anti-stable, i.e. reverses equal elements
482 rqsort :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
485 rqsort cmp (x:xs) r = rqpart cmp x xs [] [] r
487 rqpart :: (a -> a -> Ordering) -> a -> [a] -> [a] -> [a] -> [a] -> [a]
488 rqpart cmp x [] rle rgt r =
489 qsort cmp rle (x:qsort cmp rgt r)
490 rqpart cmp x (y:ys) rle rgt r =
492 GT -> rqpart cmp x ys rle (y:rgt) r
493 _ -> rqpart cmp x ys (y:rle) rgt r
495 #endif /* USE_REPORT_PRELUDE */
499 unfoldr f' (foldr f z xs) == (z,xs)
501 if the following holds:
503 f' (f x y) = Just (x,y)
508 unfoldr :: (b -> Maybe (a, b)) -> b -> [a]
511 Just (a,new_b) -> a : unfoldr f new_b