1 {-# OPTIONS_GHC -XNoImplicitPrelude #-}
2 -----------------------------------------------------------------------------
5 -- Copyright : (c) The University of Glasgow 2001
6 -- License : BSD-style (see the file libraries/base/LICENSE)
8 -- Maintainer : libraries@haskell.org
10 -- Portability : portable
12 -- Operations on lists.
14 -----------------------------------------------------------------------------
25 (++) -- :: [a] -> [a] -> [a]
28 , tail -- :: [a] -> [a]
29 , init -- :: [a] -> [a]
30 , null -- :: [a] -> Bool
31 , length -- :: [a] -> Int
33 -- * List transformations
34 , map -- :: (a -> b) -> [a] -> [b]
35 , reverse -- :: [a] -> [a]
37 , intersperse -- :: a -> [a] -> [a]
38 , intercalate -- :: [a] -> [[a]] -> [a]
39 , transpose -- :: [[a]] -> [[a]]
41 , subsequences -- :: [a] -> [[a]]
42 , permutations -- :: [a] -> [[a]]
44 -- * Reducing lists (folds)
46 , foldl -- :: (a -> b -> a) -> a -> [b] -> a
47 , foldl' -- :: (a -> b -> a) -> a -> [b] -> a
48 , foldl1 -- :: (a -> a -> a) -> [a] -> a
49 , foldl1' -- :: (a -> a -> a) -> [a] -> a
50 , foldr -- :: (a -> b -> b) -> b -> [a] -> b
51 , foldr1 -- :: (a -> a -> a) -> [a] -> a
55 , concat -- :: [[a]] -> [a]
56 , concatMap -- :: (a -> [b]) -> [a] -> [b]
57 , and -- :: [Bool] -> Bool
58 , or -- :: [Bool] -> Bool
59 , any -- :: (a -> Bool) -> [a] -> Bool
60 , all -- :: (a -> Bool) -> [a] -> Bool
61 , sum -- :: (Num a) => [a] -> a
62 , product -- :: (Num a) => [a] -> a
63 , maximum -- :: (Ord a) => [a] -> a
64 , minimum -- :: (Ord a) => [a] -> a
69 , scanl -- :: (a -> b -> a) -> a -> [b] -> [a]
70 , scanl1 -- :: (a -> a -> a) -> [a] -> [a]
71 , scanr -- :: (a -> b -> b) -> b -> [a] -> [b]
72 , scanr1 -- :: (a -> a -> a) -> [a] -> [a]
74 -- ** Accumulating maps
75 , mapAccumL -- :: (a -> b -> (a,c)) -> a -> [b] -> (a,[c])
76 , mapAccumR -- :: (a -> b -> (a,c)) -> a -> [b] -> (a,[c])
79 , iterate -- :: (a -> a) -> a -> [a]
80 , repeat -- :: a -> [a]
81 , replicate -- :: Int -> a -> [a]
82 , cycle -- :: [a] -> [a]
85 , unfoldr -- :: (b -> Maybe (a, b)) -> b -> [a]
89 -- ** Extracting sublists
90 , take -- :: Int -> [a] -> [a]
91 , drop -- :: Int -> [a] -> [a]
92 , splitAt -- :: Int -> [a] -> ([a], [a])
94 , takeWhile -- :: (a -> Bool) -> [a] -> [a]
95 , dropWhile -- :: (a -> Bool) -> [a] -> [a]
96 , span -- :: (a -> Bool) -> [a] -> ([a], [a])
97 , break -- :: (a -> Bool) -> [a] -> ([a], [a])
99 , stripPrefix -- :: Eq a => [a] -> [a] -> Maybe [a]
101 , group -- :: Eq a => [a] -> [[a]]
103 , inits -- :: [a] -> [[a]]
104 , tails -- :: [a] -> [[a]]
107 , isPrefixOf -- :: (Eq a) => [a] -> [a] -> Bool
108 , isSuffixOf -- :: (Eq a) => [a] -> [a] -> Bool
109 , isInfixOf -- :: (Eq a) => [a] -> [a] -> Bool
113 -- ** Searching by equality
114 , elem -- :: a -> [a] -> Bool
115 , notElem -- :: a -> [a] -> Bool
116 , lookup -- :: (Eq a) => a -> [(a,b)] -> Maybe b
118 -- ** Searching with a predicate
119 , find -- :: (a -> Bool) -> [a] -> Maybe a
120 , filter -- :: (a -> Bool) -> [a] -> [a]
121 , partition -- :: (a -> Bool) -> [a] -> ([a], [a])
124 -- | These functions treat a list @xs@ as a indexed collection,
125 -- with indices ranging from 0 to @'length' xs - 1@.
127 , (!!) -- :: [a] -> Int -> a
129 , elemIndex -- :: (Eq a) => a -> [a] -> Maybe Int
130 , elemIndices -- :: (Eq a) => a -> [a] -> [Int]
132 , findIndex -- :: (a -> Bool) -> [a] -> Maybe Int
133 , findIndices -- :: (a -> Bool) -> [a] -> [Int]
135 -- * Zipping and unzipping lists
137 , zip -- :: [a] -> [b] -> [(a,b)]
139 , zip4, zip5, zip6, zip7
141 , zipWith -- :: (a -> b -> c) -> [a] -> [b] -> [c]
143 , zipWith4, zipWith5, zipWith6, zipWith7
145 , unzip -- :: [(a,b)] -> ([a],[b])
147 , unzip4, unzip5, unzip6, unzip7
151 -- ** Functions on strings
152 , lines -- :: String -> [String]
153 , words -- :: String -> [String]
154 , unlines -- :: [String] -> String
155 , unwords -- :: [String] -> String
157 -- ** \"Set\" operations
159 , nub -- :: (Eq a) => [a] -> [a]
161 , delete -- :: (Eq a) => a -> [a] -> [a]
162 , (\\) -- :: (Eq a) => [a] -> [a] -> [a]
164 , union -- :: (Eq a) => [a] -> [a] -> [a]
165 , intersect -- :: (Eq a) => [a] -> [a] -> [a]
168 , sort -- :: (Ord a) => [a] -> [a]
169 , insert -- :: (Ord a) => a -> [a] -> [a]
171 -- * Generalized functions
173 -- ** The \"@By@\" operations
174 -- | By convention, overloaded functions have a non-overloaded
175 -- counterpart whose name is suffixed with \`@By@\'.
177 -- It is often convenient to use these functions together with
178 -- 'Data.Function.on', for instance @'sortBy' ('compare'
181 -- *** User-supplied equality (replacing an @Eq@ context)
182 -- | The predicate is assumed to define an equivalence.
183 , nubBy -- :: (a -> a -> Bool) -> [a] -> [a]
184 , deleteBy -- :: (a -> a -> Bool) -> a -> [a] -> [a]
185 , deleteFirstsBy -- :: (a -> a -> Bool) -> [a] -> [a] -> [a]
186 , unionBy -- :: (a -> a -> Bool) -> [a] -> [a] -> [a]
187 , intersectBy -- :: (a -> a -> Bool) -> [a] -> [a] -> [a]
188 , groupBy -- :: (a -> a -> Bool) -> [a] -> [[a]]
190 -- *** User-supplied comparison (replacing an @Ord@ context)
191 -- | The function is assumed to define a total ordering.
192 , sortBy -- :: (a -> a -> Ordering) -> [a] -> [a]
193 , insertBy -- :: (a -> a -> Ordering) -> a -> [a] -> [a]
194 , maximumBy -- :: (a -> a -> Ordering) -> [a] -> a
195 , minimumBy -- :: (a -> a -> Ordering) -> [a] -> a
197 -- ** The \"@generic@\" operations
198 -- | The prefix \`@generic@\' indicates an overloaded function that
199 -- is a generalized version of a "Prelude" function.
201 , genericLength -- :: (Integral a) => [b] -> a
202 , genericTake -- :: (Integral a) => a -> [b] -> [b]
203 , genericDrop -- :: (Integral a) => a -> [b] -> [b]
204 , genericSplitAt -- :: (Integral a) => a -> [b] -> ([b], [b])
205 , genericIndex -- :: (Integral a) => [b] -> a -> b
206 , genericReplicate -- :: (Integral a) => a -> b -> [b]
215 import Data.Char ( isSpace )
217 #ifdef __GLASGOW_HASKELL__
224 infix 5 \\ -- comment to fool cpp
226 -- -----------------------------------------------------------------------------
229 -- | The 'stripPrefix' function drops the given prefix from a list.
230 -- It returns 'Nothing' if the list did not start with the prefix
231 -- given, or 'Just' the list after the prefix, if it does.
233 -- > stripPrefix "foo" "foobar" == Just "bar"
234 -- > stripPrefix "foo" "foo" == Just ""
235 -- > stripPrefix "foo" "barfoo" == Nothing
236 -- > stripPrefix "foo" "barfoobaz" == Nothing
237 stripPrefix :: Eq a => [a] -> [a] -> Maybe [a]
238 stripPrefix [] ys = Just ys
239 stripPrefix (x:xs) (y:ys)
240 | x == y = stripPrefix xs ys
241 stripPrefix _ _ = Nothing
243 -- | The 'elemIndex' function returns the index of the first element
244 -- in the given list which is equal (by '==') to the query element,
245 -- or 'Nothing' if there is no such element.
246 elemIndex :: Eq a => a -> [a] -> Maybe Int
247 elemIndex x = findIndex (x==)
249 -- | The 'elemIndices' function extends 'elemIndex', by returning the
250 -- indices of all elements equal to the query element, in ascending order.
251 elemIndices :: Eq a => a -> [a] -> [Int]
252 elemIndices x = findIndices (x==)
254 -- | The 'find' function takes a predicate and a list and returns the
255 -- first element in the list matching the predicate, or 'Nothing' if
256 -- there is no such element.
257 find :: (a -> Bool) -> [a] -> Maybe a
258 find p = listToMaybe . filter p
260 -- | The 'findIndex' function takes a predicate and a list and returns
261 -- the index of the first element in the list satisfying the predicate,
262 -- or 'Nothing' if there is no such element.
263 findIndex :: (a -> Bool) -> [a] -> Maybe Int
264 findIndex p = listToMaybe . findIndices p
266 -- | The 'findIndices' function extends 'findIndex', by returning the
267 -- indices of all elements satisfying the predicate, in ascending order.
268 findIndices :: (a -> Bool) -> [a] -> [Int]
270 #if defined(USE_REPORT_PRELUDE) || !defined(__GLASGOW_HASKELL__)
271 findIndices p xs = [ i | (x,i) <- zip xs [0..], p x]
273 -- Efficient definition
274 findIndices p ls = loop 0# ls
277 loop n (x:xs) | p x = I# n : loop (n +# 1#) xs
278 | otherwise = loop (n +# 1#) xs
279 #endif /* USE_REPORT_PRELUDE */
281 -- | The 'isPrefixOf' function takes two lists and returns 'True'
282 -- iff the first list is a prefix of the second.
283 isPrefixOf :: (Eq a) => [a] -> [a] -> Bool
284 isPrefixOf [] _ = True
285 isPrefixOf _ [] = False
286 isPrefixOf (x:xs) (y:ys)= x == y && isPrefixOf xs ys
288 -- | The 'isSuffixOf' function takes two lists and returns 'True'
289 -- iff the first list is a suffix of the second.
290 -- Both lists must be finite.
291 isSuffixOf :: (Eq a) => [a] -> [a] -> Bool
292 isSuffixOf x y = reverse x `isPrefixOf` reverse y
294 -- | The 'isInfixOf' function takes two lists and returns 'True'
295 -- iff the first list is contained, wholly and intact,
296 -- anywhere within the second.
300 -- >isInfixOf "Haskell" "I really like Haskell." == True
301 -- >isInfixOf "Ial" "I really like Haskell." == False
302 isInfixOf :: (Eq a) => [a] -> [a] -> Bool
303 isInfixOf needle haystack = any (isPrefixOf needle) (tails haystack)
305 -- | /O(n^2)/. The 'nub' function removes duplicate elements from a list.
306 -- In particular, it keeps only the first occurrence of each element.
307 -- (The name 'nub' means \`essence\'.)
308 -- It is a special case of 'nubBy', which allows the programmer to supply
309 -- their own equality test.
310 nub :: (Eq a) => [a] -> [a]
311 #ifdef USE_REPORT_PRELUDE
315 nub l = nub' l [] -- '
319 | x `elem` ls = nub' xs ls -- '
320 | otherwise = x : nub' xs (x:ls) -- '
323 -- | The 'nubBy' function behaves just like 'nub', except it uses a
324 -- user-supplied equality predicate instead of the overloaded '=='
326 nubBy :: (a -> a -> Bool) -> [a] -> [a]
327 #ifdef USE_REPORT_PRELUDE
329 nubBy eq (x:xs) = x : nubBy eq (filter (\ y -> not (eq x y)) xs)
331 nubBy eq l = nubBy' l []
335 | elem_by eq y xs = nubBy' ys xs
336 | otherwise = y : nubBy' ys (y:xs)
339 -- Note that we keep the call to `eq` with arguments in the
340 -- same order as in the reference implementation
341 -- 'xs' is the list of things we've seen so far,
342 -- 'y' is the potential new element
343 elem_by :: (a -> a -> Bool) -> a -> [a] -> Bool
344 elem_by _ _ [] = False
345 elem_by eq y (x:xs) = y `eq` x || elem_by eq y xs
349 -- | 'delete' @x@ removes the first occurrence of @x@ from its list argument.
352 -- > delete 'a' "banana" == "bnana"
354 -- It is a special case of 'deleteBy', which allows the programmer to
355 -- supply their own equality test.
357 delete :: (Eq a) => a -> [a] -> [a]
358 delete = deleteBy (==)
360 -- | The 'deleteBy' function behaves like 'delete', but takes a
361 -- user-supplied equality predicate.
362 deleteBy :: (a -> a -> Bool) -> a -> [a] -> [a]
364 deleteBy eq x (y:ys) = if x `eq` y then ys else y : deleteBy eq x ys
366 -- | The '\\' function is list difference ((non-associative).
367 -- In the result of @xs@ '\\' @ys@, the first occurrence of each element of
368 -- @ys@ in turn (if any) has been removed from @xs@. Thus
370 -- > (xs ++ ys) \\ xs == ys.
372 -- It is a special case of 'deleteFirstsBy', which allows the programmer
373 -- to supply their own equality test.
375 (\\) :: (Eq a) => [a] -> [a] -> [a]
376 (\\) = foldl (flip delete)
378 -- | The 'union' function returns the list union of the two lists.
381 -- > "dog" `union` "cow" == "dogcw"
383 -- Duplicates, and elements of the first list, are removed from the
384 -- the second list, but if the first list contains duplicates, so will
386 -- It is a special case of 'unionBy', which allows the programmer to supply
387 -- their own equality test.
389 union :: (Eq a) => [a] -> [a] -> [a]
392 -- | The 'unionBy' function is the non-overloaded version of 'union'.
393 unionBy :: (a -> a -> Bool) -> [a] -> [a] -> [a]
394 unionBy eq xs ys = xs ++ foldl (flip (deleteBy eq)) (nubBy eq ys) xs
396 -- | The 'intersect' function takes the list intersection of two lists.
399 -- > [1,2,3,4] `intersect` [2,4,6,8] == [2,4]
401 -- If the first list contains duplicates, so will the result.
403 -- > [1,2,2,3,4] `intersect` [6,4,4,2] == [2,2,4]
405 -- It is a special case of 'intersectBy', which allows the programmer to
406 -- supply their own equality test.
408 intersect :: (Eq a) => [a] -> [a] -> [a]
409 intersect = intersectBy (==)
411 -- | The 'intersectBy' function is the non-overloaded version of 'intersect'.
412 intersectBy :: (a -> a -> Bool) -> [a] -> [a] -> [a]
413 intersectBy _ [] _ = []
414 intersectBy _ _ [] = []
415 intersectBy eq xs ys = [x | x <- xs, any (eq x) ys]
417 -- | The 'intersperse' function takes an element and a list and
418 -- \`intersperses\' that element between the elements of the list.
421 -- > intersperse ',' "abcde" == "a,b,c,d,e"
423 intersperse :: a -> [a] -> [a]
424 intersperse _ [] = []
425 intersperse sep (x:xs) = x : prependToAll sep xs
429 -- We want to make every element in the 'intersperse'd list available
430 -- as soon as possible to avoid space leaks. Experiments suggested that
431 -- a separate top-level helper is more efficient than a local worker.
432 prependToAll :: a -> [a] -> [a]
433 prependToAll _ [] = []
434 prependToAll sep (x:xs) = sep : x : prependToAll sep xs
436 -- | 'intercalate' @xs xss@ is equivalent to @('concat' ('intersperse' xs xss))@.
437 -- It inserts the list @xs@ in between the lists in @xss@ and concatenates the
439 intercalate :: [a] -> [[a]] -> [a]
440 intercalate xs xss = concat (intersperse xs xss)
442 -- | The 'transpose' function transposes the rows and columns of its argument.
445 -- > transpose [[1,2,3],[4,5,6]] == [[1,4],[2,5],[3,6]]
447 transpose :: [[a]] -> [[a]]
449 transpose ([] : xss) = transpose xss
450 transpose ((x:xs) : xss) = (x : [h | (h:_) <- xss]) : transpose (xs : [ t | (_:t) <- xss])
453 -- | The 'partition' function takes a predicate a list and returns
454 -- the pair of lists of elements which do and do not satisfy the
455 -- predicate, respectively; i.e.,
457 -- > partition p xs == (filter p xs, filter (not . p) xs)
459 partition :: (a -> Bool) -> [a] -> ([a],[a])
460 {-# INLINE partition #-}
461 partition p xs = foldr (select p) ([],[]) xs
463 select :: (a -> Bool) -> a -> ([a], [a]) -> ([a], [a])
464 select p x ~(ts,fs) | p x = (x:ts,fs)
465 | otherwise = (ts, x:fs)
467 -- | The 'mapAccumL' function behaves like a combination of 'map' and
468 -- 'foldl'; it applies a function to each element of a list, passing
469 -- an accumulating parameter from left to right, and returning a final
470 -- value of this accumulator together with the new list.
471 mapAccumL :: (acc -> x -> (acc, y)) -- Function of elt of input list
472 -- and accumulator, returning new
473 -- accumulator and elt of result list
474 -> acc -- Initial accumulator
476 -> (acc, [y]) -- Final accumulator and result list
477 mapAccumL _ s [] = (s, [])
478 mapAccumL f s (x:xs) = (s'',y:ys)
479 where (s', y ) = f s x
480 (s'',ys) = mapAccumL f s' xs
482 -- | The 'mapAccumR' function behaves like a combination of 'map' and
483 -- 'foldr'; it applies a function to each element of a list, passing
484 -- an accumulating parameter from right to left, and returning a final
485 -- value of this accumulator together with the new list.
486 mapAccumR :: (acc -> x -> (acc, y)) -- Function of elt of input list
487 -- and accumulator, returning new
488 -- accumulator and elt of result list
489 -> acc -- Initial accumulator
491 -> (acc, [y]) -- Final accumulator and result list
492 mapAccumR _ s [] = (s, [])
493 mapAccumR f s (x:xs) = (s'', y:ys)
494 where (s'',y ) = f s' x
495 (s', ys) = mapAccumR f s xs
497 -- | The 'insert' function takes an element and a list and inserts the
498 -- element into the list at the last position where it is still less
499 -- than or equal to the next element. In particular, if the list
500 -- is sorted before the call, the result will also be sorted.
501 -- It is a special case of 'insertBy', which allows the programmer to
502 -- supply their own comparison function.
503 insert :: Ord a => a -> [a] -> [a]
504 insert e ls = insertBy (compare) e ls
506 -- | The non-overloaded version of 'insert'.
507 insertBy :: (a -> a -> Ordering) -> a -> [a] -> [a]
508 insertBy _ x [] = [x]
509 insertBy cmp x ys@(y:ys')
511 GT -> y : insertBy cmp x ys'
514 #ifdef __GLASGOW_HASKELL__
516 -- | 'maximum' returns the maximum value from a list,
517 -- which must be non-empty, finite, and of an ordered type.
518 -- It is a special case of 'Data.List.maximumBy', which allows the
519 -- programmer to supply their own comparison function.
520 maximum :: (Ord a) => [a] -> a
521 maximum [] = errorEmptyList "maximum"
522 maximum xs = foldl1 max xs
525 "maximumInt" maximum = (strictMaximum :: [Int] -> Int);
526 "maximumInteger" maximum = (strictMaximum :: [Integer] -> Integer)
529 -- We can't make the overloaded version of maximum strict without
530 -- changing its semantics (max might not be strict), but we can for
531 -- the version specialised to 'Int'.
532 strictMaximum :: (Ord a) => [a] -> a
533 strictMaximum [] = errorEmptyList "maximum"
534 strictMaximum xs = foldl1' max xs
536 -- | 'minimum' returns the minimum value from a list,
537 -- which must be non-empty, finite, and of an ordered type.
538 -- It is a special case of 'Data.List.minimumBy', which allows the
539 -- programmer to supply their own comparison function.
540 minimum :: (Ord a) => [a] -> a
541 minimum [] = errorEmptyList "minimum"
542 minimum xs = foldl1 min xs
545 "minimumInt" minimum = (strictMinimum :: [Int] -> Int);
546 "minimumInteger" minimum = (strictMinimum :: [Integer] -> Integer)
549 strictMinimum :: (Ord a) => [a] -> a
550 strictMinimum [] = errorEmptyList "minimum"
551 strictMinimum xs = foldl1' min xs
553 #endif /* __GLASGOW_HASKELL__ */
555 -- | The 'maximumBy' function takes a comparison function and a list
556 -- and returns the greatest element of the list by the comparison function.
557 -- The list must be finite and non-empty.
558 maximumBy :: (a -> a -> Ordering) -> [a] -> a
559 maximumBy _ [] = error "List.maximumBy: empty list"
560 maximumBy cmp xs = foldl1 maxBy xs
562 maxBy x y = case cmp x y of
566 -- | The 'minimumBy' function takes a comparison function and a list
567 -- and returns the least element of the list by the comparison function.
568 -- The list must be finite and non-empty.
569 minimumBy :: (a -> a -> Ordering) -> [a] -> a
570 minimumBy _ [] = error "List.minimumBy: empty list"
571 minimumBy cmp xs = foldl1 minBy xs
573 minBy x y = case cmp x y of
577 -- | The 'genericLength' function is an overloaded version of 'length'. In
578 -- particular, instead of returning an 'Int', it returns any type which is
579 -- an instance of 'Num'. It is, however, less efficient than 'length'.
580 genericLength :: (Num i) => [b] -> i
582 genericLength (_:l) = 1 + genericLength l
585 "genericLengthInt" genericLength = (strictGenericLength :: [a] -> Int);
586 "genericLengthInteger" genericLength = (strictGenericLength :: [a] -> Integer);
589 strictGenericLength :: (Num i) => [b] -> i
590 strictGenericLength l = gl l 0
593 gl (_:xs) a = let a' = a + 1 in a' `seq` gl xs a'
595 -- | The 'genericTake' function is an overloaded version of 'take', which
596 -- accepts any 'Integral' value as the number of elements to take.
597 genericTake :: (Integral i) => i -> [a] -> [a]
598 genericTake n _ | n <= 0 = []
599 genericTake _ [] = []
600 genericTake n (x:xs) = x : genericTake (n-1) xs
602 -- | The 'genericDrop' function is an overloaded version of 'drop', which
603 -- accepts any 'Integral' value as the number of elements to drop.
604 genericDrop :: (Integral i) => i -> [a] -> [a]
605 genericDrop n xs | n <= 0 = xs
606 genericDrop _ [] = []
607 genericDrop n (_:xs) = genericDrop (n-1) xs
610 -- | The 'genericSplitAt' function is an overloaded version of 'splitAt', which
611 -- accepts any 'Integral' value as the position at which to split.
612 genericSplitAt :: (Integral i) => i -> [b] -> ([b],[b])
613 genericSplitAt n xs | n <= 0 = ([],xs)
614 genericSplitAt _ [] = ([],[])
615 genericSplitAt n (x:xs) = (x:xs',xs'') where
616 (xs',xs'') = genericSplitAt (n-1) xs
618 -- | The 'genericIndex' function is an overloaded version of '!!', which
619 -- accepts any 'Integral' value as the index.
620 genericIndex :: (Integral a) => [b] -> a -> b
621 genericIndex (x:_) 0 = x
622 genericIndex (_:xs) n
623 | n > 0 = genericIndex xs (n-1)
624 | otherwise = error "List.genericIndex: negative argument."
625 genericIndex _ _ = error "List.genericIndex: index too large."
627 -- | The 'genericReplicate' function is an overloaded version of 'replicate',
628 -- which accepts any 'Integral' value as the number of repetitions to make.
629 genericReplicate :: (Integral i) => i -> a -> [a]
630 genericReplicate n x = genericTake n (repeat x)
632 -- | The 'zip4' function takes four lists and returns a list of
633 -- quadruples, analogous to 'zip'.
634 zip4 :: [a] -> [b] -> [c] -> [d] -> [(a,b,c,d)]
635 zip4 = zipWith4 (,,,)
637 -- | The 'zip5' function takes five lists and returns a list of
638 -- five-tuples, analogous to 'zip'.
639 zip5 :: [a] -> [b] -> [c] -> [d] -> [e] -> [(a,b,c,d,e)]
640 zip5 = zipWith5 (,,,,)
642 -- | The 'zip6' function takes six lists and returns a list of six-tuples,
643 -- analogous to 'zip'.
644 zip6 :: [a] -> [b] -> [c] -> [d] -> [e] -> [f] ->
646 zip6 = zipWith6 (,,,,,)
648 -- | The 'zip7' function takes seven lists and returns a list of
649 -- seven-tuples, analogous to 'zip'.
650 zip7 :: [a] -> [b] -> [c] -> [d] -> [e] -> [f] ->
651 [g] -> [(a,b,c,d,e,f,g)]
652 zip7 = zipWith7 (,,,,,,)
654 -- | The 'zipWith4' function takes a function which combines four
655 -- elements, as well as four lists and returns a list of their point-wise
656 -- combination, analogous to 'zipWith'.
657 zipWith4 :: (a->b->c->d->e) -> [a]->[b]->[c]->[d]->[e]
658 zipWith4 z (a:as) (b:bs) (c:cs) (d:ds)
659 = z a b c d : zipWith4 z as bs cs ds
660 zipWith4 _ _ _ _ _ = []
662 -- | The 'zipWith5' function takes a function which combines five
663 -- elements, as well as five lists and returns a list of their point-wise
664 -- combination, analogous to 'zipWith'.
665 zipWith5 :: (a->b->c->d->e->f) ->
666 [a]->[b]->[c]->[d]->[e]->[f]
667 zipWith5 z (a:as) (b:bs) (c:cs) (d:ds) (e:es)
668 = z a b c d e : zipWith5 z as bs cs ds es
669 zipWith5 _ _ _ _ _ _ = []
671 -- | The 'zipWith6' function takes a function which combines six
672 -- elements, as well as six lists and returns a list of their point-wise
673 -- combination, analogous to 'zipWith'.
674 zipWith6 :: (a->b->c->d->e->f->g) ->
675 [a]->[b]->[c]->[d]->[e]->[f]->[g]
676 zipWith6 z (a:as) (b:bs) (c:cs) (d:ds) (e:es) (f:fs)
677 = z a b c d e f : zipWith6 z as bs cs ds es fs
678 zipWith6 _ _ _ _ _ _ _ = []
680 -- | The 'zipWith7' function takes a function which combines seven
681 -- elements, as well as seven lists and returns a list of their point-wise
682 -- combination, analogous to 'zipWith'.
683 zipWith7 :: (a->b->c->d->e->f->g->h) ->
684 [a]->[b]->[c]->[d]->[e]->[f]->[g]->[h]
685 zipWith7 z (a:as) (b:bs) (c:cs) (d:ds) (e:es) (f:fs) (g:gs)
686 = z a b c d e f g : zipWith7 z as bs cs ds es fs gs
687 zipWith7 _ _ _ _ _ _ _ _ = []
689 -- | The 'unzip4' function takes a list of quadruples and returns four
690 -- lists, analogous to 'unzip'.
691 unzip4 :: [(a,b,c,d)] -> ([a],[b],[c],[d])
692 unzip4 = foldr (\(a,b,c,d) ~(as,bs,cs,ds) ->
693 (a:as,b:bs,c:cs,d:ds))
696 -- | The 'unzip5' function takes a list of five-tuples and returns five
697 -- lists, analogous to 'unzip'.
698 unzip5 :: [(a,b,c,d,e)] -> ([a],[b],[c],[d],[e])
699 unzip5 = foldr (\(a,b,c,d,e) ~(as,bs,cs,ds,es) ->
700 (a:as,b:bs,c:cs,d:ds,e:es))
703 -- | The 'unzip6' function takes a list of six-tuples and returns six
704 -- lists, analogous to 'unzip'.
705 unzip6 :: [(a,b,c,d,e,f)] -> ([a],[b],[c],[d],[e],[f])
706 unzip6 = foldr (\(a,b,c,d,e,f) ~(as,bs,cs,ds,es,fs) ->
707 (a:as,b:bs,c:cs,d:ds,e:es,f:fs))
710 -- | The 'unzip7' function takes a list of seven-tuples and returns
711 -- seven lists, analogous to 'unzip'.
712 unzip7 :: [(a,b,c,d,e,f,g)] -> ([a],[b],[c],[d],[e],[f],[g])
713 unzip7 = foldr (\(a,b,c,d,e,f,g) ~(as,bs,cs,ds,es,fs,gs) ->
714 (a:as,b:bs,c:cs,d:ds,e:es,f:fs,g:gs))
715 ([],[],[],[],[],[],[])
718 -- | The 'deleteFirstsBy' function takes a predicate and two lists and
719 -- returns the first list with the first occurrence of each element of
720 -- the second list removed.
721 deleteFirstsBy :: (a -> a -> Bool) -> [a] -> [a] -> [a]
722 deleteFirstsBy eq = foldl (flip (deleteBy eq))
724 -- | The 'group' function takes a list and returns a list of lists such
725 -- that the concatenation of the result is equal to the argument. Moreover,
726 -- each sublist in the result contains only equal elements. For example,
728 -- > group "Mississippi" = ["M","i","ss","i","ss","i","pp","i"]
730 -- It is a special case of 'groupBy', which allows the programmer to supply
731 -- their own equality test.
732 group :: Eq a => [a] -> [[a]]
735 -- | The 'groupBy' function is the non-overloaded version of 'group'.
736 groupBy :: (a -> a -> Bool) -> [a] -> [[a]]
738 groupBy eq (x:xs) = (x:ys) : groupBy eq zs
739 where (ys,zs) = span (eq x) xs
741 -- | The 'inits' function returns all initial segments of the argument,
742 -- shortest first. For example,
744 -- > inits "abc" == ["","a","ab","abc"]
746 inits :: [a] -> [[a]]
748 inits (x:xs) = [[]] ++ map (x:) (inits xs)
750 -- | The 'tails' function returns all final segments of the argument,
751 -- longest first. For example,
753 -- > tails "abc" == ["abc", "bc", "c",""]
755 tails :: [a] -> [[a]]
757 tails xxs@(_:xs) = xxs : tails xs
760 -- | The 'subsequences' function returns the list of all subsequences of the argument.
762 -- > subsequences "abc" == ["","a","b","ab","c","ac","bc","abc"]
763 subsequences :: [a] -> [[a]]
764 subsequences xs = [] : nonEmptySubsequences xs
766 -- | The 'nonEmptySubsequences' function returns the list of all subsequences of the argument,
767 -- except for the empty list.
769 -- > nonEmptySubsequences "abc" == ["a","b","ab","c","ac","bc","abc"]
770 nonEmptySubsequences :: [a] -> [[a]]
771 nonEmptySubsequences [] = []
772 nonEmptySubsequences (x:xs) = [x] : foldr f [] (nonEmptySubsequences xs)
773 where f ys r = ys : (x : ys) : r
776 -- | The 'permutations' function returns the list of all permutations of the argument.
778 -- > permutations "abc" == ["abc","bac","cba","bca","cab","acb"]
779 permutations :: [a] -> [[a]]
780 permutations xs0 = xs0 : perms xs0 []
783 perms (t:ts) is = foldr interleave (perms ts (t:is)) (permutations is)
784 where interleave xs r = let (_,zs) = interleave' id xs r in zs
785 interleave' _ [] r = (ts, r)
786 interleave' f (y:ys) r = let (us,zs) = interleave' (f . (y:)) ys r
787 in (y:us, f (t:y:us) : zs)
790 ------------------------------------------------------------------------------
791 -- Quick Sort algorithm taken from HBC's QSort library.
793 -- | The 'sort' function implements a stable sorting algorithm.
794 -- It is a special case of 'sortBy', which allows the programmer to supply
795 -- their own comparison function.
796 sort :: (Ord a) => [a] -> [a]
798 -- | The 'sortBy' function is the non-overloaded version of 'sort'.
799 sortBy :: (a -> a -> Ordering) -> [a] -> [a]
801 #ifdef USE_REPORT_PRELUDE
802 sort = sortBy compare
803 sortBy cmp = foldr (insertBy cmp) []
807 GHC's mergesort replaced by a better implementation, 24/12/2009.
808 This code originally contributed to the nhc12 compiler by Thomas Nordin
809 in 2002. Rumoured to have been based on code by Lennart Augustsson, e.g.
810 http://www.mail-archive.com/haskell@haskell.org/msg01822.html
811 and possibly to bear similarities to a 1982 paper by Richard O'Keefe:
812 "A smooth applicative merge sort".
814 Benchmarks show it to be often 2x the speed of the previous implementation.
815 Fixes ticket http://hackage.haskell.org/trac/ghc/ticket/2143
818 sort = sortBy compare
819 sortBy cmp = mergeAll . sequences
822 | a `cmp` b == GT = descending b [a] xs
823 | otherwise = ascending b (a:) xs
826 descending a as (b:bs)
827 | a `cmp` b == GT = descending b (a:as) bs
828 descending a as bs = (a:as): sequences bs
830 ascending a as (b:bs)
831 | a `cmp` b /= GT = ascending b (\ys -> as (a:ys)) bs
832 ascending a as bs = as [a]: sequences bs
835 mergeAll xs = mergeAll (mergePairs xs)
837 mergePairs (a:b:xs) = merge a b: mergePairs xs
840 merge as@(a:as') bs@(b:bs')
841 | a `cmp` b == GT = b:merge as bs'
842 | otherwise = a:merge as' bs
847 sortBy cmp l = mergesort cmp l
848 sort l = mergesort compare l
850 Quicksort replaced by mergesort, 14/5/2002.
852 From: Ian Lynagh <igloo@earth.li>
854 I am curious as to why the List.sort implementation in GHC is a
855 quicksort algorithm rather than an algorithm that guarantees n log n
856 time in the worst case? I have attached a mergesort implementation along
857 with a few scripts to time it's performance, the results of which are
858 shown below (* means it didn't finish successfully - in all cases this
859 was due to a stack overflow).
861 If I heap profile the random_list case with only 10000 then I see
862 random_list peaks at using about 2.5M of memory, whereas in the same
863 program using List.sort it uses only 100k.
865 Input style Input length Sort data Sort alg User time
866 stdin 10000 random_list sort 2.82
867 stdin 10000 random_list mergesort 2.96
868 stdin 10000 sorted sort 31.37
869 stdin 10000 sorted mergesort 1.90
870 stdin 10000 revsorted sort 31.21
871 stdin 10000 revsorted mergesort 1.88
872 stdin 100000 random_list sort *
873 stdin 100000 random_list mergesort *
874 stdin 100000 sorted sort *
875 stdin 100000 sorted mergesort *
876 stdin 100000 revsorted sort *
877 stdin 100000 revsorted mergesort *
878 func 10000 random_list sort 0.31
879 func 10000 random_list mergesort 0.91
880 func 10000 sorted sort 19.09
881 func 10000 sorted mergesort 0.15
882 func 10000 revsorted sort 19.17
883 func 10000 revsorted mergesort 0.16
884 func 100000 random_list sort 3.85
885 func 100000 random_list mergesort *
886 func 100000 sorted sort 5831.47
887 func 100000 sorted mergesort 2.23
888 func 100000 revsorted sort 5872.34
889 func 100000 revsorted mergesort 2.24
891 mergesort :: (a -> a -> Ordering) -> [a] -> [a]
892 mergesort cmp = mergesort' cmp . map wrap
894 mergesort' :: (a -> a -> Ordering) -> [[a]] -> [a]
896 mergesort' _ [xs] = xs
897 mergesort' cmp xss = mergesort' cmp (merge_pairs cmp xss)
899 merge_pairs :: (a -> a -> Ordering) -> [[a]] -> [[a]]
900 merge_pairs _ [] = []
901 merge_pairs _ [xs] = [xs]
902 merge_pairs cmp (xs:ys:xss) = merge cmp xs ys : merge_pairs cmp xss
904 merge :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
907 merge cmp (x:xs) (y:ys)
909 GT -> y : merge cmp (x:xs) ys
910 _ -> x : merge cmp xs (y:ys)
919 -- qsort is stable and does not concatenate.
920 qsort :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
923 qsort cmp (x:xs) r = qpart cmp x xs [] [] r
925 -- qpart partitions and sorts the sublists
926 qpart :: (a -> a -> Ordering) -> a -> [a] -> [a] -> [a] -> [a] -> [a]
927 qpart cmp x [] rlt rge r =
928 -- rlt and rge are in reverse order and must be sorted with an
929 -- anti-stable sorting
930 rqsort cmp rlt (x:rqsort cmp rge r)
931 qpart cmp x (y:ys) rlt rge r =
933 GT -> qpart cmp x ys (y:rlt) rge r
934 _ -> qpart cmp x ys rlt (y:rge) r
936 -- rqsort is as qsort but anti-stable, i.e. reverses equal elements
937 rqsort :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
940 rqsort cmp (x:xs) r = rqpart cmp x xs [] [] r
942 rqpart :: (a -> a -> Ordering) -> a -> [a] -> [a] -> [a] -> [a] -> [a]
943 rqpart cmp x [] rle rgt r =
944 qsort cmp rle (x:qsort cmp rgt r)
945 rqpart cmp x (y:ys) rle rgt r =
947 GT -> rqpart cmp x ys rle (y:rgt) r
948 _ -> rqpart cmp x ys (y:rle) rgt r
951 #endif /* USE_REPORT_PRELUDE */
953 -- | The 'unfoldr' function is a \`dual\' to 'foldr': while 'foldr'
954 -- reduces a list to a summary value, 'unfoldr' builds a list from
955 -- a seed value. The function takes the element and returns 'Nothing'
956 -- if it is done producing the list or returns 'Just' @(a,b)@, in which
957 -- case, @a@ is a prepended to the list and @b@ is used as the next
958 -- element in a recursive call. For example,
960 -- > iterate f == unfoldr (\x -> Just (x, f x))
962 -- In some cases, 'unfoldr' can undo a 'foldr' operation:
964 -- > unfoldr f' (foldr f z xs) == xs
966 -- if the following holds:
968 -- > f' (f x y) = Just (x,y)
971 -- A simple use of unfoldr:
973 -- > unfoldr (\b -> if b == 0 then Nothing else Just (b, b-1)) 10
974 -- > [10,9,8,7,6,5,4,3,2,1]
976 unfoldr :: (b -> Maybe (a, b)) -> b -> [a]
979 Just (a,new_b) -> a : unfoldr f new_b
982 -- -----------------------------------------------------------------------------
984 -- | A strict version of 'foldl'.
985 foldl' :: (a -> b -> a) -> a -> [b] -> a
986 #ifdef __GLASGOW_HASKELL__
987 foldl' f z0 xs0 = lgo z0 xs0
989 lgo z (x:xs) = let z' = f z x in z' `seq` lgo z' xs
992 foldl' f a (x:xs) = let a' = f a x in a' `seq` foldl' f a' xs
995 #ifdef __GLASGOW_HASKELL__
996 -- | 'foldl1' is a variant of 'foldl' that has no starting value argument,
997 -- and thus must be applied to non-empty lists.
998 foldl1 :: (a -> a -> a) -> [a] -> a
999 foldl1 f (x:xs) = foldl f x xs
1000 foldl1 _ [] = errorEmptyList "foldl1"
1001 #endif /* __GLASGOW_HASKELL__ */
1003 -- | A strict version of 'foldl1'
1004 foldl1' :: (a -> a -> a) -> [a] -> a
1005 foldl1' f (x:xs) = foldl' f x xs
1006 foldl1' _ [] = errorEmptyList "foldl1'"
1008 #ifdef __GLASGOW_HASKELL__
1009 -- -----------------------------------------------------------------------------
1010 -- List sum and product
1012 {-# SPECIALISE sum :: [Int] -> Int #-}
1013 {-# SPECIALISE sum :: [Integer] -> Integer #-}
1014 {-# SPECIALISE product :: [Int] -> Int #-}
1015 {-# SPECIALISE product :: [Integer] -> Integer #-}
1016 -- | The 'sum' function computes the sum of a finite list of numbers.
1017 sum :: (Num a) => [a] -> a
1018 -- | The 'product' function computes the product of a finite list of numbers.
1019 product :: (Num a) => [a] -> a
1020 #ifdef USE_REPORT_PRELUDE
1022 product = foldl (*) 1
1027 sum' (x:xs) a = sum' xs (a+x)
1028 product l = prod l 1
1031 prod (x:xs) a = prod xs (a*x)
1034 -- -----------------------------------------------------------------------------
1035 -- Functions on strings
1037 -- | 'lines' breaks a string up into a list of strings at newline
1038 -- characters. The resulting strings do not contain newlines.
1039 lines :: String -> [String]
1041 lines s = let (l, s') = break (== '\n') s
1044 (_:s'') -> lines s''
1046 -- | 'unlines' is an inverse operation to 'lines'.
1047 -- It joins lines, after appending a terminating newline to each.
1048 unlines :: [String] -> String
1049 #ifdef USE_REPORT_PRELUDE
1050 unlines = concatMap (++ "\n")
1052 -- HBC version (stolen)
1053 -- here's a more efficient version
1055 unlines (l:ls) = l ++ '\n' : unlines ls
1058 -- | 'words' breaks a string up into a list of words, which were delimited
1060 words :: String -> [String]
1061 words s = case dropWhile {-partain:Char.-}isSpace s of
1065 break {-partain:Char.-}isSpace s'
1067 -- | 'unwords' is an inverse operation to 'words'.
1068 -- It joins words with separating spaces.
1069 unwords :: [String] -> String
1070 #ifdef USE_REPORT_PRELUDE
1072 unwords ws = foldr1 (\w s -> w ++ ' ':s) ws
1074 -- HBC version (stolen)
1075 -- here's a more efficient version
1078 unwords (w:ws) = w ++ ' ' : unwords ws
1081 #else /* !__GLASGOW_HASKELL__ */
1083 errorEmptyList :: String -> a
1084 errorEmptyList fun =
1085 error ("Prelude." ++ fun ++ ": empty list")
1087 #endif /* !__GLASGOW_HASKELL__ */