1 {-# LANGUAGE CPP, NoImplicitPrelude, MagicHash #-}
3 -----------------------------------------------------------------------------
6 -- Copyright : (c) The University of Glasgow 2001
7 -- License : BSD-style (see the file libraries/base/LICENSE)
9 -- Maintainer : libraries@haskell.org
11 -- Portability : portable
13 -- Operations on lists.
15 -----------------------------------------------------------------------------
26 (++) -- :: [a] -> [a] -> [a]
29 , tail -- :: [a] -> [a]
30 , init -- :: [a] -> [a]
31 , null -- :: [a] -> Bool
32 , length -- :: [a] -> Int
34 -- * List transformations
35 , map -- :: (a -> b) -> [a] -> [b]
36 , reverse -- :: [a] -> [a]
38 , intersperse -- :: a -> [a] -> [a]
39 , intercalate -- :: [a] -> [[a]] -> [a]
40 , transpose -- :: [[a]] -> [[a]]
42 , subsequences -- :: [a] -> [[a]]
43 , permutations -- :: [a] -> [[a]]
45 -- * Reducing lists (folds)
47 , foldl -- :: (a -> b -> a) -> a -> [b] -> a
48 , foldl' -- :: (a -> b -> a) -> a -> [b] -> a
49 , foldl1 -- :: (a -> a -> a) -> [a] -> a
50 , foldl1' -- :: (a -> a -> a) -> [a] -> a
51 , foldr -- :: (a -> b -> b) -> b -> [a] -> b
52 , foldr1 -- :: (a -> a -> a) -> [a] -> a
56 , concat -- :: [[a]] -> [a]
57 , concatMap -- :: (a -> [b]) -> [a] -> [b]
58 , and -- :: [Bool] -> Bool
59 , or -- :: [Bool] -> Bool
60 , any -- :: (a -> Bool) -> [a] -> Bool
61 , all -- :: (a -> Bool) -> [a] -> Bool
62 , sum -- :: (Num a) => [a] -> a
63 , product -- :: (Num a) => [a] -> a
64 , maximum -- :: (Ord a) => [a] -> a
65 , minimum -- :: (Ord a) => [a] -> a
70 , scanl -- :: (a -> b -> a) -> a -> [b] -> [a]
71 , scanl1 -- :: (a -> a -> a) -> [a] -> [a]
72 , scanr -- :: (a -> b -> b) -> b -> [a] -> [b]
73 , scanr1 -- :: (a -> a -> a) -> [a] -> [a]
75 -- ** Accumulating maps
76 , mapAccumL -- :: (a -> b -> (a,c)) -> a -> [b] -> (a,[c])
77 , mapAccumR -- :: (a -> b -> (a,c)) -> a -> [b] -> (a,[c])
80 , iterate -- :: (a -> a) -> a -> [a]
81 , repeat -- :: a -> [a]
82 , replicate -- :: Int -> a -> [a]
83 , cycle -- :: [a] -> [a]
86 , unfoldr -- :: (b -> Maybe (a, b)) -> b -> [a]
90 -- ** Extracting sublists
91 , take -- :: Int -> [a] -> [a]
92 , drop -- :: Int -> [a] -> [a]
93 , splitAt -- :: Int -> [a] -> ([a], [a])
95 , takeWhile -- :: (a -> Bool) -> [a] -> [a]
96 , dropWhile -- :: (a -> Bool) -> [a] -> [a]
97 , span -- :: (a -> Bool) -> [a] -> ([a], [a])
98 , break -- :: (a -> Bool) -> [a] -> ([a], [a])
100 , stripPrefix -- :: Eq a => [a] -> [a] -> Maybe [a]
102 , group -- :: Eq a => [a] -> [[a]]
104 , inits -- :: [a] -> [[a]]
105 , tails -- :: [a] -> [[a]]
108 , isPrefixOf -- :: (Eq a) => [a] -> [a] -> Bool
109 , isSuffixOf -- :: (Eq a) => [a] -> [a] -> Bool
110 , isInfixOf -- :: (Eq a) => [a] -> [a] -> Bool
114 -- ** Searching by equality
115 , elem -- :: a -> [a] -> Bool
116 , notElem -- :: a -> [a] -> Bool
117 , lookup -- :: (Eq a) => a -> [(a,b)] -> Maybe b
119 -- ** Searching with a predicate
120 , find -- :: (a -> Bool) -> [a] -> Maybe a
121 , filter -- :: (a -> Bool) -> [a] -> [a]
122 , partition -- :: (a -> Bool) -> [a] -> ([a], [a])
125 -- | These functions treat a list @xs@ as a indexed collection,
126 -- with indices ranging from 0 to @'length' xs - 1@.
128 , (!!) -- :: [a] -> Int -> a
130 , elemIndex -- :: (Eq a) => a -> [a] -> Maybe Int
131 , elemIndices -- :: (Eq a) => a -> [a] -> [Int]
133 , findIndex -- :: (a -> Bool) -> [a] -> Maybe Int
134 , findIndices -- :: (a -> Bool) -> [a] -> [Int]
136 -- * Zipping and unzipping lists
138 , zip -- :: [a] -> [b] -> [(a,b)]
140 , zip4, zip5, zip6, zip7
142 , zipWith -- :: (a -> b -> c) -> [a] -> [b] -> [c]
144 , zipWith4, zipWith5, zipWith6, zipWith7
146 , unzip -- :: [(a,b)] -> ([a],[b])
148 , unzip4, unzip5, unzip6, unzip7
152 -- ** Functions on strings
153 , lines -- :: String -> [String]
154 , words -- :: String -> [String]
155 , unlines -- :: [String] -> String
156 , unwords -- :: [String] -> String
158 -- ** \"Set\" operations
160 , nub -- :: (Eq a) => [a] -> [a]
162 , delete -- :: (Eq a) => a -> [a] -> [a]
163 , (\\) -- :: (Eq a) => [a] -> [a] -> [a]
165 , union -- :: (Eq a) => [a] -> [a] -> [a]
166 , intersect -- :: (Eq a) => [a] -> [a] -> [a]
169 , sort -- :: (Ord a) => [a] -> [a]
170 , insert -- :: (Ord a) => a -> [a] -> [a]
172 -- * Generalized functions
174 -- ** The \"@By@\" operations
175 -- | By convention, overloaded functions have a non-overloaded
176 -- counterpart whose name is suffixed with \`@By@\'.
178 -- It is often convenient to use these functions together with
179 -- 'Data.Function.on', for instance @'sortBy' ('compare'
182 -- *** User-supplied equality (replacing an @Eq@ context)
183 -- | The predicate is assumed to define an equivalence.
184 , nubBy -- :: (a -> a -> Bool) -> [a] -> [a]
185 , deleteBy -- :: (a -> a -> Bool) -> a -> [a] -> [a]
186 , deleteFirstsBy -- :: (a -> a -> Bool) -> [a] -> [a] -> [a]
187 , unionBy -- :: (a -> a -> Bool) -> [a] -> [a] -> [a]
188 , intersectBy -- :: (a -> a -> Bool) -> [a] -> [a] -> [a]
189 , groupBy -- :: (a -> a -> Bool) -> [a] -> [[a]]
191 -- *** User-supplied comparison (replacing an @Ord@ context)
192 -- | The function is assumed to define a total ordering.
193 , sortBy -- :: (a -> a -> Ordering) -> [a] -> [a]
194 , insertBy -- :: (a -> a -> Ordering) -> a -> [a] -> [a]
195 , maximumBy -- :: (a -> a -> Ordering) -> [a] -> a
196 , minimumBy -- :: (a -> a -> Ordering) -> [a] -> a
198 -- ** The \"@generic@\" operations
199 -- | The prefix \`@generic@\' indicates an overloaded function that
200 -- is a generalized version of a "Prelude" function.
202 , genericLength -- :: (Integral a) => [b] -> a
203 , genericTake -- :: (Integral a) => a -> [b] -> [b]
204 , genericDrop -- :: (Integral a) => a -> [b] -> [b]
205 , genericSplitAt -- :: (Integral a) => a -> [b] -> ([b], [b])
206 , genericIndex -- :: (Integral a) => [b] -> a -> b
207 , genericReplicate -- :: (Integral a) => a -> b -> [b]
216 import Data.Char ( isSpace )
218 #ifdef __GLASGOW_HASKELL__
225 infix 5 \\ -- comment to fool cpp
227 -- -----------------------------------------------------------------------------
230 -- | The 'stripPrefix' function drops the given prefix from a list.
231 -- It returns 'Nothing' if the list did not start with the prefix
232 -- given, or 'Just' the list after the prefix, if it does.
234 -- > stripPrefix "foo" "foobar" == Just "bar"
235 -- > stripPrefix "foo" "foo" == Just ""
236 -- > stripPrefix "foo" "barfoo" == Nothing
237 -- > stripPrefix "foo" "barfoobaz" == Nothing
238 stripPrefix :: Eq a => [a] -> [a] -> Maybe [a]
239 stripPrefix [] ys = Just ys
240 stripPrefix (x:xs) (y:ys)
241 | x == y = stripPrefix xs ys
242 stripPrefix _ _ = Nothing
244 -- | The 'elemIndex' function returns the index of the first element
245 -- in the given list which is equal (by '==') to the query element,
246 -- or 'Nothing' if there is no such element.
247 elemIndex :: Eq a => a -> [a] -> Maybe Int
248 elemIndex x = findIndex (x==)
250 -- | The 'elemIndices' function extends 'elemIndex', by returning the
251 -- indices of all elements equal to the query element, in ascending order.
252 elemIndices :: Eq a => a -> [a] -> [Int]
253 elemIndices x = findIndices (x==)
255 -- | The 'find' function takes a predicate and a list and returns the
256 -- first element in the list matching the predicate, or 'Nothing' if
257 -- there is no such element.
258 find :: (a -> Bool) -> [a] -> Maybe a
259 find p = listToMaybe . filter p
261 -- | The 'findIndex' function takes a predicate and a list and returns
262 -- the index of the first element in the list satisfying the predicate,
263 -- or 'Nothing' if there is no such element.
264 findIndex :: (a -> Bool) -> [a] -> Maybe Int
265 findIndex p = listToMaybe . findIndices p
267 -- | The 'findIndices' function extends 'findIndex', by returning the
268 -- indices of all elements satisfying the predicate, in ascending order.
269 findIndices :: (a -> Bool) -> [a] -> [Int]
271 #if defined(USE_REPORT_PRELUDE) || !defined(__GLASGOW_HASKELL__)
272 findIndices p xs = [ i | (x,i) <- zip xs [0..], p x]
274 -- Efficient definition
275 findIndices p ls = loop 0# ls
278 loop n (x:xs) | p x = I# n : loop (n +# 1#) xs
279 | otherwise = loop (n +# 1#) xs
280 #endif /* USE_REPORT_PRELUDE */
282 -- | The 'isPrefixOf' function takes two lists and returns 'True'
283 -- iff the first list is a prefix of the second.
284 isPrefixOf :: (Eq a) => [a] -> [a] -> Bool
285 isPrefixOf [] _ = True
286 isPrefixOf _ [] = False
287 isPrefixOf (x:xs) (y:ys)= x == y && isPrefixOf xs ys
289 -- | The 'isSuffixOf' function takes two lists and returns 'True'
290 -- iff the first list is a suffix of the second.
291 -- Both lists must be finite.
292 isSuffixOf :: (Eq a) => [a] -> [a] -> Bool
293 isSuffixOf x y = reverse x `isPrefixOf` reverse y
295 -- | The 'isInfixOf' function takes two lists and returns 'True'
296 -- iff the first list is contained, wholly and intact,
297 -- anywhere within the second.
301 -- >isInfixOf "Haskell" "I really like Haskell." == True
302 -- >isInfixOf "Ial" "I really like Haskell." == False
303 isInfixOf :: (Eq a) => [a] -> [a] -> Bool
304 isInfixOf needle haystack = any (isPrefixOf needle) (tails haystack)
306 -- | /O(n^2)/. The 'nub' function removes duplicate elements from a list.
307 -- In particular, it keeps only the first occurrence of each element.
308 -- (The name 'nub' means \`essence\'.)
309 -- It is a special case of 'nubBy', which allows the programmer to supply
310 -- their own equality test.
311 nub :: (Eq a) => [a] -> [a]
312 #ifdef USE_REPORT_PRELUDE
316 nub l = nub' l [] -- '
320 | x `elem` ls = nub' xs ls -- '
321 | otherwise = x : nub' xs (x:ls) -- '
324 -- | The 'nubBy' function behaves just like 'nub', except it uses a
325 -- user-supplied equality predicate instead of the overloaded '=='
327 nubBy :: (a -> a -> Bool) -> [a] -> [a]
328 #ifdef USE_REPORT_PRELUDE
330 nubBy eq (x:xs) = x : nubBy eq (filter (\ y -> not (eq x y)) xs)
332 nubBy eq l = nubBy' l []
336 | elem_by eq y xs = nubBy' ys xs
337 | otherwise = y : nubBy' ys (y:xs)
340 -- Note that we keep the call to `eq` with arguments in the
341 -- same order as in the reference implementation
342 -- 'xs' is the list of things we've seen so far,
343 -- 'y' is the potential new element
344 elem_by :: (a -> a -> Bool) -> a -> [a] -> Bool
345 elem_by _ _ [] = False
346 elem_by eq y (x:xs) = y `eq` x || elem_by eq y xs
350 -- | 'delete' @x@ removes the first occurrence of @x@ from its list argument.
353 -- > delete 'a' "banana" == "bnana"
355 -- It is a special case of 'deleteBy', which allows the programmer to
356 -- supply their own equality test.
358 delete :: (Eq a) => a -> [a] -> [a]
359 delete = deleteBy (==)
361 -- | The 'deleteBy' function behaves like 'delete', but takes a
362 -- user-supplied equality predicate.
363 deleteBy :: (a -> a -> Bool) -> a -> [a] -> [a]
365 deleteBy eq x (y:ys) = if x `eq` y then ys else y : deleteBy eq x ys
367 -- | The '\\' function is list difference ((non-associative).
368 -- In the result of @xs@ '\\' @ys@, the first occurrence of each element of
369 -- @ys@ in turn (if any) has been removed from @xs@. Thus
371 -- > (xs ++ ys) \\ xs == ys.
373 -- It is a special case of 'deleteFirstsBy', which allows the programmer
374 -- to supply their own equality test.
376 (\\) :: (Eq a) => [a] -> [a] -> [a]
377 (\\) = foldl (flip delete)
379 -- | The 'union' function returns the list union of the two lists.
382 -- > "dog" `union` "cow" == "dogcw"
384 -- Duplicates, and elements of the first list, are removed from the
385 -- the second list, but if the first list contains duplicates, so will
387 -- It is a special case of 'unionBy', which allows the programmer to supply
388 -- their own equality test.
390 union :: (Eq a) => [a] -> [a] -> [a]
393 -- | The 'unionBy' function is the non-overloaded version of 'union'.
394 unionBy :: (a -> a -> Bool) -> [a] -> [a] -> [a]
395 unionBy eq xs ys = xs ++ foldl (flip (deleteBy eq)) (nubBy eq ys) xs
397 -- | The 'intersect' function takes the list intersection of two lists.
400 -- > [1,2,3,4] `intersect` [2,4,6,8] == [2,4]
402 -- If the first list contains duplicates, so will the result.
404 -- > [1,2,2,3,4] `intersect` [6,4,4,2] == [2,2,4]
406 -- It is a special case of 'intersectBy', which allows the programmer to
407 -- supply their own equality test.
409 intersect :: (Eq a) => [a] -> [a] -> [a]
410 intersect = intersectBy (==)
412 -- | The 'intersectBy' function is the non-overloaded version of 'intersect'.
413 intersectBy :: (a -> a -> Bool) -> [a] -> [a] -> [a]
414 intersectBy _ [] _ = []
415 intersectBy _ _ [] = []
416 intersectBy eq xs ys = [x | x <- xs, any (eq x) ys]
418 -- | The 'intersperse' function takes an element and a list and
419 -- \`intersperses\' that element between the elements of the list.
422 -- > intersperse ',' "abcde" == "a,b,c,d,e"
424 intersperse :: a -> [a] -> [a]
425 intersperse _ [] = []
426 intersperse sep (x:xs) = x : prependToAll sep xs
430 -- We want to make every element in the 'intersperse'd list available
431 -- as soon as possible to avoid space leaks. Experiments suggested that
432 -- a separate top-level helper is more efficient than a local worker.
433 prependToAll :: a -> [a] -> [a]
434 prependToAll _ [] = []
435 prependToAll sep (x:xs) = sep : x : prependToAll sep xs
437 -- | 'intercalate' @xs xss@ is equivalent to @('concat' ('intersperse' xs xss))@.
438 -- It inserts the list @xs@ in between the lists in @xss@ and concatenates the
440 intercalate :: [a] -> [[a]] -> [a]
441 intercalate xs xss = concat (intersperse xs xss)
443 -- | The 'transpose' function transposes the rows and columns of its argument.
446 -- > transpose [[1,2,3],[4,5,6]] == [[1,4],[2,5],[3,6]]
448 transpose :: [[a]] -> [[a]]
450 transpose ([] : xss) = transpose xss
451 transpose ((x:xs) : xss) = (x : [h | (h:_) <- xss]) : transpose (xs : [ t | (_:t) <- xss])
454 -- | The 'partition' function takes a predicate a list and returns
455 -- the pair of lists of elements which do and do not satisfy the
456 -- predicate, respectively; i.e.,
458 -- > partition p xs == (filter p xs, filter (not . p) xs)
460 partition :: (a -> Bool) -> [a] -> ([a],[a])
461 {-# INLINE partition #-}
462 partition p xs = foldr (select p) ([],[]) xs
464 select :: (a -> Bool) -> a -> ([a], [a]) -> ([a], [a])
465 select p x ~(ts,fs) | p x = (x:ts,fs)
466 | otherwise = (ts, x:fs)
468 -- | The 'mapAccumL' function behaves like a combination of 'map' and
469 -- 'foldl'; it applies a function to each element of a list, passing
470 -- an accumulating parameter from left to right, and returning a final
471 -- value of this accumulator together with the new list.
472 mapAccumL :: (acc -> x -> (acc, y)) -- Function of elt of input list
473 -- and accumulator, returning new
474 -- accumulator and elt of result list
475 -> acc -- Initial accumulator
477 -> (acc, [y]) -- Final accumulator and result list
478 mapAccumL _ s [] = (s, [])
479 mapAccumL f s (x:xs) = (s'',y:ys)
480 where (s', y ) = f s x
481 (s'',ys) = mapAccumL f s' xs
483 -- | The 'mapAccumR' function behaves like a combination of 'map' and
484 -- 'foldr'; it applies a function to each element of a list, passing
485 -- an accumulating parameter from right to left, and returning a final
486 -- value of this accumulator together with the new list.
487 mapAccumR :: (acc -> x -> (acc, y)) -- Function of elt of input list
488 -- and accumulator, returning new
489 -- accumulator and elt of result list
490 -> acc -- Initial accumulator
492 -> (acc, [y]) -- Final accumulator and result list
493 mapAccumR _ s [] = (s, [])
494 mapAccumR f s (x:xs) = (s'', y:ys)
495 where (s'',y ) = f s' x
496 (s', ys) = mapAccumR f s xs
498 -- | The 'insert' function takes an element and a list and inserts the
499 -- element into the list at the last position where it is still less
500 -- than or equal to the next element. In particular, if the list
501 -- is sorted before the call, the result will also be sorted.
502 -- It is a special case of 'insertBy', which allows the programmer to
503 -- supply their own comparison function.
504 insert :: Ord a => a -> [a] -> [a]
505 insert e ls = insertBy (compare) e ls
507 -- | The non-overloaded version of 'insert'.
508 insertBy :: (a -> a -> Ordering) -> a -> [a] -> [a]
509 insertBy _ x [] = [x]
510 insertBy cmp x ys@(y:ys')
512 GT -> y : insertBy cmp x ys'
515 #ifdef __GLASGOW_HASKELL__
517 -- | 'maximum' returns the maximum value from a list,
518 -- which must be non-empty, finite, and of an ordered type.
519 -- It is a special case of 'Data.List.maximumBy', which allows the
520 -- programmer to supply their own comparison function.
521 maximum :: (Ord a) => [a] -> a
522 maximum [] = errorEmptyList "maximum"
523 maximum xs = foldl1 max xs
526 "maximumInt" maximum = (strictMaximum :: [Int] -> Int);
527 "maximumInteger" maximum = (strictMaximum :: [Integer] -> Integer)
530 -- We can't make the overloaded version of maximum strict without
531 -- changing its semantics (max might not be strict), but we can for
532 -- the version specialised to 'Int'.
533 strictMaximum :: (Ord a) => [a] -> a
534 strictMaximum [] = errorEmptyList "maximum"
535 strictMaximum xs = foldl1' max xs
537 -- | 'minimum' returns the minimum value from a list,
538 -- which must be non-empty, finite, and of an ordered type.
539 -- It is a special case of 'Data.List.minimumBy', which allows the
540 -- programmer to supply their own comparison function.
541 minimum :: (Ord a) => [a] -> a
542 minimum [] = errorEmptyList "minimum"
543 minimum xs = foldl1 min xs
546 "minimumInt" minimum = (strictMinimum :: [Int] -> Int);
547 "minimumInteger" minimum = (strictMinimum :: [Integer] -> Integer)
550 strictMinimum :: (Ord a) => [a] -> a
551 strictMinimum [] = errorEmptyList "minimum"
552 strictMinimum xs = foldl1' min xs
554 #endif /* __GLASGOW_HASKELL__ */
556 -- | The 'maximumBy' function takes a comparison function and a list
557 -- and returns the greatest element of the list by the comparison function.
558 -- The list must be finite and non-empty.
559 maximumBy :: (a -> a -> Ordering) -> [a] -> a
560 maximumBy _ [] = error "List.maximumBy: empty list"
561 maximumBy cmp xs = foldl1 maxBy xs
563 maxBy x y = case cmp x y of
567 -- | The 'minimumBy' function takes a comparison function and a list
568 -- and returns the least element of the list by the comparison function.
569 -- The list must be finite and non-empty.
570 minimumBy :: (a -> a -> Ordering) -> [a] -> a
571 minimumBy _ [] = error "List.minimumBy: empty list"
572 minimumBy cmp xs = foldl1 minBy xs
574 minBy x y = case cmp x y of
578 -- | The 'genericLength' function is an overloaded version of 'length'. In
579 -- particular, instead of returning an 'Int', it returns any type which is
580 -- an instance of 'Num'. It is, however, less efficient than 'length'.
581 genericLength :: (Num i) => [b] -> i
583 genericLength (_:l) = 1 + genericLength l
586 "genericLengthInt" genericLength = (strictGenericLength :: [a] -> Int);
587 "genericLengthInteger" genericLength = (strictGenericLength :: [a] -> Integer);
590 strictGenericLength :: (Num i) => [b] -> i
591 strictGenericLength l = gl l 0
594 gl (_:xs) a = let a' = a + 1 in a' `seq` gl xs a'
596 -- | The 'genericTake' function is an overloaded version of 'take', which
597 -- accepts any 'Integral' value as the number of elements to take.
598 genericTake :: (Integral i) => i -> [a] -> [a]
599 genericTake n _ | n <= 0 = []
600 genericTake _ [] = []
601 genericTake n (x:xs) = x : genericTake (n-1) xs
603 -- | The 'genericDrop' function is an overloaded version of 'drop', which
604 -- accepts any 'Integral' value as the number of elements to drop.
605 genericDrop :: (Integral i) => i -> [a] -> [a]
606 genericDrop n xs | n <= 0 = xs
607 genericDrop _ [] = []
608 genericDrop n (_:xs) = genericDrop (n-1) xs
611 -- | The 'genericSplitAt' function is an overloaded version of 'splitAt', which
612 -- accepts any 'Integral' value as the position at which to split.
613 genericSplitAt :: (Integral i) => i -> [b] -> ([b],[b])
614 genericSplitAt n xs | n <= 0 = ([],xs)
615 genericSplitAt _ [] = ([],[])
616 genericSplitAt n (x:xs) = (x:xs',xs'') where
617 (xs',xs'') = genericSplitAt (n-1) xs
619 -- | The 'genericIndex' function is an overloaded version of '!!', which
620 -- accepts any 'Integral' value as the index.
621 genericIndex :: (Integral a) => [b] -> a -> b
622 genericIndex (x:_) 0 = x
623 genericIndex (_:xs) n
624 | n > 0 = genericIndex xs (n-1)
625 | otherwise = error "List.genericIndex: negative argument."
626 genericIndex _ _ = error "List.genericIndex: index too large."
628 -- | The 'genericReplicate' function is an overloaded version of 'replicate',
629 -- which accepts any 'Integral' value as the number of repetitions to make.
630 genericReplicate :: (Integral i) => i -> a -> [a]
631 genericReplicate n x = genericTake n (repeat x)
633 -- | The 'zip4' function takes four lists and returns a list of
634 -- quadruples, analogous to 'zip'.
635 zip4 :: [a] -> [b] -> [c] -> [d] -> [(a,b,c,d)]
636 zip4 = zipWith4 (,,,)
638 -- | The 'zip5' function takes five lists and returns a list of
639 -- five-tuples, analogous to 'zip'.
640 zip5 :: [a] -> [b] -> [c] -> [d] -> [e] -> [(a,b,c,d,e)]
641 zip5 = zipWith5 (,,,,)
643 -- | The 'zip6' function takes six lists and returns a list of six-tuples,
644 -- analogous to 'zip'.
645 zip6 :: [a] -> [b] -> [c] -> [d] -> [e] -> [f] ->
647 zip6 = zipWith6 (,,,,,)
649 -- | The 'zip7' function takes seven lists and returns a list of
650 -- seven-tuples, analogous to 'zip'.
651 zip7 :: [a] -> [b] -> [c] -> [d] -> [e] -> [f] ->
652 [g] -> [(a,b,c,d,e,f,g)]
653 zip7 = zipWith7 (,,,,,,)
655 -- | The 'zipWith4' function takes a function which combines four
656 -- elements, as well as four lists and returns a list of their point-wise
657 -- combination, analogous to 'zipWith'.
658 zipWith4 :: (a->b->c->d->e) -> [a]->[b]->[c]->[d]->[e]
659 zipWith4 z (a:as) (b:bs) (c:cs) (d:ds)
660 = z a b c d : zipWith4 z as bs cs ds
661 zipWith4 _ _ _ _ _ = []
663 -- | The 'zipWith5' function takes a function which combines five
664 -- elements, as well as five lists and returns a list of their point-wise
665 -- combination, analogous to 'zipWith'.
666 zipWith5 :: (a->b->c->d->e->f) ->
667 [a]->[b]->[c]->[d]->[e]->[f]
668 zipWith5 z (a:as) (b:bs) (c:cs) (d:ds) (e:es)
669 = z a b c d e : zipWith5 z as bs cs ds es
670 zipWith5 _ _ _ _ _ _ = []
672 -- | The 'zipWith6' function takes a function which combines six
673 -- elements, as well as six lists and returns a list of their point-wise
674 -- combination, analogous to 'zipWith'.
675 zipWith6 :: (a->b->c->d->e->f->g) ->
676 [a]->[b]->[c]->[d]->[e]->[f]->[g]
677 zipWith6 z (a:as) (b:bs) (c:cs) (d:ds) (e:es) (f:fs)
678 = z a b c d e f : zipWith6 z as bs cs ds es fs
679 zipWith6 _ _ _ _ _ _ _ = []
681 -- | The 'zipWith7' function takes a function which combines seven
682 -- elements, as well as seven lists and returns a list of their point-wise
683 -- combination, analogous to 'zipWith'.
684 zipWith7 :: (a->b->c->d->e->f->g->h) ->
685 [a]->[b]->[c]->[d]->[e]->[f]->[g]->[h]
686 zipWith7 z (a:as) (b:bs) (c:cs) (d:ds) (e:es) (f:fs) (g:gs)
687 = z a b c d e f g : zipWith7 z as bs cs ds es fs gs
688 zipWith7 _ _ _ _ _ _ _ _ = []
690 -- | The 'unzip4' function takes a list of quadruples and returns four
691 -- lists, analogous to 'unzip'.
692 unzip4 :: [(a,b,c,d)] -> ([a],[b],[c],[d])
693 unzip4 = foldr (\(a,b,c,d) ~(as,bs,cs,ds) ->
694 (a:as,b:bs,c:cs,d:ds))
697 -- | The 'unzip5' function takes a list of five-tuples and returns five
698 -- lists, analogous to 'unzip'.
699 unzip5 :: [(a,b,c,d,e)] -> ([a],[b],[c],[d],[e])
700 unzip5 = foldr (\(a,b,c,d,e) ~(as,bs,cs,ds,es) ->
701 (a:as,b:bs,c:cs,d:ds,e:es))
704 -- | The 'unzip6' function takes a list of six-tuples and returns six
705 -- lists, analogous to 'unzip'.
706 unzip6 :: [(a,b,c,d,e,f)] -> ([a],[b],[c],[d],[e],[f])
707 unzip6 = foldr (\(a,b,c,d,e,f) ~(as,bs,cs,ds,es,fs) ->
708 (a:as,b:bs,c:cs,d:ds,e:es,f:fs))
711 -- | The 'unzip7' function takes a list of seven-tuples and returns
712 -- seven lists, analogous to 'unzip'.
713 unzip7 :: [(a,b,c,d,e,f,g)] -> ([a],[b],[c],[d],[e],[f],[g])
714 unzip7 = foldr (\(a,b,c,d,e,f,g) ~(as,bs,cs,ds,es,fs,gs) ->
715 (a:as,b:bs,c:cs,d:ds,e:es,f:fs,g:gs))
716 ([],[],[],[],[],[],[])
719 -- | The 'deleteFirstsBy' function takes a predicate and two lists and
720 -- returns the first list with the first occurrence of each element of
721 -- the second list removed.
722 deleteFirstsBy :: (a -> a -> Bool) -> [a] -> [a] -> [a]
723 deleteFirstsBy eq = foldl (flip (deleteBy eq))
725 -- | The 'group' function takes a list and returns a list of lists such
726 -- that the concatenation of the result is equal to the argument. Moreover,
727 -- each sublist in the result contains only equal elements. For example,
729 -- > group "Mississippi" = ["M","i","ss","i","ss","i","pp","i"]
731 -- It is a special case of 'groupBy', which allows the programmer to supply
732 -- their own equality test.
733 group :: Eq a => [a] -> [[a]]
736 -- | The 'groupBy' function is the non-overloaded version of 'group'.
737 groupBy :: (a -> a -> Bool) -> [a] -> [[a]]
739 groupBy eq (x:xs) = (x:ys) : groupBy eq zs
740 where (ys,zs) = span (eq x) xs
742 -- | The 'inits' function returns all initial segments of the argument,
743 -- shortest first. For example,
745 -- > inits "abc" == ["","a","ab","abc"]
747 -- Note that 'inits' has the following strictness property:
748 -- @inits _|_ = [] : _|_@
749 inits :: [a] -> [[a]]
750 inits xs = [] : case xs of
752 x : xs' -> map (x :) (inits xs')
754 -- | The 'tails' function returns all final segments of the argument,
755 -- longest first. For example,
757 -- > tails "abc" == ["abc", "bc", "c",""]
759 -- Note that 'tails' has the following strictness property:
760 -- @tails _|_ = _|_ : _|_@
761 tails :: [a] -> [[a]]
762 tails xs = xs : case xs of
766 -- | The 'subsequences' function returns the list of all subsequences of the argument.
768 -- > subsequences "abc" == ["","a","b","ab","c","ac","bc","abc"]
769 subsequences :: [a] -> [[a]]
770 subsequences xs = [] : nonEmptySubsequences xs
772 -- | The 'nonEmptySubsequences' function returns the list of all subsequences of the argument,
773 -- except for the empty list.
775 -- > nonEmptySubsequences "abc" == ["a","b","ab","c","ac","bc","abc"]
776 nonEmptySubsequences :: [a] -> [[a]]
777 nonEmptySubsequences [] = []
778 nonEmptySubsequences (x:xs) = [x] : foldr f [] (nonEmptySubsequences xs)
779 where f ys r = ys : (x : ys) : r
782 -- | The 'permutations' function returns the list of all permutations of the argument.
784 -- > permutations "abc" == ["abc","bac","cba","bca","cab","acb"]
785 permutations :: [a] -> [[a]]
786 permutations xs0 = xs0 : perms xs0 []
789 perms (t:ts) is = foldr interleave (perms ts (t:is)) (permutations is)
790 where interleave xs r = let (_,zs) = interleave' id xs r in zs
791 interleave' _ [] r = (ts, r)
792 interleave' f (y:ys) r = let (us,zs) = interleave' (f . (y:)) ys r
793 in (y:us, f (t:y:us) : zs)
796 ------------------------------------------------------------------------------
797 -- Quick Sort algorithm taken from HBC's QSort library.
799 -- | The 'sort' function implements a stable sorting algorithm.
800 -- It is a special case of 'sortBy', which allows the programmer to supply
801 -- their own comparison function.
802 sort :: (Ord a) => [a] -> [a]
804 -- | The 'sortBy' function is the non-overloaded version of 'sort'.
805 sortBy :: (a -> a -> Ordering) -> [a] -> [a]
807 #ifdef USE_REPORT_PRELUDE
808 sort = sortBy compare
809 sortBy cmp = foldr (insertBy cmp) []
813 GHC's mergesort replaced by a better implementation, 24/12/2009.
814 This code originally contributed to the nhc12 compiler by Thomas Nordin
815 in 2002. Rumoured to have been based on code by Lennart Augustsson, e.g.
816 http://www.mail-archive.com/haskell@haskell.org/msg01822.html
817 and possibly to bear similarities to a 1982 paper by Richard O'Keefe:
818 "A smooth applicative merge sort".
820 Benchmarks show it to be often 2x the speed of the previous implementation.
821 Fixes ticket http://hackage.haskell.org/trac/ghc/ticket/2143
824 sort = sortBy compare
825 sortBy cmp = mergeAll . sequences
828 | a `cmp` b == GT = descending b [a] xs
829 | otherwise = ascending b (a:) xs
832 descending a as (b:bs)
833 | a `cmp` b == GT = descending b (a:as) bs
834 descending a as bs = (a:as): sequences bs
836 ascending a as (b:bs)
837 | a `cmp` b /= GT = ascending b (\ys -> as (a:ys)) bs
838 ascending a as bs = as [a]: sequences bs
841 mergeAll xs = mergeAll (mergePairs xs)
843 mergePairs (a:b:xs) = merge a b: mergePairs xs
846 merge as@(a:as') bs@(b:bs')
847 | a `cmp` b == GT = b:merge as bs'
848 | otherwise = a:merge as' bs
853 sortBy cmp l = mergesort cmp l
854 sort l = mergesort compare l
856 Quicksort replaced by mergesort, 14/5/2002.
858 From: Ian Lynagh <igloo@earth.li>
860 I am curious as to why the List.sort implementation in GHC is a
861 quicksort algorithm rather than an algorithm that guarantees n log n
862 time in the worst case? I have attached a mergesort implementation along
863 with a few scripts to time it's performance, the results of which are
864 shown below (* means it didn't finish successfully - in all cases this
865 was due to a stack overflow).
867 If I heap profile the random_list case with only 10000 then I see
868 random_list peaks at using about 2.5M of memory, whereas in the same
869 program using List.sort it uses only 100k.
871 Input style Input length Sort data Sort alg User time
872 stdin 10000 random_list sort 2.82
873 stdin 10000 random_list mergesort 2.96
874 stdin 10000 sorted sort 31.37
875 stdin 10000 sorted mergesort 1.90
876 stdin 10000 revsorted sort 31.21
877 stdin 10000 revsorted mergesort 1.88
878 stdin 100000 random_list sort *
879 stdin 100000 random_list mergesort *
880 stdin 100000 sorted sort *
881 stdin 100000 sorted mergesort *
882 stdin 100000 revsorted sort *
883 stdin 100000 revsorted mergesort *
884 func 10000 random_list sort 0.31
885 func 10000 random_list mergesort 0.91
886 func 10000 sorted sort 19.09
887 func 10000 sorted mergesort 0.15
888 func 10000 revsorted sort 19.17
889 func 10000 revsorted mergesort 0.16
890 func 100000 random_list sort 3.85
891 func 100000 random_list mergesort *
892 func 100000 sorted sort 5831.47
893 func 100000 sorted mergesort 2.23
894 func 100000 revsorted sort 5872.34
895 func 100000 revsorted mergesort 2.24
897 mergesort :: (a -> a -> Ordering) -> [a] -> [a]
898 mergesort cmp = mergesort' cmp . map wrap
900 mergesort' :: (a -> a -> Ordering) -> [[a]] -> [a]
902 mergesort' _ [xs] = xs
903 mergesort' cmp xss = mergesort' cmp (merge_pairs cmp xss)
905 merge_pairs :: (a -> a -> Ordering) -> [[a]] -> [[a]]
906 merge_pairs _ [] = []
907 merge_pairs _ [xs] = [xs]
908 merge_pairs cmp (xs:ys:xss) = merge cmp xs ys : merge_pairs cmp xss
910 merge :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
913 merge cmp (x:xs) (y:ys)
915 GT -> y : merge cmp (x:xs) ys
916 _ -> x : merge cmp xs (y:ys)
925 -- qsort is stable and does not concatenate.
926 qsort :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
929 qsort cmp (x:xs) r = qpart cmp x xs [] [] r
931 -- qpart partitions and sorts the sublists
932 qpart :: (a -> a -> Ordering) -> a -> [a] -> [a] -> [a] -> [a] -> [a]
933 qpart cmp x [] rlt rge r =
934 -- rlt and rge are in reverse order and must be sorted with an
935 -- anti-stable sorting
936 rqsort cmp rlt (x:rqsort cmp rge r)
937 qpart cmp x (y:ys) rlt rge r =
939 GT -> qpart cmp x ys (y:rlt) rge r
940 _ -> qpart cmp x ys rlt (y:rge) r
942 -- rqsort is as qsort but anti-stable, i.e. reverses equal elements
943 rqsort :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
946 rqsort cmp (x:xs) r = rqpart cmp x xs [] [] r
948 rqpart :: (a -> a -> Ordering) -> a -> [a] -> [a] -> [a] -> [a] -> [a]
949 rqpart cmp x [] rle rgt r =
950 qsort cmp rle (x:qsort cmp rgt r)
951 rqpart cmp x (y:ys) rle rgt r =
953 GT -> rqpart cmp x ys rle (y:rgt) r
954 _ -> rqpart cmp x ys (y:rle) rgt r
957 #endif /* USE_REPORT_PRELUDE */
959 -- | The 'unfoldr' function is a \`dual\' to 'foldr': while 'foldr'
960 -- reduces a list to a summary value, 'unfoldr' builds a list from
961 -- a seed value. The function takes the element and returns 'Nothing'
962 -- if it is done producing the list or returns 'Just' @(a,b)@, in which
963 -- case, @a@ is a prepended to the list and @b@ is used as the next
964 -- element in a recursive call. For example,
966 -- > iterate f == unfoldr (\x -> Just (x, f x))
968 -- In some cases, 'unfoldr' can undo a 'foldr' operation:
970 -- > unfoldr f' (foldr f z xs) == xs
972 -- if the following holds:
974 -- > f' (f x y) = Just (x,y)
977 -- A simple use of unfoldr:
979 -- > unfoldr (\b -> if b == 0 then Nothing else Just (b, b-1)) 10
980 -- > [10,9,8,7,6,5,4,3,2,1]
982 unfoldr :: (b -> Maybe (a, b)) -> b -> [a]
985 Just (a,new_b) -> a : unfoldr f new_b
988 -- -----------------------------------------------------------------------------
990 -- | A strict version of 'foldl'.
991 foldl' :: (a -> b -> a) -> a -> [b] -> a
992 #ifdef __GLASGOW_HASKELL__
993 foldl' f z0 xs0 = lgo z0 xs0
995 lgo z (x:xs) = let z' = f z x in z' `seq` lgo z' xs
998 foldl' f a (x:xs) = let a' = f a x in a' `seq` foldl' f a' xs
1001 #ifdef __GLASGOW_HASKELL__
1002 -- | 'foldl1' is a variant of 'foldl' that has no starting value argument,
1003 -- and thus must be applied to non-empty lists.
1004 foldl1 :: (a -> a -> a) -> [a] -> a
1005 foldl1 f (x:xs) = foldl f x xs
1006 foldl1 _ [] = errorEmptyList "foldl1"
1007 #endif /* __GLASGOW_HASKELL__ */
1009 -- | A strict version of 'foldl1'
1010 foldl1' :: (a -> a -> a) -> [a] -> a
1011 foldl1' f (x:xs) = foldl' f x xs
1012 foldl1' _ [] = errorEmptyList "foldl1'"
1014 #ifdef __GLASGOW_HASKELL__
1015 -- -----------------------------------------------------------------------------
1016 -- List sum and product
1018 {-# SPECIALISE sum :: [Int] -> Int #-}
1019 {-# SPECIALISE sum :: [Integer] -> Integer #-}
1020 {-# SPECIALISE product :: [Int] -> Int #-}
1021 {-# SPECIALISE product :: [Integer] -> Integer #-}
1022 -- | The 'sum' function computes the sum of a finite list of numbers.
1023 sum :: (Num a) => [a] -> a
1024 -- | The 'product' function computes the product of a finite list of numbers.
1025 product :: (Num a) => [a] -> a
1026 #ifdef USE_REPORT_PRELUDE
1028 product = foldl (*) 1
1033 sum' (x:xs) a = sum' xs (a+x)
1034 product l = prod l 1
1037 prod (x:xs) a = prod xs (a*x)
1040 -- -----------------------------------------------------------------------------
1041 -- Functions on strings
1043 -- | 'lines' breaks a string up into a list of strings at newline
1044 -- characters. The resulting strings do not contain newlines.
1045 lines :: String -> [String]
1047 #ifdef __GLASGOW_HASKELL__
1048 -- Somehow GHC doesn't detect the selector thunks in the below code,
1049 -- so s' keeps a reference to the first line via the pair and we have
1050 -- a space leak (cf. #4334).
1051 -- So we need to make GHC see the selector thunks with a trick.
1052 lines s = cons (case break (== '\n') s of
1053 (l, s') -> (l, case s' of
1055 _:s'' -> lines s''))
1057 cons ~(h, t) = h : t
1059 lines s = let (l, s') = break (== '\n') s
1062 (_:s'') -> lines s''
1065 -- | 'unlines' is an inverse operation to 'lines'.
1066 -- It joins lines, after appending a terminating newline to each.
1067 unlines :: [String] -> String
1068 #ifdef USE_REPORT_PRELUDE
1069 unlines = concatMap (++ "\n")
1071 -- HBC version (stolen)
1072 -- here's a more efficient version
1074 unlines (l:ls) = l ++ '\n' : unlines ls
1077 -- | 'words' breaks a string up into a list of words, which were delimited
1079 words :: String -> [String]
1080 words s = case dropWhile {-partain:Char.-}isSpace s of
1084 break {-partain:Char.-}isSpace s'
1086 -- | 'unwords' is an inverse operation to 'words'.
1087 -- It joins words with separating spaces.
1088 unwords :: [String] -> String
1089 #ifdef USE_REPORT_PRELUDE
1091 unwords ws = foldr1 (\w s -> w ++ ' ':s) ws
1093 -- HBC version (stolen)
1094 -- here's a more efficient version
1097 unwords (w:ws) = w ++ ' ' : unwords ws
1100 #else /* !__GLASGOW_HASKELL__ */
1102 errorEmptyList :: String -> a
1103 errorEmptyList fun =
1104 error ("Prelude." ++ fun ++ ": empty list")
1106 #endif /* !__GLASGOW_HASKELL__ */