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 -- | 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.
402 -- It is a special case of 'intersectBy', which allows the programmer to
403 -- supply their own equality test.
405 intersect :: (Eq a) => [a] -> [a] -> [a]
406 intersect = intersectBy (==)
408 -- | The 'intersectBy' function is the non-overloaded version of 'intersect'.
409 intersectBy :: (a -> a -> Bool) -> [a] -> [a] -> [a]
410 intersectBy eq xs ys = [x | x <- xs, any (eq x) ys]
412 -- | The 'intersperse' function takes an element and a list and
413 -- \`intersperses\' that element between the elements of the list.
416 -- > intersperse ',' "abcde" == "a,b,c,d,e"
418 intersperse :: a -> [a] -> [a]
419 intersperse _ [] = []
420 intersperse _ [x] = [x]
421 intersperse sep (x:xs) = x : sep : intersperse sep xs
423 -- | 'intercalate' @xs xss@ is equivalent to @('concat' ('intersperse' xs xss))@.
424 -- It inserts the list @xs@ in between the lists in @xss@ and concatenates the
426 intercalate :: [a] -> [[a]] -> [a]
427 intercalate xs xss = concat (intersperse xs xss)
429 -- | The 'transpose' function transposes the rows and columns of its argument.
432 -- > transpose [[1,2,3],[4,5,6]] == [[1,4],[2,5],[3,6]]
434 transpose :: [[a]] -> [[a]]
436 transpose ([] : xss) = transpose xss
437 transpose ((x:xs) : xss) = (x : [h | (h:_) <- xss]) : transpose (xs : [ t | (_:t) <- xss])
440 -- | The 'partition' function takes a predicate a list and returns
441 -- the pair of lists of elements which do and do not satisfy the
442 -- predicate, respectively; i.e.,
444 -- > partition p xs == (filter p xs, filter (not . p) xs)
446 partition :: (a -> Bool) -> [a] -> ([a],[a])
447 {-# INLINE partition #-}
448 partition p xs = foldr (select p) ([],[]) xs
450 select :: (a -> Bool) -> a -> ([a], [a]) -> ([a], [a])
451 select p x ~(ts,fs) | p x = (x:ts,fs)
452 | otherwise = (ts, x:fs)
454 -- | The 'mapAccumL' function behaves like a combination of 'map' and
455 -- 'foldl'; it applies a function to each element of a list, passing
456 -- an accumulating parameter from left to right, and returning a final
457 -- value of this accumulator together with the new list.
458 mapAccumL :: (acc -> x -> (acc, y)) -- Function of elt of input list
459 -- and accumulator, returning new
460 -- accumulator and elt of result list
461 -> acc -- Initial accumulator
463 -> (acc, [y]) -- Final accumulator and result list
464 mapAccumL _ s [] = (s, [])
465 mapAccumL f s (x:xs) = (s'',y:ys)
466 where (s', y ) = f s x
467 (s'',ys) = mapAccumL f s' xs
469 -- | The 'mapAccumR' function behaves like a combination of 'map' and
470 -- 'foldr'; it applies a function to each element of a list, passing
471 -- an accumulating parameter from right to left, and returning a final
472 -- value of this accumulator together with the new list.
473 mapAccumR :: (acc -> x -> (acc, y)) -- Function of elt of input list
474 -- and accumulator, returning new
475 -- accumulator and elt of result list
476 -> acc -- Initial accumulator
478 -> (acc, [y]) -- Final accumulator and result list
479 mapAccumR _ s [] = (s, [])
480 mapAccumR f s (x:xs) = (s'', y:ys)
481 where (s'',y ) = f s' x
482 (s', ys) = mapAccumR f s xs
484 -- | The 'insert' function takes an element and a list and inserts the
485 -- element into the list at the last position where it is still less
486 -- than or equal to the next element. In particular, if the list
487 -- is sorted before the call, the result will also be sorted.
488 -- It is a special case of 'insertBy', which allows the programmer to
489 -- supply their own comparison function.
490 insert :: Ord a => a -> [a] -> [a]
491 insert e ls = insertBy (compare) e ls
493 -- | The non-overloaded version of 'insert'.
494 insertBy :: (a -> a -> Ordering) -> a -> [a] -> [a]
495 insertBy _ x [] = [x]
496 insertBy cmp x ys@(y:ys')
498 GT -> y : insertBy cmp x ys'
501 #ifdef __GLASGOW_HASKELL__
503 -- | 'maximum' returns the maximum value from a list,
504 -- which must be non-empty, finite, and of an ordered type.
505 -- It is a special case of 'Data.List.maximumBy', which allows the
506 -- programmer to supply their own comparison function.
507 maximum :: (Ord a) => [a] -> a
508 maximum [] = errorEmptyList "maximum"
509 maximum xs = foldl1 max xs
512 "maximumInt" maximum = (strictMaximum :: [Int] -> Int);
513 "maximumInteger" maximum = (strictMaximum :: [Integer] -> Integer)
516 -- We can't make the overloaded version of maximum strict without
517 -- changing its semantics (max might not be strict), but we can for
518 -- the version specialised to 'Int'.
519 strictMaximum :: (Ord a) => [a] -> a
520 strictMaximum [] = errorEmptyList "maximum"
521 strictMaximum xs = foldl1' max xs
523 -- | 'minimum' returns the minimum value from a list,
524 -- which must be non-empty, finite, and of an ordered type.
525 -- It is a special case of 'Data.List.minimumBy', which allows the
526 -- programmer to supply their own comparison function.
527 minimum :: (Ord a) => [a] -> a
528 minimum [] = errorEmptyList "minimum"
529 minimum xs = foldl1 min xs
532 "minimumInt" minimum = (strictMinimum :: [Int] -> Int);
533 "minimumInteger" minimum = (strictMinimum :: [Integer] -> Integer)
536 strictMinimum :: (Ord a) => [a] -> a
537 strictMinimum [] = errorEmptyList "minimum"
538 strictMinimum xs = foldl1' min xs
540 #endif /* __GLASGOW_HASKELL__ */
542 -- | The 'maximumBy' function takes a comparison function and a list
543 -- and returns the greatest element of the list by the comparison function.
544 -- The list must be finite and non-empty.
545 maximumBy :: (a -> a -> Ordering) -> [a] -> a
546 maximumBy _ [] = error "List.maximumBy: empty list"
547 maximumBy cmp xs = foldl1 maxBy xs
549 maxBy x y = case cmp x y of
553 -- | The 'minimumBy' function takes a comparison function and a list
554 -- and returns the least element of the list by the comparison function.
555 -- The list must be finite and non-empty.
556 minimumBy :: (a -> a -> Ordering) -> [a] -> a
557 minimumBy _ [] = error "List.minimumBy: empty list"
558 minimumBy cmp xs = foldl1 minBy xs
560 minBy x y = case cmp x y of
564 -- | The 'genericLength' function is an overloaded version of 'length'. In
565 -- particular, instead of returning an 'Int', it returns any type which is
566 -- an instance of 'Num'. It is, however, less efficient than 'length'.
567 genericLength :: (Num i) => [b] -> i
569 genericLength (_:l) = 1 + genericLength l
572 "genericLengthInt" genericLength = (strictGenericLength :: [a] -> Int);
573 "genericLengthInteger" genericLength = (strictGenericLength :: [a] -> Integer);
576 strictGenericLength :: (Num i) => [b] -> i
577 strictGenericLength l = gl l 0
580 gl (_:xs) a = let a' = a + 1 in a' `seq` gl xs a'
582 -- | The 'genericTake' function is an overloaded version of 'take', which
583 -- accepts any 'Integral' value as the number of elements to take.
584 genericTake :: (Integral i) => i -> [a] -> [a]
585 genericTake n _ | n <= 0 = []
586 genericTake _ [] = []
587 genericTake n (x:xs) = x : genericTake (n-1) xs
589 -- | The 'genericDrop' function is an overloaded version of 'drop', which
590 -- accepts any 'Integral' value as the number of elements to drop.
591 genericDrop :: (Integral i) => i -> [a] -> [a]
592 genericDrop n xs | n <= 0 = xs
593 genericDrop _ [] = []
594 genericDrop n (_:xs) = genericDrop (n-1) xs
597 -- | The 'genericSplitAt' function is an overloaded version of 'splitAt', which
598 -- accepts any 'Integral' value as the position at which to split.
599 genericSplitAt :: (Integral i) => i -> [b] -> ([b],[b])
600 genericSplitAt n xs | n <= 0 = ([],xs)
601 genericSplitAt _ [] = ([],[])
602 genericSplitAt n (x:xs) = (x:xs',xs'') where
603 (xs',xs'') = genericSplitAt (n-1) xs
605 -- | The 'genericIndex' function is an overloaded version of '!!', which
606 -- accepts any 'Integral' value as the index.
607 genericIndex :: (Integral a) => [b] -> a -> b
608 genericIndex (x:_) 0 = x
609 genericIndex (_:xs) n
610 | n > 0 = genericIndex xs (n-1)
611 | otherwise = error "List.genericIndex: negative argument."
612 genericIndex _ _ = error "List.genericIndex: index too large."
614 -- | The 'genericReplicate' function is an overloaded version of 'replicate',
615 -- which accepts any 'Integral' value as the number of repetitions to make.
616 genericReplicate :: (Integral i) => i -> a -> [a]
617 genericReplicate n x = genericTake n (repeat x)
619 -- | The 'zip4' function takes four lists and returns a list of
620 -- quadruples, analogous to 'zip'.
621 zip4 :: [a] -> [b] -> [c] -> [d] -> [(a,b,c,d)]
622 zip4 = zipWith4 (,,,)
624 -- | The 'zip5' function takes five lists and returns a list of
625 -- five-tuples, analogous to 'zip'.
626 zip5 :: [a] -> [b] -> [c] -> [d] -> [e] -> [(a,b,c,d,e)]
627 zip5 = zipWith5 (,,,,)
629 -- | The 'zip6' function takes six lists and returns a list of six-tuples,
630 -- analogous to 'zip'.
631 zip6 :: [a] -> [b] -> [c] -> [d] -> [e] -> [f] ->
633 zip6 = zipWith6 (,,,,,)
635 -- | The 'zip7' function takes seven lists and returns a list of
636 -- seven-tuples, analogous to 'zip'.
637 zip7 :: [a] -> [b] -> [c] -> [d] -> [e] -> [f] ->
638 [g] -> [(a,b,c,d,e,f,g)]
639 zip7 = zipWith7 (,,,,,,)
641 -- | The 'zipWith4' function takes a function which combines four
642 -- elements, as well as four lists and returns a list of their point-wise
643 -- combination, analogous to 'zipWith'.
644 zipWith4 :: (a->b->c->d->e) -> [a]->[b]->[c]->[d]->[e]
645 zipWith4 z (a:as) (b:bs) (c:cs) (d:ds)
646 = z a b c d : zipWith4 z as bs cs ds
647 zipWith4 _ _ _ _ _ = []
649 -- | The 'zipWith5' function takes a function which combines five
650 -- elements, as well as five lists and returns a list of their point-wise
651 -- combination, analogous to 'zipWith'.
652 zipWith5 :: (a->b->c->d->e->f) ->
653 [a]->[b]->[c]->[d]->[e]->[f]
654 zipWith5 z (a:as) (b:bs) (c:cs) (d:ds) (e:es)
655 = z a b c d e : zipWith5 z as bs cs ds es
656 zipWith5 _ _ _ _ _ _ = []
658 -- | The 'zipWith6' function takes a function which combines six
659 -- elements, as well as six lists and returns a list of their point-wise
660 -- combination, analogous to 'zipWith'.
661 zipWith6 :: (a->b->c->d->e->f->g) ->
662 [a]->[b]->[c]->[d]->[e]->[f]->[g]
663 zipWith6 z (a:as) (b:bs) (c:cs) (d:ds) (e:es) (f:fs)
664 = z a b c d e f : zipWith6 z as bs cs ds es fs
665 zipWith6 _ _ _ _ _ _ _ = []
667 -- | The 'zipWith7' function takes a function which combines seven
668 -- elements, as well as seven lists and returns a list of their point-wise
669 -- combination, analogous to 'zipWith'.
670 zipWith7 :: (a->b->c->d->e->f->g->h) ->
671 [a]->[b]->[c]->[d]->[e]->[f]->[g]->[h]
672 zipWith7 z (a:as) (b:bs) (c:cs) (d:ds) (e:es) (f:fs) (g:gs)
673 = z a b c d e f g : zipWith7 z as bs cs ds es fs gs
674 zipWith7 _ _ _ _ _ _ _ _ = []
676 -- | The 'unzip4' function takes a list of quadruples and returns four
677 -- lists, analogous to 'unzip'.
678 unzip4 :: [(a,b,c,d)] -> ([a],[b],[c],[d])
679 unzip4 = foldr (\(a,b,c,d) ~(as,bs,cs,ds) ->
680 (a:as,b:bs,c:cs,d:ds))
683 -- | The 'unzip5' function takes a list of five-tuples and returns five
684 -- lists, analogous to 'unzip'.
685 unzip5 :: [(a,b,c,d,e)] -> ([a],[b],[c],[d],[e])
686 unzip5 = foldr (\(a,b,c,d,e) ~(as,bs,cs,ds,es) ->
687 (a:as,b:bs,c:cs,d:ds,e:es))
690 -- | The 'unzip6' function takes a list of six-tuples and returns six
691 -- lists, analogous to 'unzip'.
692 unzip6 :: [(a,b,c,d,e,f)] -> ([a],[b],[c],[d],[e],[f])
693 unzip6 = foldr (\(a,b,c,d,e,f) ~(as,bs,cs,ds,es,fs) ->
694 (a:as,b:bs,c:cs,d:ds,e:es,f:fs))
697 -- | The 'unzip7' function takes a list of seven-tuples and returns
698 -- seven lists, analogous to 'unzip'.
699 unzip7 :: [(a,b,c,d,e,f,g)] -> ([a],[b],[c],[d],[e],[f],[g])
700 unzip7 = foldr (\(a,b,c,d,e,f,g) ~(as,bs,cs,ds,es,fs,gs) ->
701 (a:as,b:bs,c:cs,d:ds,e:es,f:fs,g:gs))
702 ([],[],[],[],[],[],[])
705 -- | The 'deleteFirstsBy' function takes a predicate and two lists and
706 -- returns the first list with the first occurrence of each element of
707 -- the second list removed.
708 deleteFirstsBy :: (a -> a -> Bool) -> [a] -> [a] -> [a]
709 deleteFirstsBy eq = foldl (flip (deleteBy eq))
711 -- | The 'group' function takes a list and returns a list of lists such
712 -- that the concatenation of the result is equal to the argument. Moreover,
713 -- each sublist in the result contains only equal elements. For example,
715 -- > group "Mississippi" = ["M","i","ss","i","ss","i","pp","i"]
717 -- It is a special case of 'groupBy', which allows the programmer to supply
718 -- their own equality test.
719 group :: Eq a => [a] -> [[a]]
722 -- | The 'groupBy' function is the non-overloaded version of 'group'.
723 groupBy :: (a -> a -> Bool) -> [a] -> [[a]]
725 groupBy eq (x:xs) = (x:ys) : groupBy eq zs
726 where (ys,zs) = span (eq x) xs
728 -- | The 'inits' function returns all initial segments of the argument,
729 -- shortest first. For example,
731 -- > inits "abc" == ["","a","ab","abc"]
733 inits :: [a] -> [[a]]
735 inits (x:xs) = [[]] ++ map (x:) (inits xs)
737 -- | The 'tails' function returns all final segments of the argument,
738 -- longest first. For example,
740 -- > tails "abc" == ["abc", "bc", "c",""]
742 tails :: [a] -> [[a]]
744 tails xxs@(_:xs) = xxs : tails xs
747 -- | The 'subsequences' function returns the list of all subsequences of the argument.
749 -- > subsequences "abc" == ["","a","b","ab","c","ac","bc","abc"]
750 subsequences :: [a] -> [[a]]
751 subsequences xs = [] : nonEmptySubsequences xs
753 -- | The 'nonEmptySubsequences' function returns the list of all subsequences of the argument,
754 -- except for the empty list.
756 -- > nonEmptySubsequences "abc" == ["a","b","ab","c","ac","bc","abc"]
757 nonEmptySubsequences :: [a] -> [[a]]
758 nonEmptySubsequences [] = []
759 nonEmptySubsequences (x:xs) = [x] : foldr f [] (nonEmptySubsequences xs)
760 where f ys r = ys : (x : ys) : r
763 -- | The 'permutations' function returns the list of all permutations of the argument.
765 -- > permutations "abc" == ["abc","bac","cba","bca","cab","acb"]
766 permutations :: [a] -> [[a]]
767 permutations xs0 = xs0 : perms xs0 []
770 perms (t:ts) is = foldr interleave (perms ts (t:is)) (permutations is)
771 where interleave xs r = let (_,zs) = interleave' id xs r in zs
772 interleave' _ [] r = (ts, r)
773 interleave' f (y:ys) r = let (us,zs) = interleave' (f . (y:)) ys r
774 in (y:us, f (t:y:us) : zs)
777 ------------------------------------------------------------------------------
778 -- Quick Sort algorithm taken from HBC's QSort library.
780 -- | The 'sort' function implements a stable sorting algorithm.
781 -- It is a special case of 'sortBy', which allows the programmer to supply
782 -- their own comparison function.
783 sort :: (Ord a) => [a] -> [a]
785 -- | The 'sortBy' function is the non-overloaded version of 'sort'.
786 sortBy :: (a -> a -> Ordering) -> [a] -> [a]
788 #ifdef USE_REPORT_PRELUDE
789 sort = sortBy compare
790 sortBy cmp = foldr (insertBy cmp) []
793 sortBy cmp l = mergesort cmp l
794 sort l = mergesort compare l
797 Quicksort replaced by mergesort, 14/5/2002.
799 From: Ian Lynagh <igloo@earth.li>
801 I am curious as to why the List.sort implementation in GHC is a
802 quicksort algorithm rather than an algorithm that guarantees n log n
803 time in the worst case? I have attached a mergesort implementation along
804 with a few scripts to time it's performance, the results of which are
805 shown below (* means it didn't finish successfully - in all cases this
806 was due to a stack overflow).
808 If I heap profile the random_list case with only 10000 then I see
809 random_list peaks at using about 2.5M of memory, whereas in the same
810 program using List.sort it uses only 100k.
812 Input style Input length Sort data Sort alg User time
813 stdin 10000 random_list sort 2.82
814 stdin 10000 random_list mergesort 2.96
815 stdin 10000 sorted sort 31.37
816 stdin 10000 sorted mergesort 1.90
817 stdin 10000 revsorted sort 31.21
818 stdin 10000 revsorted mergesort 1.88
819 stdin 100000 random_list sort *
820 stdin 100000 random_list mergesort *
821 stdin 100000 sorted sort *
822 stdin 100000 sorted mergesort *
823 stdin 100000 revsorted sort *
824 stdin 100000 revsorted mergesort *
825 func 10000 random_list sort 0.31
826 func 10000 random_list mergesort 0.91
827 func 10000 sorted sort 19.09
828 func 10000 sorted mergesort 0.15
829 func 10000 revsorted sort 19.17
830 func 10000 revsorted mergesort 0.16
831 func 100000 random_list sort 3.85
832 func 100000 random_list mergesort *
833 func 100000 sorted sort 5831.47
834 func 100000 sorted mergesort 2.23
835 func 100000 revsorted sort 5872.34
836 func 100000 revsorted mergesort 2.24
839 mergesort :: (a -> a -> Ordering) -> [a] -> [a]
840 mergesort cmp = mergesort' cmp . map wrap
842 mergesort' :: (a -> a -> Ordering) -> [[a]] -> [a]
844 mergesort' _ [xs] = xs
845 mergesort' cmp xss = mergesort' cmp (merge_pairs cmp xss)
847 merge_pairs :: (a -> a -> Ordering) -> [[a]] -> [[a]]
848 merge_pairs _ [] = []
849 merge_pairs _ [xs] = [xs]
850 merge_pairs cmp (xs:ys:xss) = merge cmp xs ys : merge_pairs cmp xss
852 merge :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
855 merge cmp (x:xs) (y:ys)
857 GT -> y : merge cmp (x:xs) ys
858 _ -> x : merge cmp xs (y:ys)
866 -- qsort is stable and does not concatenate.
867 qsort :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
870 qsort cmp (x:xs) r = qpart cmp x xs [] [] r
872 -- qpart partitions and sorts the sublists
873 qpart :: (a -> a -> Ordering) -> a -> [a] -> [a] -> [a] -> [a] -> [a]
874 qpart cmp x [] rlt rge r =
875 -- rlt and rge are in reverse order and must be sorted with an
876 -- anti-stable sorting
877 rqsort cmp rlt (x:rqsort cmp rge r)
878 qpart cmp x (y:ys) rlt rge r =
880 GT -> qpart cmp x ys (y:rlt) rge r
881 _ -> qpart cmp x ys rlt (y:rge) r
883 -- rqsort is as qsort but anti-stable, i.e. reverses equal elements
884 rqsort :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
887 rqsort cmp (x:xs) r = rqpart cmp x xs [] [] r
889 rqpart :: (a -> a -> Ordering) -> a -> [a] -> [a] -> [a] -> [a] -> [a]
890 rqpart cmp x [] rle rgt r =
891 qsort cmp rle (x:qsort cmp rgt r)
892 rqpart cmp x (y:ys) rle rgt r =
894 GT -> rqpart cmp x ys rle (y:rgt) r
895 _ -> rqpart cmp x ys (y:rle) rgt r
898 #endif /* USE_REPORT_PRELUDE */
900 -- | The 'unfoldr' function is a \`dual\' to 'foldr': while 'foldr'
901 -- reduces a list to a summary value, 'unfoldr' builds a list from
902 -- a seed value. The function takes the element and returns 'Nothing'
903 -- if it is done producing the list or returns 'Just' @(a,b)@, in which
904 -- case, @a@ is a prepended to the list and @b@ is used as the next
905 -- element in a recursive call. For example,
907 -- > iterate f == unfoldr (\x -> Just (x, f x))
909 -- In some cases, 'unfoldr' can undo a 'foldr' operation:
911 -- > unfoldr f' (foldr f z xs) == xs
913 -- if the following holds:
915 -- > f' (f x y) = Just (x,y)
918 -- A simple use of unfoldr:
920 -- > unfoldr (\b -> if b == 0 then Nothing else Just (b, b-1)) 10
921 -- > [10,9,8,7,6,5,4,3,2,1]
923 unfoldr :: (b -> Maybe (a, b)) -> b -> [a]
926 Just (a,new_b) -> a : unfoldr f new_b
929 -- -----------------------------------------------------------------------------
931 -- | A strict version of 'foldl'.
932 foldl' :: (a -> b -> a) -> a -> [b] -> a
933 #ifdef __GLASGOW_HASKELL__
934 foldl' f z0 xs0 = lgo z0 xs0
936 lgo z (x:xs) = let z' = f z x in z' `seq` lgo z' xs
939 foldl' f a (x:xs) = let a' = f a x in a' `seq` foldl' f a' xs
942 #ifdef __GLASGOW_HASKELL__
943 -- | 'foldl1' is a variant of 'foldl' that has no starting value argument,
944 -- and thus must be applied to non-empty lists.
945 foldl1 :: (a -> a -> a) -> [a] -> a
946 foldl1 f (x:xs) = foldl f x xs
947 foldl1 _ [] = errorEmptyList "foldl1"
948 #endif /* __GLASGOW_HASKELL__ */
950 -- | A strict version of 'foldl1'
951 foldl1' :: (a -> a -> a) -> [a] -> a
952 foldl1' f (x:xs) = foldl' f x xs
953 foldl1' _ [] = errorEmptyList "foldl1'"
955 #ifdef __GLASGOW_HASKELL__
956 -- -----------------------------------------------------------------------------
957 -- List sum and product
959 {-# SPECIALISE sum :: [Int] -> Int #-}
960 {-# SPECIALISE sum :: [Integer] -> Integer #-}
961 {-# SPECIALISE product :: [Int] -> Int #-}
962 {-# SPECIALISE product :: [Integer] -> Integer #-}
963 -- | The 'sum' function computes the sum of a finite list of numbers.
964 sum :: (Num a) => [a] -> a
965 -- | The 'product' function computes the product of a finite list of numbers.
966 product :: (Num a) => [a] -> a
967 #ifdef USE_REPORT_PRELUDE
969 product = foldl (*) 1
974 sum' (x:xs) a = sum' xs (a+x)
978 prod (x:xs) a = prod xs (a*x)
981 -- -----------------------------------------------------------------------------
982 -- Functions on strings
984 -- | 'lines' breaks a string up into a list of strings at newline
985 -- characters. The resulting strings do not contain newlines.
986 lines :: String -> [String]
988 lines s = let (l, s') = break (== '\n') s
993 -- | 'unlines' is an inverse operation to 'lines'.
994 -- It joins lines, after appending a terminating newline to each.
995 unlines :: [String] -> String
996 #ifdef USE_REPORT_PRELUDE
997 unlines = concatMap (++ "\n")
999 -- HBC version (stolen)
1000 -- here's a more efficient version
1002 unlines (l:ls) = l ++ '\n' : unlines ls
1005 -- | 'words' breaks a string up into a list of words, which were delimited
1007 words :: String -> [String]
1008 words s = case dropWhile {-partain:Char.-}isSpace s of
1012 break {-partain:Char.-}isSpace s'
1014 -- | 'unwords' is an inverse operation to 'words'.
1015 -- It joins words with separating spaces.
1016 unwords :: [String] -> String
1017 #ifdef USE_REPORT_PRELUDE
1019 unwords ws = foldr1 (\w s -> w ++ ' ':s) ws
1021 -- HBC version (stolen)
1022 -- here's a more efficient version
1025 unwords (w:ws) = w ++ ' ' : unwords ws
1028 #else /* !__GLASGOW_HASKELL__ */
1030 errorEmptyList :: String -> a
1031 errorEmptyList fun =
1032 error ("Prelude." ++ fun ++ ": empty list")
1034 #endif /* !__GLASGOW_HASKELL__ */