SafeHaskell: Added SafeHaskell to base
[ghc.git] / libraries / base / Data / List.hs
1 {-# LANGUAGE Trustworthy #-}
2 {-# LANGUAGE CPP, NoImplicitPrelude, MagicHash #-}
3
4 -----------------------------------------------------------------------------
5 -- |
6 -- Module : Data.List
7 -- Copyright : (c) The University of Glasgow 2001
8 -- License : BSD-style (see the file libraries/base/LICENSE)
9 --
10 -- Maintainer : libraries@haskell.org
11 -- Stability : stable
12 -- Portability : portable
13 --
14 -- Operations on lists.
15 --
16 -----------------------------------------------------------------------------
17
18 module Data.List
19 (
20 #ifdef __NHC__
21 [] (..)
22 ,
23 #endif
24
25 -- * Basic functions
26
27 (++) -- :: [a] -> [a] -> [a]
28 , head -- :: [a] -> a
29 , last -- :: [a] -> a
30 , tail -- :: [a] -> [a]
31 , init -- :: [a] -> [a]
32 , null -- :: [a] -> Bool
33 , length -- :: [a] -> Int
34
35 -- * List transformations
36 , map -- :: (a -> b) -> [a] -> [b]
37 , reverse -- :: [a] -> [a]
38
39 , intersperse -- :: a -> [a] -> [a]
40 , intercalate -- :: [a] -> [[a]] -> [a]
41 , transpose -- :: [[a]] -> [[a]]
42
43 , subsequences -- :: [a] -> [[a]]
44 , permutations -- :: [a] -> [[a]]
45
46 -- * Reducing lists (folds)
47
48 , foldl -- :: (a -> b -> a) -> a -> [b] -> a
49 , foldl' -- :: (a -> b -> a) -> a -> [b] -> a
50 , foldl1 -- :: (a -> a -> a) -> [a] -> a
51 , foldl1' -- :: (a -> a -> a) -> [a] -> a
52 , foldr -- :: (a -> b -> b) -> b -> [a] -> b
53 , foldr1 -- :: (a -> a -> a) -> [a] -> a
54
55 -- ** Special folds
56
57 , concat -- :: [[a]] -> [a]
58 , concatMap -- :: (a -> [b]) -> [a] -> [b]
59 , and -- :: [Bool] -> Bool
60 , or -- :: [Bool] -> Bool
61 , any -- :: (a -> Bool) -> [a] -> Bool
62 , all -- :: (a -> Bool) -> [a] -> Bool
63 , sum -- :: (Num a) => [a] -> a
64 , product -- :: (Num a) => [a] -> a
65 , maximum -- :: (Ord a) => [a] -> a
66 , minimum -- :: (Ord a) => [a] -> a
67
68 -- * Building lists
69
70 -- ** Scans
71 , scanl -- :: (a -> b -> a) -> a -> [b] -> [a]
72 , scanl1 -- :: (a -> a -> a) -> [a] -> [a]
73 , scanr -- :: (a -> b -> b) -> b -> [a] -> [b]
74 , scanr1 -- :: (a -> a -> a) -> [a] -> [a]
75
76 -- ** Accumulating maps
77 , mapAccumL -- :: (a -> b -> (a,c)) -> a -> [b] -> (a,[c])
78 , mapAccumR -- :: (a -> b -> (a,c)) -> a -> [b] -> (a,[c])
79
80 -- ** Infinite lists
81 , iterate -- :: (a -> a) -> a -> [a]
82 , repeat -- :: a -> [a]
83 , replicate -- :: Int -> a -> [a]
84 , cycle -- :: [a] -> [a]
85
86 -- ** Unfolding
87 , unfoldr -- :: (b -> Maybe (a, b)) -> b -> [a]
88
89 -- * Sublists
90
91 -- ** Extracting sublists
92 , take -- :: Int -> [a] -> [a]
93 , drop -- :: Int -> [a] -> [a]
94 , splitAt -- :: Int -> [a] -> ([a], [a])
95
96 , takeWhile -- :: (a -> Bool) -> [a] -> [a]
97 , dropWhile -- :: (a -> Bool) -> [a] -> [a]
98 , span -- :: (a -> Bool) -> [a] -> ([a], [a])
99 , break -- :: (a -> Bool) -> [a] -> ([a], [a])
100
101 , stripPrefix -- :: Eq a => [a] -> [a] -> Maybe [a]
102
103 , group -- :: Eq a => [a] -> [[a]]
104
105 , inits -- :: [a] -> [[a]]
106 , tails -- :: [a] -> [[a]]
107
108 -- ** Predicates
109 , isPrefixOf -- :: (Eq a) => [a] -> [a] -> Bool
110 , isSuffixOf -- :: (Eq a) => [a] -> [a] -> Bool
111 , isInfixOf -- :: (Eq a) => [a] -> [a] -> Bool
112
113 -- * Searching lists
114
115 -- ** Searching by equality
116 , elem -- :: a -> [a] -> Bool
117 , notElem -- :: a -> [a] -> Bool
118 , lookup -- :: (Eq a) => a -> [(a,b)] -> Maybe b
119
120 -- ** Searching with a predicate
121 , find -- :: (a -> Bool) -> [a] -> Maybe a
122 , filter -- :: (a -> Bool) -> [a] -> [a]
123 , partition -- :: (a -> Bool) -> [a] -> ([a], [a])
124
125 -- * Indexing lists
126 -- | These functions treat a list @xs@ as a indexed collection,
127 -- with indices ranging from 0 to @'length' xs - 1@.
128
129 , (!!) -- :: [a] -> Int -> a
130
131 , elemIndex -- :: (Eq a) => a -> [a] -> Maybe Int
132 , elemIndices -- :: (Eq a) => a -> [a] -> [Int]
133
134 , findIndex -- :: (a -> Bool) -> [a] -> Maybe Int
135 , findIndices -- :: (a -> Bool) -> [a] -> [Int]
136
137 -- * Zipping and unzipping lists
138
139 , zip -- :: [a] -> [b] -> [(a,b)]
140 , zip3
141 , zip4, zip5, zip6, zip7
142
143 , zipWith -- :: (a -> b -> c) -> [a] -> [b] -> [c]
144 , zipWith3
145 , zipWith4, zipWith5, zipWith6, zipWith7
146
147 , unzip -- :: [(a,b)] -> ([a],[b])
148 , unzip3
149 , unzip4, unzip5, unzip6, unzip7
150
151 -- * Special lists
152
153 -- ** Functions on strings
154 , lines -- :: String -> [String]
155 , words -- :: String -> [String]
156 , unlines -- :: [String] -> String
157 , unwords -- :: [String] -> String
158
159 -- ** \"Set\" operations
160
161 , nub -- :: (Eq a) => [a] -> [a]
162
163 , delete -- :: (Eq a) => a -> [a] -> [a]
164 , (\\) -- :: (Eq a) => [a] -> [a] -> [a]
165
166 , union -- :: (Eq a) => [a] -> [a] -> [a]
167 , intersect -- :: (Eq a) => [a] -> [a] -> [a]
168
169 -- ** Ordered lists
170 , sort -- :: (Ord a) => [a] -> [a]
171 , insert -- :: (Ord a) => a -> [a] -> [a]
172
173 -- * Generalized functions
174
175 -- ** The \"@By@\" operations
176 -- | By convention, overloaded functions have a non-overloaded
177 -- counterpart whose name is suffixed with \`@By@\'.
178 --
179 -- It is often convenient to use these functions together with
180 -- 'Data.Function.on', for instance @'sortBy' ('compare'
181 -- \`on\` 'fst')@.
182
183 -- *** User-supplied equality (replacing an @Eq@ context)
184 -- | The predicate is assumed to define an equivalence.
185 , nubBy -- :: (a -> a -> Bool) -> [a] -> [a]
186 , deleteBy -- :: (a -> a -> Bool) -> a -> [a] -> [a]
187 , deleteFirstsBy -- :: (a -> a -> Bool) -> [a] -> [a] -> [a]
188 , unionBy -- :: (a -> a -> Bool) -> [a] -> [a] -> [a]
189 , intersectBy -- :: (a -> a -> Bool) -> [a] -> [a] -> [a]
190 , groupBy -- :: (a -> a -> Bool) -> [a] -> [[a]]
191
192 -- *** User-supplied comparison (replacing an @Ord@ context)
193 -- | The function is assumed to define a total ordering.
194 , sortBy -- :: (a -> a -> Ordering) -> [a] -> [a]
195 , insertBy -- :: (a -> a -> Ordering) -> a -> [a] -> [a]
196 , maximumBy -- :: (a -> a -> Ordering) -> [a] -> a
197 , minimumBy -- :: (a -> a -> Ordering) -> [a] -> a
198
199 -- ** The \"@generic@\" operations
200 -- | The prefix \`@generic@\' indicates an overloaded function that
201 -- is a generalized version of a "Prelude" function.
202
203 , genericLength -- :: (Integral a) => [b] -> a
204 , genericTake -- :: (Integral a) => a -> [b] -> [b]
205 , genericDrop -- :: (Integral a) => a -> [b] -> [b]
206 , genericSplitAt -- :: (Integral a) => a -> [b] -> ([b], [b])
207 , genericIndex -- :: (Integral a) => [b] -> a -> b
208 , genericReplicate -- :: (Integral a) => a -> b -> [b]
209
210 ) where
211
212 #ifdef __NHC__
213 import Prelude
214 #endif
215
216 import Data.Maybe
217 import Data.Char ( isSpace )
218
219 #ifdef __GLASGOW_HASKELL__
220 import GHC.Num
221 import GHC.Real
222 import GHC.List
223 import GHC.Base
224 #endif
225
226 infix 5 \\ -- comment to fool cpp
227
228 -- -----------------------------------------------------------------------------
229 -- List functions
230
231 -- | The 'stripPrefix' function drops the given prefix from a list.
232 -- It returns 'Nothing' if the list did not start with the prefix
233 -- given, or 'Just' the list after the prefix, if it does.
234 --
235 -- > stripPrefix "foo" "foobar" == Just "bar"
236 -- > stripPrefix "foo" "foo" == Just ""
237 -- > stripPrefix "foo" "barfoo" == Nothing
238 -- > stripPrefix "foo" "barfoobaz" == Nothing
239 stripPrefix :: Eq a => [a] -> [a] -> Maybe [a]
240 stripPrefix [] ys = Just ys
241 stripPrefix (x:xs) (y:ys)
242 | x == y = stripPrefix xs ys
243 stripPrefix _ _ = Nothing
244
245 -- | The 'elemIndex' function returns the index of the first element
246 -- in the given list which is equal (by '==') to the query element,
247 -- or 'Nothing' if there is no such element.
248 elemIndex :: Eq a => a -> [a] -> Maybe Int
249 elemIndex x = findIndex (x==)
250
251 -- | The 'elemIndices' function extends 'elemIndex', by returning the
252 -- indices of all elements equal to the query element, in ascending order.
253 elemIndices :: Eq a => a -> [a] -> [Int]
254 elemIndices x = findIndices (x==)
255
256 -- | The 'find' function takes a predicate and a list and returns the
257 -- first element in the list matching the predicate, or 'Nothing' if
258 -- there is no such element.
259 find :: (a -> Bool) -> [a] -> Maybe a
260 find p = listToMaybe . filter p
261
262 -- | The 'findIndex' function takes a predicate and a list and returns
263 -- the index of the first element in the list satisfying the predicate,
264 -- or 'Nothing' if there is no such element.
265 findIndex :: (a -> Bool) -> [a] -> Maybe Int
266 findIndex p = listToMaybe . findIndices p
267
268 -- | The 'findIndices' function extends 'findIndex', by returning the
269 -- indices of all elements satisfying the predicate, in ascending order.
270 findIndices :: (a -> Bool) -> [a] -> [Int]
271
272 #if defined(USE_REPORT_PRELUDE) || !defined(__GLASGOW_HASKELL__)
273 findIndices p xs = [ i | (x,i) <- zip xs [0..], p x]
274 #else
275 -- Efficient definition
276 findIndices p ls = loop 0# ls
277 where
278 loop _ [] = []
279 loop n (x:xs) | p x = I# n : loop (n +# 1#) xs
280 | otherwise = loop (n +# 1#) xs
281 #endif /* USE_REPORT_PRELUDE */
282
283 -- | The 'isPrefixOf' function takes two lists and returns 'True'
284 -- iff the first list is a prefix of the second.
285 isPrefixOf :: (Eq a) => [a] -> [a] -> Bool
286 isPrefixOf [] _ = True
287 isPrefixOf _ [] = False
288 isPrefixOf (x:xs) (y:ys)= x == y && isPrefixOf xs ys
289
290 -- | The 'isSuffixOf' function takes two lists and returns 'True'
291 -- iff the first list is a suffix of the second.
292 -- Both lists must be finite.
293 isSuffixOf :: (Eq a) => [a] -> [a] -> Bool
294 isSuffixOf x y = reverse x `isPrefixOf` reverse y
295
296 -- | The 'isInfixOf' function takes two lists and returns 'True'
297 -- iff the first list is contained, wholly and intact,
298 -- anywhere within the second.
299 --
300 -- Example:
301 --
302 -- >isInfixOf "Haskell" "I really like Haskell." == True
303 -- >isInfixOf "Ial" "I really like Haskell." == False
304 isInfixOf :: (Eq a) => [a] -> [a] -> Bool
305 isInfixOf needle haystack = any (isPrefixOf needle) (tails haystack)
306
307 -- | /O(n^2)/. The 'nub' function removes duplicate elements from a list.
308 -- In particular, it keeps only the first occurrence of each element.
309 -- (The name 'nub' means \`essence\'.)
310 -- It is a special case of 'nubBy', which allows the programmer to supply
311 -- their own equality test.
312 nub :: (Eq a) => [a] -> [a]
313 #ifdef USE_REPORT_PRELUDE
314 nub = nubBy (==)
315 #else
316 -- stolen from HBC
317 nub l = nub' l [] -- '
318 where
319 nub' [] _ = [] -- '
320 nub' (x:xs) ls -- '
321 | x `elem` ls = nub' xs ls -- '
322 | otherwise = x : nub' xs (x:ls) -- '
323 #endif
324
325 -- | The 'nubBy' function behaves just like 'nub', except it uses a
326 -- user-supplied equality predicate instead of the overloaded '=='
327 -- function.
328 nubBy :: (a -> a -> Bool) -> [a] -> [a]
329 #ifdef USE_REPORT_PRELUDE
330 nubBy eq [] = []
331 nubBy eq (x:xs) = x : nubBy eq (filter (\ y -> not (eq x y)) xs)
332 #else
333 nubBy eq l = nubBy' l []
334 where
335 nubBy' [] _ = []
336 nubBy' (y:ys) xs
337 | elem_by eq y xs = nubBy' ys xs
338 | otherwise = y : nubBy' ys (y:xs)
339
340 -- Not exported:
341 -- Note that we keep the call to `eq` with arguments in the
342 -- same order as in the reference implementation
343 -- 'xs' is the list of things we've seen so far,
344 -- 'y' is the potential new element
345 elem_by :: (a -> a -> Bool) -> a -> [a] -> Bool
346 elem_by _ _ [] = False
347 elem_by eq y (x:xs) = y `eq` x || elem_by eq y xs
348 #endif
349
350
351 -- | 'delete' @x@ removes the first occurrence of @x@ from its list argument.
352 -- For example,
353 --
354 -- > delete 'a' "banana" == "bnana"
355 --
356 -- It is a special case of 'deleteBy', which allows the programmer to
357 -- supply their own equality test.
358
359 delete :: (Eq a) => a -> [a] -> [a]
360 delete = deleteBy (==)
361
362 -- | The 'deleteBy' function behaves like 'delete', but takes a
363 -- user-supplied equality predicate.
364 deleteBy :: (a -> a -> Bool) -> a -> [a] -> [a]
365 deleteBy _ _ [] = []
366 deleteBy eq x (y:ys) = if x `eq` y then ys else y : deleteBy eq x ys
367
368 -- | The '\\' function is list difference ((non-associative).
369 -- In the result of @xs@ '\\' @ys@, the first occurrence of each element of
370 -- @ys@ in turn (if any) has been removed from @xs@. Thus
371 --
372 -- > (xs ++ ys) \\ xs == ys.
373 --
374 -- It is a special case of 'deleteFirstsBy', which allows the programmer
375 -- to supply their own equality test.
376
377 (\\) :: (Eq a) => [a] -> [a] -> [a]
378 (\\) = foldl (flip delete)
379
380 -- | The 'union' function returns the list union of the two lists.
381 -- For example,
382 --
383 -- > "dog" `union` "cow" == "dogcw"
384 --
385 -- Duplicates, and elements of the first list, are removed from the
386 -- the second list, but if the first list contains duplicates, so will
387 -- the result.
388 -- It is a special case of 'unionBy', which allows the programmer to supply
389 -- their own equality test.
390
391 union :: (Eq a) => [a] -> [a] -> [a]
392 union = unionBy (==)
393
394 -- | The 'unionBy' function is the non-overloaded version of 'union'.
395 unionBy :: (a -> a -> Bool) -> [a] -> [a] -> [a]
396 unionBy eq xs ys = xs ++ foldl (flip (deleteBy eq)) (nubBy eq ys) xs
397
398 -- | The 'intersect' function takes the list intersection of two lists.
399 -- For example,
400 --
401 -- > [1,2,3,4] `intersect` [2,4,6,8] == [2,4]
402 --
403 -- If the first list contains duplicates, so will the result.
404 --
405 -- > [1,2,2,3,4] `intersect` [6,4,4,2] == [2,2,4]
406 --
407 -- It is a special case of 'intersectBy', which allows the programmer to
408 -- supply their own equality test.
409
410 intersect :: (Eq a) => [a] -> [a] -> [a]
411 intersect = intersectBy (==)
412
413 -- | The 'intersectBy' function is the non-overloaded version of 'intersect'.
414 intersectBy :: (a -> a -> Bool) -> [a] -> [a] -> [a]
415 intersectBy _ [] _ = []
416 intersectBy _ _ [] = []
417 intersectBy eq xs ys = [x | x <- xs, any (eq x) ys]
418
419 -- | The 'intersperse' function takes an element and a list and
420 -- \`intersperses\' that element between the elements of the list.
421 -- For example,
422 --
423 -- > intersperse ',' "abcde" == "a,b,c,d,e"
424
425 intersperse :: a -> [a] -> [a]
426 intersperse _ [] = []
427 intersperse sep (x:xs) = x : prependToAll sep xs
428
429
430 -- Not exported:
431 -- We want to make every element in the 'intersperse'd list available
432 -- as soon as possible to avoid space leaks. Experiments suggested that
433 -- a separate top-level helper is more efficient than a local worker.
434 prependToAll :: a -> [a] -> [a]
435 prependToAll _ [] = []
436 prependToAll sep (x:xs) = sep : x : prependToAll sep xs
437
438 -- | 'intercalate' @xs xss@ is equivalent to @('concat' ('intersperse' xs xss))@.
439 -- It inserts the list @xs@ in between the lists in @xss@ and concatenates the
440 -- result.
441 intercalate :: [a] -> [[a]] -> [a]
442 intercalate xs xss = concat (intersperse xs xss)
443
444 -- | The 'transpose' function transposes the rows and columns of its argument.
445 -- For example,
446 --
447 -- > transpose [[1,2,3],[4,5,6]] == [[1,4],[2,5],[3,6]]
448
449 transpose :: [[a]] -> [[a]]
450 transpose [] = []
451 transpose ([] : xss) = transpose xss
452 transpose ((x:xs) : xss) = (x : [h | (h:_) <- xss]) : transpose (xs : [ t | (_:t) <- xss])
453
454
455 -- | The 'partition' function takes a predicate a list and returns
456 -- the pair of lists of elements which do and do not satisfy the
457 -- predicate, respectively; i.e.,
458 --
459 -- > partition p xs == (filter p xs, filter (not . p) xs)
460
461 partition :: (a -> Bool) -> [a] -> ([a],[a])
462 {-# INLINE partition #-}
463 partition p xs = foldr (select p) ([],[]) xs
464
465 select :: (a -> Bool) -> a -> ([a], [a]) -> ([a], [a])
466 select p x ~(ts,fs) | p x = (x:ts,fs)
467 | otherwise = (ts, x:fs)
468
469 -- | The 'mapAccumL' function behaves like a combination of 'map' and
470 -- 'foldl'; it applies a function to each element of a list, passing
471 -- an accumulating parameter from left to right, and returning a final
472 -- value of this accumulator together with the new list.
473 mapAccumL :: (acc -> x -> (acc, y)) -- Function of elt of input list
474 -- and accumulator, returning new
475 -- accumulator and elt of result list
476 -> acc -- Initial accumulator
477 -> [x] -- Input list
478 -> (acc, [y]) -- Final accumulator and result list
479 mapAccumL _ s [] = (s, [])
480 mapAccumL f s (x:xs) = (s'',y:ys)
481 where (s', y ) = f s x
482 (s'',ys) = mapAccumL f s' xs
483
484 -- | The 'mapAccumR' function behaves like a combination of 'map' and
485 -- 'foldr'; it applies a function to each element of a list, passing
486 -- an accumulating parameter from right to left, and returning a final
487 -- value of this accumulator together with the new list.
488 mapAccumR :: (acc -> x -> (acc, y)) -- Function of elt of input list
489 -- and accumulator, returning new
490 -- accumulator and elt of result list
491 -> acc -- Initial accumulator
492 -> [x] -- Input list
493 -> (acc, [y]) -- Final accumulator and result list
494 mapAccumR _ s [] = (s, [])
495 mapAccumR f s (x:xs) = (s'', y:ys)
496 where (s'',y ) = f s' x
497 (s', ys) = mapAccumR f s xs
498
499 -- | The 'insert' function takes an element and a list and inserts the
500 -- element into the list at the last position where it is still less
501 -- than or equal to the next element. In particular, if the list
502 -- is sorted before the call, the result will also be sorted.
503 -- It is a special case of 'insertBy', which allows the programmer to
504 -- supply their own comparison function.
505 insert :: Ord a => a -> [a] -> [a]
506 insert e ls = insertBy (compare) e ls
507
508 -- | The non-overloaded version of 'insert'.
509 insertBy :: (a -> a -> Ordering) -> a -> [a] -> [a]
510 insertBy _ x [] = [x]
511 insertBy cmp x ys@(y:ys')
512 = case cmp x y of
513 GT -> y : insertBy cmp x ys'
514 _ -> x : ys
515
516 #ifdef __GLASGOW_HASKELL__
517
518 -- | 'maximum' returns the maximum value from a list,
519 -- which must be non-empty, finite, and of an ordered type.
520 -- It is a special case of 'Data.List.maximumBy', which allows the
521 -- programmer to supply their own comparison function.
522 maximum :: (Ord a) => [a] -> a
523 maximum [] = errorEmptyList "maximum"
524 maximum xs = foldl1 max xs
525
526 {-# RULES
527 "maximumInt" maximum = (strictMaximum :: [Int] -> Int);
528 "maximumInteger" maximum = (strictMaximum :: [Integer] -> Integer)
529 #-}
530
531 -- We can't make the overloaded version of maximum strict without
532 -- changing its semantics (max might not be strict), but we can for
533 -- the version specialised to 'Int'.
534 strictMaximum :: (Ord a) => [a] -> a
535 strictMaximum [] = errorEmptyList "maximum"
536 strictMaximum xs = foldl1' max xs
537
538 -- | 'minimum' returns the minimum value from a list,
539 -- which must be non-empty, finite, and of an ordered type.
540 -- It is a special case of 'Data.List.minimumBy', which allows the
541 -- programmer to supply their own comparison function.
542 minimum :: (Ord a) => [a] -> a
543 minimum [] = errorEmptyList "minimum"
544 minimum xs = foldl1 min xs
545
546 {-# RULES
547 "minimumInt" minimum = (strictMinimum :: [Int] -> Int);
548 "minimumInteger" minimum = (strictMinimum :: [Integer] -> Integer)
549 #-}
550
551 strictMinimum :: (Ord a) => [a] -> a
552 strictMinimum [] = errorEmptyList "minimum"
553 strictMinimum xs = foldl1' min xs
554
555 #endif /* __GLASGOW_HASKELL__ */
556
557 -- | The 'maximumBy' function takes a comparison function and a list
558 -- and returns the greatest element of the list by the comparison function.
559 -- The list must be finite and non-empty.
560 maximumBy :: (a -> a -> Ordering) -> [a] -> a
561 maximumBy _ [] = error "List.maximumBy: empty list"
562 maximumBy cmp xs = foldl1 maxBy xs
563 where
564 maxBy x y = case cmp x y of
565 GT -> x
566 _ -> y
567
568 -- | The 'minimumBy' function takes a comparison function and a list
569 -- and returns the least element of the list by the comparison function.
570 -- The list must be finite and non-empty.
571 minimumBy :: (a -> a -> Ordering) -> [a] -> a
572 minimumBy _ [] = error "List.minimumBy: empty list"
573 minimumBy cmp xs = foldl1 minBy xs
574 where
575 minBy x y = case cmp x y of
576 GT -> y
577 _ -> x
578
579 -- | The 'genericLength' function is an overloaded version of 'length'. In
580 -- particular, instead of returning an 'Int', it returns any type which is
581 -- an instance of 'Num'. It is, however, less efficient than 'length'.
582 genericLength :: (Num i) => [b] -> i
583 genericLength [] = 0
584 genericLength (_:l) = 1 + genericLength l
585
586 {-# RULES
587 "genericLengthInt" genericLength = (strictGenericLength :: [a] -> Int);
588 "genericLengthInteger" genericLength = (strictGenericLength :: [a] -> Integer);
589 #-}
590
591 strictGenericLength :: (Num i) => [b] -> i
592 strictGenericLength l = gl l 0
593 where
594 gl [] a = a
595 gl (_:xs) a = let a' = a + 1 in a' `seq` gl xs a'
596
597 -- | The 'genericTake' function is an overloaded version of 'take', which
598 -- accepts any 'Integral' value as the number of elements to take.
599 genericTake :: (Integral i) => i -> [a] -> [a]
600 genericTake n _ | n <= 0 = []
601 genericTake _ [] = []
602 genericTake n (x:xs) = x : genericTake (n-1) xs
603
604 -- | The 'genericDrop' function is an overloaded version of 'drop', which
605 -- accepts any 'Integral' value as the number of elements to drop.
606 genericDrop :: (Integral i) => i -> [a] -> [a]
607 genericDrop n xs | n <= 0 = xs
608 genericDrop _ [] = []
609 genericDrop n (_:xs) = genericDrop (n-1) xs
610
611
612 -- | The 'genericSplitAt' function is an overloaded version of 'splitAt', which
613 -- accepts any 'Integral' value as the position at which to split.
614 genericSplitAt :: (Integral i) => i -> [b] -> ([b],[b])
615 genericSplitAt n xs | n <= 0 = ([],xs)
616 genericSplitAt _ [] = ([],[])
617 genericSplitAt n (x:xs) = (x:xs',xs'') where
618 (xs',xs'') = genericSplitAt (n-1) xs
619
620 -- | The 'genericIndex' function is an overloaded version of '!!', which
621 -- accepts any 'Integral' value as the index.
622 genericIndex :: (Integral a) => [b] -> a -> b
623 genericIndex (x:_) 0 = x
624 genericIndex (_:xs) n
625 | n > 0 = genericIndex xs (n-1)
626 | otherwise = error "List.genericIndex: negative argument."
627 genericIndex _ _ = error "List.genericIndex: index too large."
628
629 -- | The 'genericReplicate' function is an overloaded version of 'replicate',
630 -- which accepts any 'Integral' value as the number of repetitions to make.
631 genericReplicate :: (Integral i) => i -> a -> [a]
632 genericReplicate n x = genericTake n (repeat x)
633
634 -- | The 'zip4' function takes four lists and returns a list of
635 -- quadruples, analogous to 'zip'.
636 zip4 :: [a] -> [b] -> [c] -> [d] -> [(a,b,c,d)]
637 zip4 = zipWith4 (,,,)
638
639 -- | The 'zip5' function takes five lists and returns a list of
640 -- five-tuples, analogous to 'zip'.
641 zip5 :: [a] -> [b] -> [c] -> [d] -> [e] -> [(a,b,c,d,e)]
642 zip5 = zipWith5 (,,,,)
643
644 -- | The 'zip6' function takes six lists and returns a list of six-tuples,
645 -- analogous to 'zip'.
646 zip6 :: [a] -> [b] -> [c] -> [d] -> [e] -> [f] ->
647 [(a,b,c,d,e,f)]
648 zip6 = zipWith6 (,,,,,)
649
650 -- | The 'zip7' function takes seven lists and returns a list of
651 -- seven-tuples, analogous to 'zip'.
652 zip7 :: [a] -> [b] -> [c] -> [d] -> [e] -> [f] ->
653 [g] -> [(a,b,c,d,e,f,g)]
654 zip7 = zipWith7 (,,,,,,)
655
656 -- | The 'zipWith4' function takes a function which combines four
657 -- elements, as well as four lists and returns a list of their point-wise
658 -- combination, analogous to 'zipWith'.
659 zipWith4 :: (a->b->c->d->e) -> [a]->[b]->[c]->[d]->[e]
660 zipWith4 z (a:as) (b:bs) (c:cs) (d:ds)
661 = z a b c d : zipWith4 z as bs cs ds
662 zipWith4 _ _ _ _ _ = []
663
664 -- | The 'zipWith5' function takes a function which combines five
665 -- elements, as well as five lists and returns a list of their point-wise
666 -- combination, analogous to 'zipWith'.
667 zipWith5 :: (a->b->c->d->e->f) ->
668 [a]->[b]->[c]->[d]->[e]->[f]
669 zipWith5 z (a:as) (b:bs) (c:cs) (d:ds) (e:es)
670 = z a b c d e : zipWith5 z as bs cs ds es
671 zipWith5 _ _ _ _ _ _ = []
672
673 -- | The 'zipWith6' function takes a function which combines six
674 -- elements, as well as six lists and returns a list of their point-wise
675 -- combination, analogous to 'zipWith'.
676 zipWith6 :: (a->b->c->d->e->f->g) ->
677 [a]->[b]->[c]->[d]->[e]->[f]->[g]
678 zipWith6 z (a:as) (b:bs) (c:cs) (d:ds) (e:es) (f:fs)
679 = z a b c d e f : zipWith6 z as bs cs ds es fs
680 zipWith6 _ _ _ _ _ _ _ = []
681
682 -- | The 'zipWith7' function takes a function which combines seven
683 -- elements, as well as seven lists and returns a list of their point-wise
684 -- combination, analogous to 'zipWith'.
685 zipWith7 :: (a->b->c->d->e->f->g->h) ->
686 [a]->[b]->[c]->[d]->[e]->[f]->[g]->[h]
687 zipWith7 z (a:as) (b:bs) (c:cs) (d:ds) (e:es) (f:fs) (g:gs)
688 = z a b c d e f g : zipWith7 z as bs cs ds es fs gs
689 zipWith7 _ _ _ _ _ _ _ _ = []
690
691 -- | The 'unzip4' function takes a list of quadruples and returns four
692 -- lists, analogous to 'unzip'.
693 unzip4 :: [(a,b,c,d)] -> ([a],[b],[c],[d])
694 unzip4 = foldr (\(a,b,c,d) ~(as,bs,cs,ds) ->
695 (a:as,b:bs,c:cs,d:ds))
696 ([],[],[],[])
697
698 -- | The 'unzip5' function takes a list of five-tuples and returns five
699 -- lists, analogous to 'unzip'.
700 unzip5 :: [(a,b,c,d,e)] -> ([a],[b],[c],[d],[e])
701 unzip5 = foldr (\(a,b,c,d,e) ~(as,bs,cs,ds,es) ->
702 (a:as,b:bs,c:cs,d:ds,e:es))
703 ([],[],[],[],[])
704
705 -- | The 'unzip6' function takes a list of six-tuples and returns six
706 -- lists, analogous to 'unzip'.
707 unzip6 :: [(a,b,c,d,e,f)] -> ([a],[b],[c],[d],[e],[f])
708 unzip6 = foldr (\(a,b,c,d,e,f) ~(as,bs,cs,ds,es,fs) ->
709 (a:as,b:bs,c:cs,d:ds,e:es,f:fs))
710 ([],[],[],[],[],[])
711
712 -- | The 'unzip7' function takes a list of seven-tuples and returns
713 -- seven lists, analogous to 'unzip'.
714 unzip7 :: [(a,b,c,d,e,f,g)] -> ([a],[b],[c],[d],[e],[f],[g])
715 unzip7 = foldr (\(a,b,c,d,e,f,g) ~(as,bs,cs,ds,es,fs,gs) ->
716 (a:as,b:bs,c:cs,d:ds,e:es,f:fs,g:gs))
717 ([],[],[],[],[],[],[])
718
719
720 -- | The 'deleteFirstsBy' function takes a predicate and two lists and
721 -- returns the first list with the first occurrence of each element of
722 -- the second list removed.
723 deleteFirstsBy :: (a -> a -> Bool) -> [a] -> [a] -> [a]
724 deleteFirstsBy eq = foldl (flip (deleteBy eq))
725
726 -- | The 'group' function takes a list and returns a list of lists such
727 -- that the concatenation of the result is equal to the argument. Moreover,
728 -- each sublist in the result contains only equal elements. For example,
729 --
730 -- > group "Mississippi" = ["M","i","ss","i","ss","i","pp","i"]
731 --
732 -- It is a special case of 'groupBy', which allows the programmer to supply
733 -- their own equality test.
734 group :: Eq a => [a] -> [[a]]
735 group = groupBy (==)
736
737 -- | The 'groupBy' function is the non-overloaded version of 'group'.
738 groupBy :: (a -> a -> Bool) -> [a] -> [[a]]
739 groupBy _ [] = []
740 groupBy eq (x:xs) = (x:ys) : groupBy eq zs
741 where (ys,zs) = span (eq x) xs
742
743 -- | The 'inits' function returns all initial segments of the argument,
744 -- shortest first. For example,
745 --
746 -- > inits "abc" == ["","a","ab","abc"]
747 --
748 -- Note that 'inits' has the following strictness property:
749 -- @inits _|_ = [] : _|_@
750 inits :: [a] -> [[a]]
751 inits xs = [] : case xs of
752 [] -> []
753 x : xs' -> map (x :) (inits xs')
754
755 -- | The 'tails' function returns all final segments of the argument,
756 -- longest first. For example,
757 --
758 -- > tails "abc" == ["abc", "bc", "c",""]
759 --
760 -- Note that 'tails' has the following strictness property:
761 -- @tails _|_ = _|_ : _|_@
762 tails :: [a] -> [[a]]
763 tails xs = xs : case xs of
764 [] -> []
765 _ : xs' -> tails xs'
766
767 -- | The 'subsequences' function returns the list of all subsequences of the argument.
768 --
769 -- > subsequences "abc" == ["","a","b","ab","c","ac","bc","abc"]
770 subsequences :: [a] -> [[a]]
771 subsequences xs = [] : nonEmptySubsequences xs
772
773 -- | The 'nonEmptySubsequences' function returns the list of all subsequences of the argument,
774 -- except for the empty list.
775 --
776 -- > nonEmptySubsequences "abc" == ["a","b","ab","c","ac","bc","abc"]
777 nonEmptySubsequences :: [a] -> [[a]]
778 nonEmptySubsequences [] = []
779 nonEmptySubsequences (x:xs) = [x] : foldr f [] (nonEmptySubsequences xs)
780 where f ys r = ys : (x : ys) : r
781
782
783 -- | The 'permutations' function returns the list of all permutations of the argument.
784 --
785 -- > permutations "abc" == ["abc","bac","cba","bca","cab","acb"]
786 permutations :: [a] -> [[a]]
787 permutations xs0 = xs0 : perms xs0 []
788 where
789 perms [] _ = []
790 perms (t:ts) is = foldr interleave (perms ts (t:is)) (permutations is)
791 where interleave xs r = let (_,zs) = interleave' id xs r in zs
792 interleave' _ [] r = (ts, r)
793 interleave' f (y:ys) r = let (us,zs) = interleave' (f . (y:)) ys r
794 in (y:us, f (t:y:us) : zs)
795
796
797 ------------------------------------------------------------------------------
798 -- Quick Sort algorithm taken from HBC's QSort library.
799
800 -- | The 'sort' function implements a stable sorting algorithm.
801 -- It is a special case of 'sortBy', which allows the programmer to supply
802 -- their own comparison function.
803 sort :: (Ord a) => [a] -> [a]
804
805 -- | The 'sortBy' function is the non-overloaded version of 'sort'.
806 sortBy :: (a -> a -> Ordering) -> [a] -> [a]
807
808 #ifdef USE_REPORT_PRELUDE
809 sort = sortBy compare
810 sortBy cmp = foldr (insertBy cmp) []
811 #else
812
813 {-
814 GHC's mergesort replaced by a better implementation, 24/12/2009.
815 This code originally contributed to the nhc12 compiler by Thomas Nordin
816 in 2002. Rumoured to have been based on code by Lennart Augustsson, e.g.
817 http://www.mail-archive.com/haskell@haskell.org/msg01822.html
818 and possibly to bear similarities to a 1982 paper by Richard O'Keefe:
819 "A smooth applicative merge sort".
820
821 Benchmarks show it to be often 2x the speed of the previous implementation.
822 Fixes ticket http://hackage.haskell.org/trac/ghc/ticket/2143
823 -}
824
825 sort = sortBy compare
826 sortBy cmp = mergeAll . sequences
827 where
828 sequences (a:b:xs)
829 | a `cmp` b == GT = descending b [a] xs
830 | otherwise = ascending b (a:) xs
831 sequences xs = [xs]
832
833 descending a as (b:bs)
834 | a `cmp` b == GT = descending b (a:as) bs
835 descending a as bs = (a:as): sequences bs
836
837 ascending a as (b:bs)
838 | a `cmp` b /= GT = ascending b (\ys -> as (a:ys)) bs
839 ascending a as bs = as [a]: sequences bs
840
841 mergeAll [x] = x
842 mergeAll xs = mergeAll (mergePairs xs)
843
844 mergePairs (a:b:xs) = merge a b: mergePairs xs
845 mergePairs xs = xs
846
847 merge as@(a:as') bs@(b:bs')
848 | a `cmp` b == GT = b:merge as bs'
849 | otherwise = a:merge as' bs
850 merge [] bs = bs
851 merge as [] = as
852
853 {-
854 sortBy cmp l = mergesort cmp l
855 sort l = mergesort compare l
856
857 Quicksort replaced by mergesort, 14/5/2002.
858
859 From: Ian Lynagh <igloo@earth.li>
860
861 I am curious as to why the List.sort implementation in GHC is a
862 quicksort algorithm rather than an algorithm that guarantees n log n
863 time in the worst case? I have attached a mergesort implementation along
864 with a few scripts to time it's performance, the results of which are
865 shown below (* means it didn't finish successfully - in all cases this
866 was due to a stack overflow).
867
868 If I heap profile the random_list case with only 10000 then I see
869 random_list peaks at using about 2.5M of memory, whereas in the same
870 program using List.sort it uses only 100k.
871
872 Input style Input length Sort data Sort alg User time
873 stdin 10000 random_list sort 2.82
874 stdin 10000 random_list mergesort 2.96
875 stdin 10000 sorted sort 31.37
876 stdin 10000 sorted mergesort 1.90
877 stdin 10000 revsorted sort 31.21
878 stdin 10000 revsorted mergesort 1.88
879 stdin 100000 random_list sort *
880 stdin 100000 random_list mergesort *
881 stdin 100000 sorted sort *
882 stdin 100000 sorted mergesort *
883 stdin 100000 revsorted sort *
884 stdin 100000 revsorted mergesort *
885 func 10000 random_list sort 0.31
886 func 10000 random_list mergesort 0.91
887 func 10000 sorted sort 19.09
888 func 10000 sorted mergesort 0.15
889 func 10000 revsorted sort 19.17
890 func 10000 revsorted mergesort 0.16
891 func 100000 random_list sort 3.85
892 func 100000 random_list mergesort *
893 func 100000 sorted sort 5831.47
894 func 100000 sorted mergesort 2.23
895 func 100000 revsorted sort 5872.34
896 func 100000 revsorted mergesort 2.24
897
898 mergesort :: (a -> a -> Ordering) -> [a] -> [a]
899 mergesort cmp = mergesort' cmp . map wrap
900
901 mergesort' :: (a -> a -> Ordering) -> [[a]] -> [a]
902 mergesort' _ [] = []
903 mergesort' _ [xs] = xs
904 mergesort' cmp xss = mergesort' cmp (merge_pairs cmp xss)
905
906 merge_pairs :: (a -> a -> Ordering) -> [[a]] -> [[a]]
907 merge_pairs _ [] = []
908 merge_pairs _ [xs] = [xs]
909 merge_pairs cmp (xs:ys:xss) = merge cmp xs ys : merge_pairs cmp xss
910
911 merge :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
912 merge _ [] ys = ys
913 merge _ xs [] = xs
914 merge cmp (x:xs) (y:ys)
915 = case x `cmp` y of
916 GT -> y : merge cmp (x:xs) ys
917 _ -> x : merge cmp xs (y:ys)
918
919 wrap :: a -> [a]
920 wrap x = [x]
921
922
923
924 OLDER: qsort version
925
926 -- qsort is stable and does not concatenate.
927 qsort :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
928 qsort _ [] r = r
929 qsort _ [x] r = x:r
930 qsort cmp (x:xs) r = qpart cmp x xs [] [] r
931
932 -- qpart partitions and sorts the sublists
933 qpart :: (a -> a -> Ordering) -> a -> [a] -> [a] -> [a] -> [a] -> [a]
934 qpart cmp x [] rlt rge r =
935 -- rlt and rge are in reverse order and must be sorted with an
936 -- anti-stable sorting
937 rqsort cmp rlt (x:rqsort cmp rge r)
938 qpart cmp x (y:ys) rlt rge r =
939 case cmp x y of
940 GT -> qpart cmp x ys (y:rlt) rge r
941 _ -> qpart cmp x ys rlt (y:rge) r
942
943 -- rqsort is as qsort but anti-stable, i.e. reverses equal elements
944 rqsort :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
945 rqsort _ [] r = r
946 rqsort _ [x] r = x:r
947 rqsort cmp (x:xs) r = rqpart cmp x xs [] [] r
948
949 rqpart :: (a -> a -> Ordering) -> a -> [a] -> [a] -> [a] -> [a] -> [a]
950 rqpart cmp x [] rle rgt r =
951 qsort cmp rle (x:qsort cmp rgt r)
952 rqpart cmp x (y:ys) rle rgt r =
953 case cmp y x of
954 GT -> rqpart cmp x ys rle (y:rgt) r
955 _ -> rqpart cmp x ys (y:rle) rgt r
956 -}
957
958 #endif /* USE_REPORT_PRELUDE */
959
960 -- | The 'unfoldr' function is a \`dual\' to 'foldr': while 'foldr'
961 -- reduces a list to a summary value, 'unfoldr' builds a list from
962 -- a seed value. The function takes the element and returns 'Nothing'
963 -- if it is done producing the list or returns 'Just' @(a,b)@, in which
964 -- case, @a@ is a prepended to the list and @b@ is used as the next
965 -- element in a recursive call. For example,
966 --
967 -- > iterate f == unfoldr (\x -> Just (x, f x))
968 --
969 -- In some cases, 'unfoldr' can undo a 'foldr' operation:
970 --
971 -- > unfoldr f' (foldr f z xs) == xs
972 --
973 -- if the following holds:
974 --
975 -- > f' (f x y) = Just (x,y)
976 -- > f' z = Nothing
977 --
978 -- A simple use of unfoldr:
979 --
980 -- > unfoldr (\b -> if b == 0 then Nothing else Just (b, b-1)) 10
981 -- > [10,9,8,7,6,5,4,3,2,1]
982 --
983 unfoldr :: (b -> Maybe (a, b)) -> b -> [a]
984 unfoldr f b =
985 case f b of
986 Just (a,new_b) -> a : unfoldr f new_b
987 Nothing -> []
988
989 -- -----------------------------------------------------------------------------
990
991 -- | A strict version of 'foldl'.
992 foldl' :: (a -> b -> a) -> a -> [b] -> a
993 #ifdef __GLASGOW_HASKELL__
994 foldl' f z0 xs0 = lgo z0 xs0
995 where lgo z [] = z
996 lgo z (x:xs) = let z' = f z x in z' `seq` lgo z' xs
997 #else
998 foldl' f a [] = a
999 foldl' f a (x:xs) = let a' = f a x in a' `seq` foldl' f a' xs
1000 #endif
1001
1002 #ifdef __GLASGOW_HASKELL__
1003 -- | 'foldl1' is a variant of 'foldl' that has no starting value argument,
1004 -- and thus must be applied to non-empty lists.
1005 foldl1 :: (a -> a -> a) -> [a] -> a
1006 foldl1 f (x:xs) = foldl f x xs
1007 foldl1 _ [] = errorEmptyList "foldl1"
1008 #endif /* __GLASGOW_HASKELL__ */
1009
1010 -- | A strict version of 'foldl1'
1011 foldl1' :: (a -> a -> a) -> [a] -> a
1012 foldl1' f (x:xs) = foldl' f x xs
1013 foldl1' _ [] = errorEmptyList "foldl1'"
1014
1015 #ifdef __GLASGOW_HASKELL__
1016 -- -----------------------------------------------------------------------------
1017 -- List sum and product
1018
1019 {-# SPECIALISE sum :: [Int] -> Int #-}
1020 {-# SPECIALISE sum :: [Integer] -> Integer #-}
1021 {-# SPECIALISE product :: [Int] -> Int #-}
1022 {-# SPECIALISE product :: [Integer] -> Integer #-}
1023 -- | The 'sum' function computes the sum of a finite list of numbers.
1024 sum :: (Num a) => [a] -> a
1025 -- | The 'product' function computes the product of a finite list of numbers.
1026 product :: (Num a) => [a] -> a
1027 #ifdef USE_REPORT_PRELUDE
1028 sum = foldl (+) 0
1029 product = foldl (*) 1
1030 #else
1031 sum l = sum' l 0
1032 where
1033 sum' [] a = a
1034 sum' (x:xs) a = sum' xs (a+x)
1035 product l = prod l 1
1036 where
1037 prod [] a = a
1038 prod (x:xs) a = prod xs (a*x)
1039 #endif
1040
1041 -- -----------------------------------------------------------------------------
1042 -- Functions on strings
1043
1044 -- | 'lines' breaks a string up into a list of strings at newline
1045 -- characters. The resulting strings do not contain newlines.
1046 lines :: String -> [String]
1047 lines "" = []
1048 #ifdef __GLASGOW_HASKELL__
1049 -- Somehow GHC doesn't detect the selector thunks in the below code,
1050 -- so s' keeps a reference to the first line via the pair and we have
1051 -- a space leak (cf. #4334).
1052 -- So we need to make GHC see the selector thunks with a trick.
1053 lines s = cons (case break (== '\n') s of
1054 (l, s') -> (l, case s' of
1055 [] -> []
1056 _:s'' -> lines s''))
1057 where
1058 cons ~(h, t) = h : t
1059 #else
1060 lines s = let (l, s') = break (== '\n') s
1061 in l : case s' of
1062 [] -> []
1063 (_:s'') -> lines s''
1064 #endif
1065
1066 -- | 'unlines' is an inverse operation to 'lines'.
1067 -- It joins lines, after appending a terminating newline to each.
1068 unlines :: [String] -> String
1069 #ifdef USE_REPORT_PRELUDE
1070 unlines = concatMap (++ "\n")
1071 #else
1072 -- HBC version (stolen)
1073 -- here's a more efficient version
1074 unlines [] = []
1075 unlines (l:ls) = l ++ '\n' : unlines ls
1076 #endif
1077
1078 -- | 'words' breaks a string up into a list of words, which were delimited
1079 -- by white space.
1080 words :: String -> [String]
1081 words s = case dropWhile {-partain:Char.-}isSpace s of
1082 "" -> []
1083 s' -> w : words s''
1084 where (w, s'') =
1085 break {-partain:Char.-}isSpace s'
1086
1087 -- | 'unwords' is an inverse operation to 'words'.
1088 -- It joins words with separating spaces.
1089 unwords :: [String] -> String
1090 #ifdef USE_REPORT_PRELUDE
1091 unwords [] = ""
1092 unwords ws = foldr1 (\w s -> w ++ ' ':s) ws
1093 #else
1094 -- HBC version (stolen)
1095 -- here's a more efficient version
1096 unwords [] = ""
1097 unwords [w] = w
1098 unwords (w:ws) = w ++ ' ' : unwords ws
1099 #endif
1100
1101 #else /* !__GLASGOW_HASKELL__ */
1102
1103 errorEmptyList :: String -> a
1104 errorEmptyList fun =
1105 error ("Prelude." ++ fun ++ ": empty list")
1106
1107 #endif /* !__GLASGOW_HASKELL__ */