1 {-# OPTIONS_GHC -fno-implicit-prelude #-}
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 -- * Reducing lists (folds)
43 , foldl -- :: (a -> b -> a) -> a -> [b] -> a
44 , foldl' -- :: (a -> b -> a) -> a -> [b] -> a
45 , foldl1 -- :: (a -> a -> a) -> [a] -> a
46 , foldl1' -- :: (a -> a -> a) -> [a] -> a
47 , foldr -- :: (a -> b -> b) -> b -> [a] -> b
48 , foldr1 -- :: (a -> a -> a) -> [a] -> a
52 , concat -- :: [[a]] -> [a]
53 , concatMap -- :: (a -> [b]) -> [a] -> [b]
54 , and -- :: [Bool] -> Bool
55 , or -- :: [Bool] -> Bool
56 , any -- :: (a -> Bool) -> [a] -> Bool
57 , all -- :: (a -> Bool) -> [a] -> Bool
58 , sum -- :: (Num a) => [a] -> a
59 , product -- :: (Num a) => [a] -> a
60 , maximum -- :: (Ord a) => [a] -> a
61 , minimum -- :: (Ord a) => [a] -> a
66 , scanl -- :: (a -> b -> a) -> a -> [b] -> [a]
67 , scanl1 -- :: (a -> a -> a) -> [a] -> [a]
68 , scanr -- :: (a -> b -> b) -> b -> [a] -> [b]
69 , scanr1 -- :: (a -> a -> a) -> [a] -> [a]
71 -- ** Accumulating maps
72 , mapAccumL -- :: (a -> b -> (a,c)) -> a -> [b] -> (a,[c])
73 , mapAccumR -- :: (a -> b -> (a,c)) -> a -> [b] -> (a,[c])
76 , iterate -- :: (a -> a) -> a -> [a]
77 , repeat -- :: a -> [a]
78 , replicate -- :: Int -> a -> [a]
79 , cycle -- :: [a] -> [a]
82 , unfoldr -- :: (b -> Maybe (a, b)) -> b -> [a]
86 -- ** Extracting sublists
87 , take -- :: Int -> [a] -> [a]
88 , drop -- :: Int -> [a] -> [a]
89 , splitAt -- :: Int -> [a] -> ([a], [a])
91 , takeWhile -- :: (a -> Bool) -> [a] -> [a]
92 , dropWhile -- :: (a -> Bool) -> [a] -> [a]
93 , span -- :: (a -> Bool) -> [a] -> ([a], [a])
94 , break -- :: (a -> Bool) -> [a] -> ([a], [a])
96 , split -- :: Eq a => a -> [a] -> [[a]]
98 , group -- :: Eq a => [a] -> [[a]]
100 , inits -- :: [a] -> [[a]]
101 , tails -- :: [a] -> [[a]]
104 , isPrefixOf -- :: (Eq a) => [a] -> [a] -> Bool
105 , isSuffixOf -- :: (Eq a) => [a] -> [a] -> Bool
106 , isInfixOf -- :: (Eq a) => [a] -> [a] -> Bool
110 -- ** Searching by equality
111 , elem -- :: a -> [a] -> Bool
112 , notElem -- :: a -> [a] -> Bool
113 , lookup -- :: (Eq a) => a -> [(a,b)] -> Maybe b
115 -- ** Searching with a predicate
116 , find -- :: (a -> Bool) -> [a] -> Maybe a
117 , filter -- :: (a -> Bool) -> [a] -> [a]
118 , partition -- :: (a -> Bool) -> [a] -> ([a], [a])
121 -- | These functions treat a list @xs@ as a indexed collection,
122 -- with indices ranging from 0 to @'length' xs - 1@.
124 , (!!) -- :: [a] -> Int -> a
126 , elemIndex -- :: (Eq a) => a -> [a] -> Maybe Int
127 , elemIndices -- :: (Eq a) => a -> [a] -> [Int]
129 , findIndex -- :: (a -> Bool) -> [a] -> Maybe Int
130 , findIndices -- :: (a -> Bool) -> [a] -> [Int]
132 -- * Zipping and unzipping lists
134 , zip -- :: [a] -> [b] -> [(a,b)]
136 , zip4, zip5, zip6, zip7
138 , zipWith -- :: (a -> b -> c) -> [a] -> [b] -> [c]
140 , zipWith4, zipWith5, zipWith6, zipWith7
142 , unzip -- :: [(a,b)] -> ([a],[b])
144 , unzip4, unzip5, unzip6, unzip7
148 -- ** Functions on strings
149 , lines -- :: String -> [String]
150 , words -- :: String -> [String]
151 , unlines -- :: [String] -> String
152 , unwords -- :: [String] -> String
154 -- ** \"Set\" operations
156 , nub -- :: (Eq a) => [a] -> [a]
158 , delete -- :: (Eq a) => a -> [a] -> [a]
159 , (\\) -- :: (Eq a) => [a] -> [a] -> [a]
161 , union -- :: (Eq a) => [a] -> [a] -> [a]
162 , intersect -- :: (Eq a) => [a] -> [a] -> [a]
165 , sort -- :: (Ord a) => [a] -> [a]
166 , insert -- :: (Ord a) => a -> [a] -> [a]
168 -- * Generalized functions
170 -- ** The \"@By@\" operations
171 -- | By convention, overloaded functions have a non-overloaded
172 -- counterpart whose name is suffixed with \`@By@\'.
174 -- *** User-supplied equality (replacing an @Eq@ context)
175 -- | The predicate is assumed to define an equivalence.
176 , nubBy -- :: (a -> a -> Bool) -> [a] -> [a]
177 , deleteBy -- :: (a -> a -> Bool) -> a -> [a] -> [a]
178 , deleteFirstsBy -- :: (a -> a -> Bool) -> [a] -> [a] -> [a]
179 , unionBy -- :: (a -> a -> Bool) -> [a] -> [a] -> [a]
180 , intersectBy -- :: (a -> a -> Bool) -> [a] -> [a] -> [a]
181 , groupBy -- :: (a -> a -> Bool) -> [a] -> [[a]]
183 -- *** User-supplied comparison (replacing an @Ord@ context)
184 -- | The function is assumed to define a total ordering.
185 , sortBy -- :: (a -> a -> Ordering) -> [a] -> [a]
186 , insertBy -- :: (a -> a -> Ordering) -> a -> [a] -> [a]
187 , maximumBy -- :: (a -> a -> Ordering) -> [a] -> a
188 , minimumBy -- :: (a -> a -> Ordering) -> [a] -> a
190 -- ** The \"@generic@\" operations
191 -- | The prefix \`@generic@\' indicates an overloaded function that
192 -- is a generalized version of a "Prelude" function.
194 , genericLength -- :: (Integral a) => [b] -> a
195 , genericTake -- :: (Integral a) => a -> [b] -> [b]
196 , genericDrop -- :: (Integral a) => a -> [b] -> [b]
197 , genericSplitAt -- :: (Integral a) => a -> [b] -> ([b], [b])
198 , genericIndex -- :: (Integral a) => [b] -> a -> b
199 , genericReplicate -- :: (Integral a) => a -> b -> [b]
204 import Prelude hiding (Maybe(..))
208 import Data.Char ( isSpace )
210 #ifdef __GLASGOW_HASKELL__
217 infix 5 \\ -- comment to fool cpp
219 -- -----------------------------------------------------------------------------
222 -- | The 'elemIndex' function returns the index of the first element
223 -- in the given list which is equal (by '==') to the query element,
224 -- or 'Nothing' if there is no such element.
225 elemIndex :: Eq a => a -> [a] -> Maybe Int
226 elemIndex x = findIndex (x==)
228 -- | The 'elemIndices' function extends 'elemIndex', by returning the
229 -- indices of all elements equal to the query element, in ascending order.
230 elemIndices :: Eq a => a -> [a] -> [Int]
231 elemIndices x = findIndices (x==)
233 -- | The 'find' function takes a predicate and a list and returns the
234 -- first element in the list matching the predicate, or 'Nothing' if
235 -- there is no such element.
236 find :: (a -> Bool) -> [a] -> Maybe a
237 find p = listToMaybe . filter p
239 -- | The 'findIndex' function takes a predicate and a list and returns
240 -- the index of the first element in the list satisfying the predicate,
241 -- or 'Nothing' if there is no such element.
242 findIndex :: (a -> Bool) -> [a] -> Maybe Int
243 findIndex p = listToMaybe . findIndices p
245 -- | The 'findIndices' function extends 'findIndex', by returning the
246 -- indices of all elements satisfying the predicate, in ascending order.
247 findIndices :: (a -> Bool) -> [a] -> [Int]
249 #if defined(USE_REPORT_PRELUDE) || !defined(__GLASGOW_HASKELL__)
250 findIndices p xs = [ i | (x,i) <- zip xs [0..], p x]
252 -- Efficient definition
253 findIndices p ls = loop 0# ls
256 loop n (x:xs) | p x = I# n : loop (n +# 1#) xs
257 | otherwise = loop (n +# 1#) xs
258 #endif /* USE_REPORT_PRELUDE */
260 -- | The 'isPrefixOf' function takes two lists and returns 'True'
261 -- iff the first list is a prefix of the second.
262 isPrefixOf :: (Eq a) => [a] -> [a] -> Bool
263 isPrefixOf [] _ = True
264 isPrefixOf _ [] = False
265 isPrefixOf (x:xs) (y:ys)= x == y && isPrefixOf xs ys
267 -- | The 'isSuffixOf' function takes two lists and returns 'True'
268 -- iff the first list is a suffix of the second.
269 -- Both lists must be finite.
270 isSuffixOf :: (Eq a) => [a] -> [a] -> Bool
271 isSuffixOf x y = reverse x `isPrefixOf` reverse y
273 -- | The 'isInfixOf' function takes two lists and returns 'True'
274 -- iff the first list is contained, wholly and intact,
275 -- anywhere within the second.
279 -- >isInfixOf "Haskell" "I really like Haskell." -> True
280 -- >isInfixOf "Ial" "I really like Haskell." -> False
281 isInfixOf :: (Eq a) => [a] -> [a] -> Bool
282 isInfixOf needle haystack = any (isPrefixOf needle) (tails haystack)
284 -- | The 'nub' function removes duplicate elements from a list.
285 -- In particular, it keeps only the first occurrence of each element.
286 -- (The name 'nub' means \`essence\'.)
287 -- It is a special case of 'nubBy', which allows the programmer to supply
288 -- their own equality test.
289 nub :: (Eq a) => [a] -> [a]
290 #ifdef USE_REPORT_PRELUDE
294 nub l = nub' l [] -- '
298 | x `elem` ls = nub' xs ls -- '
299 | otherwise = x : nub' xs (x:ls) -- '
302 -- | The 'nubBy' function behaves just like 'nub', except it uses a
303 -- user-supplied equality predicate instead of the overloaded '=='
305 nubBy :: (a -> a -> Bool) -> [a] -> [a]
306 #ifdef USE_REPORT_PRELUDE
308 nubBy eq (x:xs) = x : nubBy eq (filter (\ y -> not (eq x y)) xs)
310 nubBy eq l = nubBy' l []
314 | elem_by eq y xs = nubBy' ys xs
315 | otherwise = y : nubBy' ys (y:xs)
318 -- Note that we keep the call to `eq` with arguments in the
319 -- same order as in the reference implementation
320 -- 'xs' is the list of things we've seen so far,
321 -- 'y' is the potential new element
322 elem_by :: (a -> a -> Bool) -> a -> [a] -> Bool
323 elem_by _ _ [] = False
324 elem_by eq y (x:xs) = x `eq` y || elem_by eq y xs
328 -- | 'delete' @x@ removes the first occurrence of @x@ from its list argument.
331 -- > delete 'a' "banana" == "bnana"
333 -- It is a special case of 'deleteBy', which allows the programmer to
334 -- supply their own equality test.
336 delete :: (Eq a) => a -> [a] -> [a]
337 delete = deleteBy (==)
339 -- | The 'deleteBy' function behaves like 'delete', but takes a
340 -- user-supplied equality predicate.
341 deleteBy :: (a -> a -> Bool) -> a -> [a] -> [a]
343 deleteBy eq x (y:ys) = if x `eq` y then ys else y : deleteBy eq x ys
345 -- | The '\\' function is list difference ((non-associative).
346 -- In the result of @xs@ '\\' @ys@, the first occurrence of each element of
347 -- @ys@ in turn (if any) has been removed from @xs@. Thus
349 -- > (xs ++ ys) \\ xs == ys.
351 -- It is a special case of 'deleteFirstsBy', which allows the programmer
352 -- to supply their own equality test.
354 (\\) :: (Eq a) => [a] -> [a] -> [a]
355 (\\) = foldl (flip delete)
357 -- | The 'union' function returns the list union of the two lists.
360 -- > "dog" `union` "cow" == "dogcw"
362 -- Duplicates, and elements of the first list, are removed from the
363 -- the second list, but if the first list contains duplicates, so will
365 -- It is a special case of 'unionBy', which allows the programmer to supply
366 -- their own equality test.
368 union :: (Eq a) => [a] -> [a] -> [a]
371 -- | The 'unionBy' function is the non-overloaded version of 'union'.
372 unionBy :: (a -> a -> Bool) -> [a] -> [a] -> [a]
373 unionBy eq xs ys = xs ++ foldl (flip (deleteBy eq)) (nubBy eq ys) xs
375 -- | The 'intersect' function takes the list intersection of two lists.
378 -- > [1,2,3,4] `intersect` [2,4,6,8] == [2,4]
380 -- If the first list contains duplicates, so will the result.
381 -- It is a special case of 'intersectBy', which allows the programmer to
382 -- supply their own equality test.
384 intersect :: (Eq a) => [a] -> [a] -> [a]
385 intersect = intersectBy (==)
387 -- | The 'intersectBy' function is the non-overloaded version of 'intersect'.
388 intersectBy :: (a -> a -> Bool) -> [a] -> [a] -> [a]
389 intersectBy eq xs ys = [x | x <- xs, any (eq x) ys]
391 -- | The 'intersperse' function takes an element and a list and
392 -- \`intersperses\' that element between the elements of the list.
395 -- > intersperse ',' "abcde" == "a,b,c,d,e"
397 intersperse :: a -> [a] -> [a]
398 intersperse _ [] = []
399 intersperse _ [x] = [x]
400 intersperse sep (x:xs) = x : sep : intersperse sep xs
402 -- | 'intercalate' @xs xss@ is equivalent to @('concat' ('intersperse' xs xss))@.
403 -- It inserts the list @xs@ in between the lists in @xss@ and concatenates the
405 intercalate :: [a] -> [[a]] -> [a]
406 intercalate xs xss = concat (intersperse xs xss)
408 -- | The 'transpose' function transposes the rows and columns of its argument.
411 -- > transpose [[1,2,3],[4,5,6]] == [[1,4],[2,5],[3,6]]
413 transpose :: [[a]] -> [[a]]
415 transpose ([] : xss) = transpose xss
416 transpose ((x:xs) : xss) = (x : [h | (h:t) <- xss]) : transpose (xs : [ t | (h:t) <- xss])
419 -- | The 'partition' function takes a predicate a list and returns
420 -- the pair of lists of elements which do and do not satisfy the
421 -- predicate, respectively; i.e.,
423 -- > partition p xs == (filter p xs, filter (not . p) xs)
425 partition :: (a -> Bool) -> [a] -> ([a],[a])
426 {-# INLINE partition #-}
427 partition p xs = foldr (select p) ([],[]) xs
429 select p x ~(ts,fs) | p x = (x:ts,fs)
430 | otherwise = (ts, x:fs)
432 -- | The 'mapAccumL' function behaves like a combination of 'map' and
433 -- 'foldl'; it applies a function to each element of a list, passing
434 -- an accumulating parameter from left to right, and returning a final
435 -- value of this accumulator together with the new list.
436 mapAccumL :: (acc -> x -> (acc, y)) -- Function of elt of input list
437 -- and accumulator, returning new
438 -- accumulator and elt of result list
439 -> acc -- Initial accumulator
441 -> (acc, [y]) -- Final accumulator and result list
442 mapAccumL _ s [] = (s, [])
443 mapAccumL f s (x:xs) = (s'',y:ys)
444 where (s', y ) = f s x
445 (s'',ys) = mapAccumL f s' xs
447 -- | The 'mapAccumR' function behaves like a combination of 'map' and
448 -- 'foldr'; it applies a function to each element of a list, passing
449 -- an accumulating parameter from right to left, and returning a final
450 -- value of this accumulator together with the new list.
451 mapAccumR :: (acc -> x -> (acc, y)) -- Function of elt of input list
452 -- and accumulator, returning new
453 -- accumulator and elt of result list
454 -> acc -- Initial accumulator
456 -> (acc, [y]) -- Final accumulator and result list
457 mapAccumR _ s [] = (s, [])
458 mapAccumR f s (x:xs) = (s'', y:ys)
459 where (s'',y ) = f s' x
460 (s', ys) = mapAccumR f s xs
462 -- | The 'insert' function takes an element and a list and inserts the
463 -- element into the list at the last position where it is still less
464 -- than or equal to the next element. In particular, if the list
465 -- is sorted before the call, the result will also be sorted.
466 -- It is a special case of 'insertBy', which allows the programmer to
467 -- supply their own comparison function.
468 insert :: Ord a => a -> [a] -> [a]
469 insert e ls = insertBy (compare) e ls
471 -- | The non-overloaded version of 'insert'.
472 insertBy :: (a -> a -> Ordering) -> a -> [a] -> [a]
473 insertBy _ x [] = [x]
474 insertBy cmp x ys@(y:ys')
476 GT -> y : insertBy cmp x ys'
479 #ifdef __GLASGOW_HASKELL__
481 -- | 'maximum' returns the maximum value from a list,
482 -- which must be non-empty, finite, and of an ordered type.
483 -- It is a special case of 'Data.List.maximumBy', which allows the
484 -- programmer to supply their own comparison function.
485 maximum :: (Ord a) => [a] -> a
486 maximum [] = errorEmptyList "maximum"
487 maximum xs = foldl1 max xs
490 "maximumInt" maximum = (strictMaximum :: [Int] -> Int);
491 "maximumInteger" maximum = (strictMaximum :: [Integer] -> Integer)
494 -- We can't make the overloaded version of maximum strict without
495 -- changing its semantics (max might not be strict), but we can for
496 -- the version specialised to 'Int'.
497 strictMaximum :: (Ord a) => [a] -> a
498 strictMaximum [] = errorEmptyList "maximum"
499 strictMaximum xs = foldl1' max xs
501 -- | 'minimum' returns the minimum value from a list,
502 -- which must be non-empty, finite, and of an ordered type.
503 -- It is a special case of 'Data.List.minimumBy', which allows the
504 -- programmer to supply their own comparison function.
505 minimum :: (Ord a) => [a] -> a
506 minimum [] = errorEmptyList "minimum"
507 minimum xs = foldl1 min xs
510 "minimumInt" minimum = (strictMinimum :: [Int] -> Int);
511 "minimumInteger" minimum = (strictMinimum :: [Integer] -> Integer)
514 strictMinimum :: (Ord a) => [a] -> a
515 strictMinimum [] = errorEmptyList "minimum"
516 strictMinimum xs = foldl1' min xs
518 #endif /* __GLASGOW_HASKELL__ */
520 -- | The 'maximumBy' function takes a comparison function and a list
521 -- and returns the greatest element of the list by the comparison function.
522 -- The list must be finite and non-empty.
523 maximumBy :: (a -> a -> Ordering) -> [a] -> a
524 maximumBy _ [] = error "List.maximumBy: empty list"
525 maximumBy cmp xs = foldl1 max xs
527 max x y = case cmp x y of
531 -- | The 'minimumBy' function takes a comparison function and a list
532 -- and returns the least element of the list by the comparison function.
533 -- The list must be finite and non-empty.
534 minimumBy :: (a -> a -> Ordering) -> [a] -> a
535 minimumBy _ [] = error "List.minimumBy: empty list"
536 minimumBy cmp xs = foldl1 min xs
538 min x y = case cmp x y of
542 -- | The 'genericLength' function is an overloaded version of 'length'. In
543 -- particular, instead of returning an 'Int', it returns any type which is
544 -- an instance of 'Num'. It is, however, less efficient than 'length'.
545 genericLength :: (Num i) => [b] -> i
547 genericLength (_:l) = 1 + genericLength l
549 -- | The 'genericTake' function is an overloaded version of 'take', which
550 -- accepts any 'Integral' value as the number of elements to take.
551 genericTake :: (Integral i) => i -> [a] -> [a]
553 genericTake _ [] = []
554 genericTake n (x:xs) | n > 0 = x : genericTake (n-1) xs
555 genericTake _ _ = error "List.genericTake: negative argument"
557 -- | The 'genericDrop' function is an overloaded version of 'drop', which
558 -- accepts any 'Integral' value as the number of elements to drop.
559 genericDrop :: (Integral i) => i -> [a] -> [a]
560 genericDrop 0 xs = xs
561 genericDrop _ [] = []
562 genericDrop n (_:xs) | n > 0 = genericDrop (n-1) xs
563 genericDrop _ _ = error "List.genericDrop: negative argument"
565 -- | The 'genericSplitAt' function is an overloaded version of 'splitAt', which
566 -- accepts any 'Integral' value as the position at which to split.
567 genericSplitAt :: (Integral i) => i -> [b] -> ([b],[b])
568 genericSplitAt 0 xs = ([],xs)
569 genericSplitAt _ [] = ([],[])
570 genericSplitAt n (x:xs) | n > 0 = (x:xs',xs'') where
571 (xs',xs'') = genericSplitAt (n-1) xs
572 genericSplitAt _ _ = error "List.genericSplitAt: negative argument"
574 -- | The 'genericIndex' function is an overloaded version of '!!', which
575 -- accepts any 'Integral' value as the index.
576 genericIndex :: (Integral a) => [b] -> a -> b
577 genericIndex (x:_) 0 = x
578 genericIndex (_:xs) n
579 | n > 0 = genericIndex xs (n-1)
580 | otherwise = error "List.genericIndex: negative argument."
581 genericIndex _ _ = error "List.genericIndex: index too large."
583 -- | The 'genericReplicate' function is an overloaded version of 'replicate',
584 -- which accepts any 'Integral' value as the number of repetitions to make.
585 genericReplicate :: (Integral i) => i -> a -> [a]
586 genericReplicate n x = genericTake n (repeat x)
588 -- | The 'zip4' function takes four lists and returns a list of
589 -- quadruples, analogous to 'zip'.
590 zip4 :: [a] -> [b] -> [c] -> [d] -> [(a,b,c,d)]
591 zip4 = zipWith4 (,,,)
593 -- | The 'zip5' function takes five lists and returns a list of
594 -- five-tuples, analogous to 'zip'.
595 zip5 :: [a] -> [b] -> [c] -> [d] -> [e] -> [(a,b,c,d,e)]
596 zip5 = zipWith5 (,,,,)
598 -- | The 'zip6' function takes six lists and returns a list of six-tuples,
599 -- analogous to 'zip'.
600 zip6 :: [a] -> [b] -> [c] -> [d] -> [e] -> [f] ->
602 zip6 = zipWith6 (,,,,,)
604 -- | The 'zip7' function takes seven lists and returns a list of
605 -- seven-tuples, analogous to 'zip'.
606 zip7 :: [a] -> [b] -> [c] -> [d] -> [e] -> [f] ->
607 [g] -> [(a,b,c,d,e,f,g)]
608 zip7 = zipWith7 (,,,,,,)
610 -- | The 'zipWith4' function takes a function which combines four
611 -- elements, as well as four lists and returns a list of their point-wise
612 -- combination, analogous to 'zipWith'.
613 zipWith4 :: (a->b->c->d->e) -> [a]->[b]->[c]->[d]->[e]
614 zipWith4 z (a:as) (b:bs) (c:cs) (d:ds)
615 = z a b c d : zipWith4 z as bs cs ds
616 zipWith4 _ _ _ _ _ = []
618 -- | The 'zipWith5' function takes a function which combines five
619 -- elements, as well as five lists and returns a list of their point-wise
620 -- combination, analogous to 'zipWith'.
621 zipWith5 :: (a->b->c->d->e->f) ->
622 [a]->[b]->[c]->[d]->[e]->[f]
623 zipWith5 z (a:as) (b:bs) (c:cs) (d:ds) (e:es)
624 = z a b c d e : zipWith5 z as bs cs ds es
625 zipWith5 _ _ _ _ _ _ = []
627 -- | The 'zipWith6' function takes a function which combines six
628 -- elements, as well as six lists and returns a list of their point-wise
629 -- combination, analogous to 'zipWith'.
630 zipWith6 :: (a->b->c->d->e->f->g) ->
631 [a]->[b]->[c]->[d]->[e]->[f]->[g]
632 zipWith6 z (a:as) (b:bs) (c:cs) (d:ds) (e:es) (f:fs)
633 = z a b c d e f : zipWith6 z as bs cs ds es fs
634 zipWith6 _ _ _ _ _ _ _ = []
636 -- | The 'zipWith7' function takes a function which combines seven
637 -- elements, as well as seven lists and returns a list of their point-wise
638 -- combination, analogous to 'zipWith'.
639 zipWith7 :: (a->b->c->d->e->f->g->h) ->
640 [a]->[b]->[c]->[d]->[e]->[f]->[g]->[h]
641 zipWith7 z (a:as) (b:bs) (c:cs) (d:ds) (e:es) (f:fs) (g:gs)
642 = z a b c d e f g : zipWith7 z as bs cs ds es fs gs
643 zipWith7 _ _ _ _ _ _ _ _ = []
645 -- | The 'unzip4' function takes a list of quadruples and returns four
646 -- lists, analogous to 'unzip'.
647 unzip4 :: [(a,b,c,d)] -> ([a],[b],[c],[d])
648 unzip4 = foldr (\(a,b,c,d) ~(as,bs,cs,ds) ->
649 (a:as,b:bs,c:cs,d:ds))
652 -- | The 'unzip5' function takes a list of five-tuples and returns five
653 -- lists, analogous to 'unzip'.
654 unzip5 :: [(a,b,c,d,e)] -> ([a],[b],[c],[d],[e])
655 unzip5 = foldr (\(a,b,c,d,e) ~(as,bs,cs,ds,es) ->
656 (a:as,b:bs,c:cs,d:ds,e:es))
659 -- | The 'unzip6' function takes a list of six-tuples and returns six
660 -- lists, analogous to 'unzip'.
661 unzip6 :: [(a,b,c,d,e,f)] -> ([a],[b],[c],[d],[e],[f])
662 unzip6 = foldr (\(a,b,c,d,e,f) ~(as,bs,cs,ds,es,fs) ->
663 (a:as,b:bs,c:cs,d:ds,e:es,f:fs))
666 -- | The 'unzip7' function takes a list of seven-tuples and returns
667 -- seven lists, analogous to 'unzip'.
668 unzip7 :: [(a,b,c,d,e,f,g)] -> ([a],[b],[c],[d],[e],[f],[g])
669 unzip7 = foldr (\(a,b,c,d,e,f,g) ~(as,bs,cs,ds,es,fs,gs) ->
670 (a:as,b:bs,c:cs,d:ds,e:es,f:fs,g:gs))
671 ([],[],[],[],[],[],[])
674 -- | The 'deleteFirstsBy' function takes a predicate and two lists and
675 -- returns the first list with the first occurrence of each element of
676 -- the second list removed.
677 deleteFirstsBy :: (a -> a -> Bool) -> [a] -> [a] -> [a]
678 deleteFirstsBy eq = foldl (flip (deleteBy eq))
680 -- | 'split' @x xs@ divides the list @xs@ at every occurrence of @x@ and
681 -- removes those occurrences.
685 -- > split 'i' "mississippi" -> ["m","ss","ss","pp",""]
686 -- > split 'i' [] -> [""]
687 split :: Eq a => a -> [a] -> [[a]]
688 split x xs = let (f,r) = break (==x) xs
693 -- | The 'group' function takes a list and returns a list of lists such
694 -- that the concatenation of the result is equal to the argument. Moreover,
695 -- each sublist in the result contains only equal elements. For example,
697 -- > group "Mississippi" = ["M","i","ss","i","ss","i","pp","i"]
699 -- It is a special case of 'groupBy', which allows the programmer to supply
700 -- their own equality test.
701 group :: Eq a => [a] -> [[a]]
704 -- | The 'groupBy' function is the non-overloaded version of 'group'.
705 groupBy :: (a -> a -> Bool) -> [a] -> [[a]]
707 groupBy eq (x:xs) = (x:ys) : groupBy eq zs
708 where (ys,zs) = span (eq x) xs
710 -- | The 'inits' function returns all initial segments of the argument,
711 -- shortest first. For example,
713 -- > inits "abc" == ["","a","ab","abc"]
715 inits :: [a] -> [[a]]
717 inits (x:xs) = [[]] ++ map (x:) (inits xs)
719 -- | The 'tails' function returns all final segments of the argument,
720 -- longest first. For example,
722 -- > tails "abc" == ["abc", "bc", "c",""]
724 tails :: [a] -> [[a]]
726 tails xxs@(_:xs) = xxs : tails xs
729 ------------------------------------------------------------------------------
730 -- Quick Sort algorithm taken from HBC's QSort library.
732 -- | The 'sort' function implements a stable sorting algorithm.
733 -- It is a special case of 'sortBy', which allows the programmer to supply
734 -- their own comparison function.
735 sort :: (Ord a) => [a] -> [a]
737 -- | The 'sortBy' function is the non-overloaded version of 'sort'.
738 sortBy :: (a -> a -> Ordering) -> [a] -> [a]
740 #ifdef USE_REPORT_PRELUDE
741 sort = sortBy compare
742 sortBy cmp = foldr (insertBy cmp) []
745 sortBy cmp l = mergesort cmp l
746 sort l = mergesort compare l
749 Quicksort replaced by mergesort, 14/5/2002.
751 From: Ian Lynagh <igloo@earth.li>
753 I am curious as to why the List.sort implementation in GHC is a
754 quicksort algorithm rather than an algorithm that guarantees n log n
755 time in the worst case? I have attached a mergesort implementation along
756 with a few scripts to time it's performance, the results of which are
757 shown below (* means it didn't finish successfully - in all cases this
758 was due to a stack overflow).
760 If I heap profile the random_list case with only 10000 then I see
761 random_list peaks at using about 2.5M of memory, whereas in the same
762 program using List.sort it uses only 100k.
764 Input style Input length Sort data Sort alg User time
765 stdin 10000 random_list sort 2.82
766 stdin 10000 random_list mergesort 2.96
767 stdin 10000 sorted sort 31.37
768 stdin 10000 sorted mergesort 1.90
769 stdin 10000 revsorted sort 31.21
770 stdin 10000 revsorted mergesort 1.88
771 stdin 100000 random_list sort *
772 stdin 100000 random_list mergesort *
773 stdin 100000 sorted sort *
774 stdin 100000 sorted mergesort *
775 stdin 100000 revsorted sort *
776 stdin 100000 revsorted mergesort *
777 func 10000 random_list sort 0.31
778 func 10000 random_list mergesort 0.91
779 func 10000 sorted sort 19.09
780 func 10000 sorted mergesort 0.15
781 func 10000 revsorted sort 19.17
782 func 10000 revsorted mergesort 0.16
783 func 100000 random_list sort 3.85
784 func 100000 random_list mergesort *
785 func 100000 sorted sort 5831.47
786 func 100000 sorted mergesort 2.23
787 func 100000 revsorted sort 5872.34
788 func 100000 revsorted mergesort 2.24
791 mergesort :: (a -> a -> Ordering) -> [a] -> [a]
792 mergesort cmp = mergesort' cmp . map wrap
794 mergesort' :: (a -> a -> Ordering) -> [[a]] -> [a]
795 mergesort' cmp [] = []
796 mergesort' cmp [xs] = xs
797 mergesort' cmp xss = mergesort' cmp (merge_pairs cmp xss)
799 merge_pairs :: (a -> a -> Ordering) -> [[a]] -> [[a]]
800 merge_pairs cmp [] = []
801 merge_pairs cmp [xs] = [xs]
802 merge_pairs cmp (xs:ys:xss) = merge cmp xs ys : merge_pairs cmp xss
804 merge :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
807 merge cmp (x:xs) (y:ys)
809 GT -> y : merge cmp (x:xs) ys
810 _ -> x : merge cmp xs (y:ys)
818 -- qsort is stable and does not concatenate.
819 qsort :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
822 qsort cmp (x:xs) r = qpart cmp x xs [] [] r
824 -- qpart partitions and sorts the sublists
825 qpart :: (a -> a -> Ordering) -> a -> [a] -> [a] -> [a] -> [a] -> [a]
826 qpart cmp x [] rlt rge r =
827 -- rlt and rge are in reverse order and must be sorted with an
828 -- anti-stable sorting
829 rqsort cmp rlt (x:rqsort cmp rge r)
830 qpart cmp x (y:ys) rlt rge r =
832 GT -> qpart cmp x ys (y:rlt) rge r
833 _ -> qpart cmp x ys rlt (y:rge) r
835 -- rqsort is as qsort but anti-stable, i.e. reverses equal elements
836 rqsort :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
839 rqsort cmp (x:xs) r = rqpart cmp x xs [] [] r
841 rqpart :: (a -> a -> Ordering) -> a -> [a] -> [a] -> [a] -> [a] -> [a]
842 rqpart cmp x [] rle rgt r =
843 qsort cmp rle (x:qsort cmp rgt r)
844 rqpart cmp x (y:ys) rle rgt r =
846 GT -> rqpart cmp x ys rle (y:rgt) r
847 _ -> rqpart cmp x ys (y:rle) rgt r
850 #endif /* USE_REPORT_PRELUDE */
852 -- | The 'unfoldr' function is a \`dual\' to 'foldr': while 'foldr'
853 -- reduces a list to a summary value, 'unfoldr' builds a list from
854 -- a seed value. The function takes the element and returns 'Nothing'
855 -- if it is done producing the list or returns 'Just' @(a,b)@, in which
856 -- case, @a@ is a prepended to the list and @b@ is used as the next
857 -- element in a recursive call. For example,
859 -- > iterate f == unfoldr (\x -> Just (x, f x))
861 -- In some cases, 'unfoldr' can undo a 'foldr' operation:
863 -- > unfoldr f' (foldr f z xs) == xs
865 -- if the following holds:
867 -- > f' (f x y) = Just (x,y)
870 unfoldr :: (b -> Maybe (a, b)) -> b -> [a]
873 Just (a,new_b) -> a : unfoldr f new_b
876 -- -----------------------------------------------------------------------------
878 -- | A strict version of 'foldl'.
879 foldl' :: (a -> b -> a) -> a -> [b] -> a
881 foldl' f a (x:xs) = let a' = f a x in a' `seq` foldl' f a' xs
883 #ifdef __GLASGOW_HASKELL__
884 -- | 'foldl1' is a variant of 'foldl' that has no starting value argument,
885 -- and thus must be applied to non-empty lists.
886 foldl1 :: (a -> a -> a) -> [a] -> a
887 foldl1 f (x:xs) = foldl f x xs
888 foldl1 _ [] = errorEmptyList "foldl1"
889 #endif /* __GLASGOW_HASKELL__ */
891 -- | A strict version of 'foldl1'
892 foldl1' :: (a -> a -> a) -> [a] -> a
893 foldl1' f (x:xs) = foldl' f x xs
894 foldl1' _ [] = errorEmptyList "foldl1'"
896 #ifdef __GLASGOW_HASKELL__
897 -- -----------------------------------------------------------------------------
898 -- List sum and product
900 {-# SPECIALISE sum :: [Int] -> Int #-}
901 {-# SPECIALISE sum :: [Integer] -> Integer #-}
902 {-# SPECIALISE product :: [Int] -> Int #-}
903 {-# SPECIALISE product :: [Integer] -> Integer #-}
904 -- | The 'sum' function computes the sum of a finite list of numbers.
905 sum :: (Num a) => [a] -> a
906 -- | The 'product' function computes the product of a finite list of numbers.
907 product :: (Num a) => [a] -> a
908 #ifdef USE_REPORT_PRELUDE
910 product = foldl (*) 1
915 sum' (x:xs) a = sum' xs (a+x)
919 prod (x:xs) a = prod xs (a*x)
922 -- -----------------------------------------------------------------------------
923 -- Functions on strings
925 -- | 'lines' breaks a string up into a list of strings at newline
926 -- characters. The resulting strings do not contain newlines.
927 lines :: String -> [String]
929 lines s = let (l, s') = break (== '\n') s
934 -- | 'unlines' is an inverse operation to 'lines'.
935 -- It joins lines, after appending a terminating newline to each.
936 unlines :: [String] -> String
937 #ifdef USE_REPORT_PRELUDE
938 unlines = concatMap (++ "\n")
940 -- HBC version (stolen)
941 -- here's a more efficient version
943 unlines (l:ls) = l ++ '\n' : unlines ls
946 -- | 'words' breaks a string up into a list of words, which were delimited
948 words :: String -> [String]
949 words s = case dropWhile {-partain:Char.-}isSpace s of
953 break {-partain:Char.-}isSpace s'
955 -- | 'unwords' is an inverse operation to 'words'.
956 -- It joins words with separating spaces.
957 unwords :: [String] -> String
958 #ifdef USE_REPORT_PRELUDE
960 unwords ws = foldr1 (\w s -> w ++ ' ':s) ws
962 -- HBC version (stolen)
963 -- here's a more efficient version
966 unwords (w:ws) = w ++ ' ' : unwords ws
969 #else /* !__GLASGOW_HASKELL__ */
971 errorEmptyList :: String -> a
973 error ("Prelude." ++ fun ++ ": empty list")
975 #endif /* !__GLASGOW_HASKELL__ */