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