1 {-# OPTIONS -fno-implicit-prelude #-}
2 -----------------------------------------------------------------------------
5 -- Copyright : (c) The University of Glasgow 2001
6 -- License : BSD-style (see the file libraries/core/LICENSE)
8 -- Maintainer : libraries@haskell.org
9 -- Stability : provisional
10 -- Portability : portable
12 -- $Id: List.hs,v 1.4 2002/04/24 16:31:39 simonmar Exp $
14 -- Operations on lists.
16 -----------------------------------------------------------------------------
22 , elemIndex -- :: (Eq a) => a -> [a] -> Maybe Int
23 , elemIndices -- :: (Eq a) => a -> [a] -> [Int]
25 , find -- :: (a -> Bool) -> [a] -> Maybe a
26 , findIndex -- :: (a -> Bool) -> [a] -> Maybe Int
27 , findIndices -- :: (a -> Bool) -> [a] -> [Int]
29 , nub -- :: (Eq a) => [a] -> [a]
30 , nubBy -- :: (a -> a -> Bool) -> [a] -> [a]
32 , delete -- :: (Eq a) => a -> [a] -> [a]
33 , deleteBy -- :: (a -> a -> Bool) -> a -> [a] -> [a]
34 , (\\) -- :: (Eq a) => [a] -> [a] -> [a]
35 , deleteFirstsBy -- :: (a -> a -> Bool) -> [a] -> [a] -> [a]
37 , union -- :: (Eq a) => [a] -> [a] -> [a]
38 , unionBy -- :: (a -> a -> Bool) -> [a] -> [a] -> [a]
40 , intersect -- :: (Eq a) => [a] -> [a] -> [a]
41 , intersectBy -- :: (a -> a -> Bool) -> [a] -> [a] -> [a]
43 , intersperse -- :: a -> [a] -> [a]
44 , transpose -- :: [[a]] -> [[a]]
45 , partition -- :: (a -> Bool) -> [a] -> ([a], [a])
47 , group -- :: Eq a => [a] -> [[a]]
48 , groupBy -- :: (a -> a -> Bool) -> [a] -> [[a]]
50 , inits -- :: [a] -> [[a]]
51 , tails -- :: [a] -> [[a]]
53 , isPrefixOf -- :: (Eq a) => [a] -> [a] -> Bool
54 , isSuffixOf -- :: (Eq a) => [a] -> [a] -> Bool
56 , mapAccumL -- :: (a -> b -> (a,c)) -> a -> [b] -> (a,[c])
57 , mapAccumR -- :: (a -> b -> (a,c)) -> a -> [b] -> (a,[c])
59 , sort -- :: (Ord a) => [a] -> [a]
60 , sortBy -- :: (a -> a -> Ordering) -> [a] -> [a]
62 , insert -- :: (Ord a) => a -> [a] -> [a]
63 , insertBy -- :: (a -> a -> Ordering) -> a -> [a] -> [a]
65 , maximumBy -- :: (a -> a -> Ordering) -> [a] -> a
66 , minimumBy -- :: (a -> a -> Ordering) -> [a] -> a
68 , genericLength -- :: (Integral a) => [b] -> a
69 , genericTake -- :: (Integral a) => a -> [b] -> [b]
70 , genericDrop -- :: (Integral a) => a -> [b] -> [b]
71 , genericSplitAt -- :: (Integral a) => a -> [b] -> ([b], [b])
72 , genericIndex -- :: (Integral a) => [b] -> a -> b
73 , genericReplicate -- :: (Integral a) => a -> b -> [b]
75 , unfoldr -- :: (b -> Maybe (a, b)) -> b -> [a]
77 , zip4, zip5, zip6, zip7
78 , zipWith4, zipWith5, zipWith6, zipWith7
79 , unzip4, unzip5, unzip6, unzip7
81 , map -- :: ( a -> b ) -> [a] -> [b]
82 , (++) -- :: [a] -> [a] -> [a]
83 , concat -- :: [[a]] -> [a]
84 , filter -- :: (a -> Bool) -> [a] -> [a]
87 , tail -- :: [a] -> [a]
88 , init -- :: [a] -> [a]
89 , null -- :: [a] -> Bool
90 , length -- :: [a] -> Int
91 , (!!) -- :: [a] -> Int -> a
92 , foldl -- :: (a -> b -> a) -> a -> [b] -> a
93 , foldl' -- :: (a -> b -> a) -> a -> [b] -> a
94 , foldl1 -- :: (a -> a -> a) -> [a] -> a
95 , scanl -- :: (a -> b -> a) -> a -> [b] -> [a]
96 , scanl1 -- :: (a -> a -> a) -> [a] -> [a]
97 , foldr -- :: (a -> b -> b) -> b -> [a] -> b
98 , foldr1 -- :: (a -> a -> a) -> [a] -> a
99 , scanr -- :: (a -> b -> b) -> b -> [a] -> [b]
100 , scanr1 -- :: (a -> a -> a) -> [a] -> [a]
101 , iterate -- :: (a -> a) -> a -> [a]
102 , repeat -- :: a -> [a]
103 , replicate -- :: Int -> a -> [a]
104 , cycle -- :: [a] -> [a]
105 , take -- :: Int -> [a] -> [a]
106 , drop -- :: Int -> [a] -> [a]
107 , splitAt -- :: Int -> [a] -> ([a], [a])
108 , takeWhile -- :: (a -> Bool) -> [a] -> [a]
109 , dropWhile -- :: (a -> Bool) -> [a] -> [a]
110 , span -- :: (a -> Bool) -> [a] -> ([a], [a])
111 , break -- :: (a -> Bool) -> [a] -> ([a], [a])
113 , lines -- :: String -> [String]
114 , words -- :: String -> [String]
115 , unlines -- :: [String] -> String
116 , unwords -- :: [String] -> String
117 , reverse -- :: [a] -> [a]
118 , and -- :: [Bool] -> Bool
119 , or -- :: [Bool] -> Bool
120 , any -- :: (a -> Bool) -> [a] -> Bool
121 , all -- :: (a -> Bool) -> [a] -> Bool
122 , elem -- :: a -> [a] -> Bool
123 , notElem -- :: a -> [a] -> Bool
124 , lookup -- :: (Eq a) => a -> [(a,b)] -> Maybe b
125 , sum -- :: (Num a) => [a] -> a
126 , product -- :: (Num a) => [a] -> a
127 , maximum -- :: (Ord a) => [a] -> a
128 , minimum -- :: (Ord a) => [a] -> a
129 , concatMap -- :: (a -> [b]) -> [a] -> [b]
130 , zip -- :: [a] -> [b] -> [(a,b)]
132 , zipWith -- :: (a -> b -> c) -> [a] -> [b] -> [c]
134 , unzip -- :: [(a,b)] -> ([a],[b])
141 #ifdef __GLASGOW_HASKELL__
145 import GHC.Show ( lines, words, unlines, unwords )
151 -- -----------------------------------------------------------------------------
154 elemIndex :: Eq a => a -> [a] -> Maybe Int
155 elemIndex x = findIndex (x==)
157 elemIndices :: Eq a => a -> [a] -> [Int]
158 elemIndices x = findIndices (x==)
160 find :: (a -> Bool) -> [a] -> Maybe a
161 find p = listToMaybe . filter p
163 findIndex :: (a -> Bool) -> [a] -> Maybe Int
164 findIndex p = listToMaybe . findIndices p
166 findIndices :: (a -> Bool) -> [a] -> [Int]
168 #ifdef USE_REPORT_PRELUDE
169 findIndices p xs = [ i | (x,i) <- zip xs [0..], p x]
172 findIndices p xs = [ i | (x,i) <- zip xs [0..], p x]
174 -- Efficient definition
175 findIndices p ls = loop 0# ls
178 loop n (x:xs) | p x = I# n : loop (n +# 1#) xs
179 | otherwise = loop (n +# 1#) xs
180 #endif /* __HUGS__ */
181 #endif /* USE_REPORT_PRELUDE */
183 isPrefixOf :: (Eq a) => [a] -> [a] -> Bool
184 isPrefixOf [] _ = True
185 isPrefixOf _ [] = False
186 isPrefixOf (x:xs) (y:ys)= x == y && isPrefixOf xs ys
188 isSuffixOf :: (Eq a) => [a] -> [a] -> Bool
189 isSuffixOf x y = reverse x `isPrefixOf` reverse y
191 -- nub (meaning "essence") remove duplicate elements from its list argument.
192 nub :: (Eq a) => [a] -> [a]
193 #ifdef USE_REPORT_PRELUDE
197 nub l = nub' l [] -- '
201 | x `elem` ls = nub' xs ls -- '
202 | otherwise = x : nub' xs (x:ls) -- '
205 nubBy :: (a -> a -> Bool) -> [a] -> [a]
206 #ifdef USE_REPORT_PRELUDE
208 nubBy eq (x:xs) = x : nubBy eq (filter (\ y -> not (eq x y)) xs)
210 nubBy eq l = nubBy' l []
214 | elem_by eq y xs = nubBy' ys xs
215 | otherwise = y : nubBy' ys (y:xs)
218 -- Note that we keep the call to `eq` with arguments in the
219 -- same order as in the reference implementation
220 -- 'xs' is the list of things we've seen so far,
221 -- 'y' is the potential new element
222 elem_by :: (a -> a -> Bool) -> a -> [a] -> Bool
223 elem_by _ _ [] = False
224 elem_by eq y (x:xs) = x `eq` y || elem_by eq y xs
228 -- delete x removes the first occurrence of x from its list argument.
229 delete :: (Eq a) => a -> [a] -> [a]
230 delete = deleteBy (==)
232 deleteBy :: (a -> a -> Bool) -> a -> [a] -> [a]
234 deleteBy eq x (y:ys) = if x `eq` y then ys else y : deleteBy eq x ys
236 -- list difference (non-associative). In the result of xs \\ ys,
237 -- the first occurrence of each element of ys in turn (if any)
238 -- has been removed from xs. Thus, (xs ++ ys) \\ xs == ys.
239 (\\) :: (Eq a) => [a] -> [a] -> [a]
240 (\\) = foldl (flip delete)
242 -- List union, remove the elements of first list from second.
243 union :: (Eq a) => [a] -> [a] -> [a]
246 unionBy :: (a -> a -> Bool) -> [a] -> [a] -> [a]
247 unionBy eq xs ys = xs ++ foldl (flip (deleteBy eq)) (nubBy eq ys) xs
249 intersect :: (Eq a) => [a] -> [a] -> [a]
250 intersect = intersectBy (==)
252 intersectBy :: (a -> a -> Bool) -> [a] -> [a] -> [a]
253 intersectBy eq xs ys = [x | x <- xs, any (eq x) ys]
255 -- intersperse sep inserts sep between the elements of its list argument.
256 -- e.g. intersperse ',' "abcde" == "a,b,c,d,e"
257 intersperse :: a -> [a] -> [a]
258 intersperse _ [] = []
259 intersperse _ [x] = [x]
260 intersperse sep (x:xs) = x : sep : intersperse sep xs
262 transpose :: [[a]] -> [[a]]
264 transpose ([] : xss) = transpose xss
265 transpose ((x:xs) : xss) = (x : [h | (h:t) <- xss]) : transpose (xs : [ t | (h:t) <- xss])
268 -- partition takes a predicate and a list and returns a pair of lists:
269 -- those elements of the argument list that do and do not satisfy the
270 -- predicate, respectively; i,e,,
271 -- partition p xs == (filter p xs, filter (not . p) xs).
272 partition :: (a -> Bool) -> [a] -> ([a],[a])
273 {-# INLINE partition #-}
274 partition p xs = foldr (select p) ([],[]) xs
276 select p x (ts,fs) | p x = (x:ts,fs)
277 | otherwise = (ts, x:fs)
279 -- @mapAccumL@ behaves like a combination
280 -- of @map@ and @foldl@;
281 -- it applies a function to each element of a list, passing an accumulating
282 -- parameter from left to right, and returning a final value of this
283 -- accumulator together with the new list.
285 mapAccumL :: (acc -> x -> (acc, y)) -- Function of elt of input list
286 -- and accumulator, returning new
287 -- accumulator and elt of result list
288 -> acc -- Initial accumulator
290 -> (acc, [y]) -- Final accumulator and result list
291 mapAccumL _ s [] = (s, [])
292 mapAccumL f s (x:xs) = (s'',y:ys)
293 where (s', y ) = f s x
294 (s'',ys) = mapAccumL f s' xs
296 -- @mapAccumR@ does the same, but working from right to left instead.
297 -- Its type is the same as @mapAccumL@, though.
299 mapAccumR :: (acc -> x -> (acc, y)) -- Function of elt of input list
300 -- and accumulator, returning new
301 -- accumulator and elt of result list
302 -> acc -- Initial accumulator
304 -> (acc, [y]) -- Final accumulator and result list
305 mapAccumR _ s [] = (s, [])
306 mapAccumR f s (x:xs) = (s'', y:ys)
307 where (s'',y ) = f s' x
308 (s', ys) = mapAccumR f s xs
311 insert :: Ord a => a -> [a] -> [a]
312 insert e ls = insertBy (compare) e ls
314 insertBy :: (a -> a -> Ordering) -> a -> [a] -> [a]
315 insertBy _ x [] = [x]
316 insertBy cmp x ys@(y:ys')
318 GT -> y : insertBy cmp x ys'
321 maximumBy :: (a -> a -> Ordering) -> [a] -> a
322 maximumBy _ [] = error "List.maximumBy: empty list"
323 maximumBy cmp xs = foldl1 max xs
325 max x y = case cmp x y of
329 minimumBy :: (a -> a -> Ordering) -> [a] -> a
330 minimumBy _ [] = error "List.minimumBy: empty list"
331 minimumBy cmp xs = foldl1 min xs
333 min x y = case cmp x y of
337 genericLength :: (Num i) => [b] -> i
339 genericLength (_:l) = 1 + genericLength l
341 genericTake :: (Integral i) => i -> [a] -> [a]
343 genericTake _ [] = []
344 genericTake n (x:xs) | n > 0 = x : genericTake (n-1) xs
345 genericTake _ _ = error "List.genericTake: negative argument"
347 genericDrop :: (Integral i) => i -> [a] -> [a]
348 genericDrop 0 xs = xs
349 genericDrop _ [] = []
350 genericDrop n (_:xs) | n > 0 = genericDrop (n-1) xs
351 genericDrop _ _ = error "List.genericDrop: negative argument"
353 genericSplitAt :: (Integral i) => i -> [b] -> ([b],[b])
354 genericSplitAt 0 xs = ([],xs)
355 genericSplitAt _ [] = ([],[])
356 genericSplitAt n (x:xs) | n > 0 = (x:xs',xs'') where
357 (xs',xs'') = genericSplitAt (n-1) xs
358 genericSplitAt _ _ = error "List.genericSplitAt: negative argument"
361 genericIndex :: (Integral a) => [b] -> a -> b
362 genericIndex (x:_) 0 = x
363 genericIndex (_:xs) n
364 | n > 0 = genericIndex xs (n-1)
365 | otherwise = error "List.genericIndex: negative argument."
366 genericIndex _ _ = error "List.genericIndex: index too large."
368 genericReplicate :: (Integral i) => i -> a -> [a]
369 genericReplicate n x = genericTake n (repeat x)
372 zip4 :: [a] -> [b] -> [c] -> [d] -> [(a,b,c,d)]
373 zip4 = zipWith4 (,,,)
375 zip5 :: [a] -> [b] -> [c] -> [d] -> [e] -> [(a,b,c,d,e)]
376 zip5 = zipWith5 (,,,,)
378 zip6 :: [a] -> [b] -> [c] -> [d] -> [e] -> [f] ->
380 zip6 = zipWith6 (,,,,,)
382 zip7 :: [a] -> [b] -> [c] -> [d] -> [e] -> [f] ->
383 [g] -> [(a,b,c,d,e,f,g)]
384 zip7 = zipWith7 (,,,,,,)
386 zipWith4 :: (a->b->c->d->e) -> [a]->[b]->[c]->[d]->[e]
387 zipWith4 z (a:as) (b:bs) (c:cs) (d:ds)
388 = z a b c d : zipWith4 z as bs cs ds
389 zipWith4 _ _ _ _ _ = []
391 zipWith5 :: (a->b->c->d->e->f) ->
392 [a]->[b]->[c]->[d]->[e]->[f]
393 zipWith5 z (a:as) (b:bs) (c:cs) (d:ds) (e:es)
394 = z a b c d e : zipWith5 z as bs cs ds es
395 zipWith5 _ _ _ _ _ _ = []
397 zipWith6 :: (a->b->c->d->e->f->g) ->
398 [a]->[b]->[c]->[d]->[e]->[f]->[g]
399 zipWith6 z (a:as) (b:bs) (c:cs) (d:ds) (e:es) (f:fs)
400 = z a b c d e f : zipWith6 z as bs cs ds es fs
401 zipWith6 _ _ _ _ _ _ _ = []
403 zipWith7 :: (a->b->c->d->e->f->g->h) ->
404 [a]->[b]->[c]->[d]->[e]->[f]->[g]->[h]
405 zipWith7 z (a:as) (b:bs) (c:cs) (d:ds) (e:es) (f:fs) (g:gs)
406 = z a b c d e f g : zipWith7 z as bs cs ds es fs gs
407 zipWith7 _ _ _ _ _ _ _ _ = []
409 unzip4 :: [(a,b,c,d)] -> ([a],[b],[c],[d])
410 unzip4 = foldr (\(a,b,c,d) ~(as,bs,cs,ds) ->
411 (a:as,b:bs,c:cs,d:ds))
414 unzip5 :: [(a,b,c,d,e)] -> ([a],[b],[c],[d],[e])
415 unzip5 = foldr (\(a,b,c,d,e) ~(as,bs,cs,ds,es) ->
416 (a:as,b:bs,c:cs,d:ds,e:es))
419 unzip6 :: [(a,b,c,d,e,f)] -> ([a],[b],[c],[d],[e],[f])
420 unzip6 = foldr (\(a,b,c,d,e,f) ~(as,bs,cs,ds,es,fs) ->
421 (a:as,b:bs,c:cs,d:ds,e:es,f:fs))
424 unzip7 :: [(a,b,c,d,e,f,g)] -> ([a],[b],[c],[d],[e],[f],[g])
425 unzip7 = foldr (\(a,b,c,d,e,f,g) ~(as,bs,cs,ds,es,fs,gs) ->
426 (a:as,b:bs,c:cs,d:ds,e:es,f:fs,g:gs))
427 ([],[],[],[],[],[],[])
431 deleteFirstsBy :: (a -> a -> Bool) -> [a] -> [a] -> [a]
432 deleteFirstsBy eq = foldl (flip (deleteBy eq))
435 -- group splits its list argument into a list of lists of equal, adjacent
437 -- group "Mississippi" == ["M","i","ss","i","ss","i","pp","i"]
438 group :: (Eq a) => [a] -> [[a]]
441 groupBy :: (a -> a -> Bool) -> [a] -> [[a]]
443 groupBy eq (x:xs) = (x:ys) : groupBy eq zs
444 where (ys,zs) = span (eq x) xs
446 -- inits xs returns the list of initial segments of xs, shortest first.
447 -- e.g., inits "abc" == ["","a","ab","abc"]
448 inits :: [a] -> [[a]]
450 inits (x:xs) = [[]] ++ map (x:) (inits xs)
452 -- tails xs returns the list of all final segments of xs, longest first.
453 -- e.g., tails "abc" == ["abc", "bc", "c",""]
454 tails :: [a] -> [[a]]
456 tails xxs@(_:xs) = xxs : tails xs
459 ------------------------------------------------------------------------------
460 -- Quick Sort algorithm taken from HBC's QSort library.
462 sort :: (Ord a) => [a] -> [a]
463 sortBy :: (a -> a -> Ordering) -> [a] -> [a]
465 #ifdef USE_REPORT_PRELUDE
466 sort = sortBy compare
467 sortBy cmp = foldr (insertBy cmp) []
470 sortBy cmp l = qsort cmp l []
471 sort l = qsort compare l []
473 -- rest is not exported:
475 -- qsort is stable and does not concatenate.
476 qsort :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
479 qsort cmp (x:xs) r = qpart cmp x xs [] [] r
481 -- qpart partitions and sorts the sublists
482 qpart :: (a -> a -> Ordering) -> a -> [a] -> [a] -> [a] -> [a] -> [a]
483 qpart cmp x [] rlt rge r =
484 -- rlt and rge are in reverse order and must be sorted with an
485 -- anti-stable sorting
486 rqsort cmp rlt (x:rqsort cmp rge r)
487 qpart cmp x (y:ys) rlt rge r =
489 GT -> qpart cmp x ys (y:rlt) rge r
490 _ -> qpart cmp x ys rlt (y:rge) r
492 -- rqsort is as qsort but anti-stable, i.e. reverses equal elements
493 rqsort :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
496 rqsort cmp (x:xs) r = rqpart cmp x xs [] [] r
498 rqpart :: (a -> a -> Ordering) -> a -> [a] -> [a] -> [a] -> [a] -> [a]
499 rqpart cmp x [] rle rgt r =
500 qsort cmp rle (x:qsort cmp rgt r)
501 rqpart cmp x (y:ys) rle rgt r =
503 GT -> rqpart cmp x ys rle (y:rgt) r
504 _ -> rqpart cmp x ys (y:rle) rgt r
506 #endif /* USE_REPORT_PRELUDE */
510 unfoldr f' (foldr f z xs) == (z,xs)
512 if the following holds:
514 f' (f x y) = Just (x,y)
519 unfoldr :: (b -> Maybe (a, b)) -> b -> [a]
522 Just (a,new_b) -> a : unfoldr f new_b
526 -- -----------------------------------------------------------------------------
527 -- strict version of foldl
529 foldl' :: (a -> b -> a) -> a -> [b] -> a
531 foldl' f a (x:xs) = let a' = f a x in a' `seq` foldl' f a' xs
533 -- -----------------------------------------------------------------------------
534 -- List sum and product
536 -- sum and product compute the sum or product of a finite list of numbers.
537 {-# SPECIALISE sum :: [Int] -> Int #-}
538 {-# SPECIALISE sum :: [Integer] -> Integer #-}
539 {-# SPECIALISE product :: [Int] -> Int #-}
540 {-# SPECIALISE product :: [Integer] -> Integer #-}
541 sum, product :: (Num a) => [a] -> a
542 #ifdef USE_REPORT_PRELUDE
544 product = foldl (*) 1
549 sum' (x:xs) a = sum' xs (a+x)
553 prod (x:xs) a = prod xs (a*x)