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