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 , stripPrefix -- :: Eq a => [a] -> [a] -> Maybe [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 -- It is often convenient to use these functions together with
175 -- 'Data.Function.on', for instance @'sortBy' ('compare'
178 -- *** User-supplied equality (replacing an @Eq@ context)
179 -- | The predicate is assumed to define an equivalence.
180 , nubBy -- :: (a -> a -> Bool) -> [a] -> [a]
181 , deleteBy -- :: (a -> a -> Bool) -> a -> [a] -> [a]
182 , deleteFirstsBy -- :: (a -> a -> Bool) -> [a] -> [a] -> [a]
183 , unionBy -- :: (a -> a -> Bool) -> [a] -> [a] -> [a]
184 , intersectBy -- :: (a -> a -> Bool) -> [a] -> [a] -> [a]
185 , groupBy -- :: (a -> a -> Bool) -> [a] -> [[a]]
187 -- *** User-supplied comparison (replacing an @Ord@ context)
188 -- | The function is assumed to define a total ordering.
189 , sortBy -- :: (a -> a -> Ordering) -> [a] -> [a]
190 , insertBy -- :: (a -> a -> Ordering) -> a -> [a] -> [a]
191 , maximumBy -- :: (a -> a -> Ordering) -> [a] -> a
192 , minimumBy -- :: (a -> a -> Ordering) -> [a] -> a
194 -- ** The \"@generic@\" operations
195 -- | The prefix \`@generic@\' indicates an overloaded function that
196 -- is a generalized version of a "Prelude" function.
198 , genericLength -- :: (Integral a) => [b] -> a
199 , genericTake -- :: (Integral a) => a -> [b] -> [b]
200 , genericDrop -- :: (Integral a) => a -> [b] -> [b]
201 , genericSplitAt -- :: (Integral a) => a -> [b] -> ([b], [b])
202 , genericIndex -- :: (Integral a) => [b] -> a -> b
203 , genericReplicate -- :: (Integral a) => a -> b -> [b]
212 import Data.Char ( isSpace )
214 #ifdef __GLASGOW_HASKELL__
221 infix 5 \\ -- comment to fool cpp
223 -- -----------------------------------------------------------------------------
226 -- | The 'stripPrefix' function drops the given prefix from a list.
227 -- It returns 'Nothing' if the list did not start with the prefix
228 -- given, or 'Just' the list after the prefix, if it does.
230 -- > stripPrefix "foo" "foobar" -> Just "bar"
231 -- > stripPrefix "foo" "foo" -> Just ""
232 -- > stripPrefix "foo" "barfoo" -> Nothing
233 -- > stripPrefix "foo" "barfoobaz" -> Nothing
234 stripPrefix :: Eq a => [a] -> [a] -> Maybe [a]
235 stripPrefix [] ys = Just ys
236 stripPrefix (x:xs) (y:ys)
237 | x == y = stripPrefix xs ys
238 stripPrefix _ _ = Nothing
240 -- | The 'elemIndex' function returns the index of the first element
241 -- in the given list which is equal (by '==') to the query element,
242 -- or 'Nothing' if there is no such element.
243 elemIndex :: Eq a => a -> [a] -> Maybe Int
244 elemIndex x = findIndex (x==)
246 -- | The 'elemIndices' function extends 'elemIndex', by returning the
247 -- indices of all elements equal to the query element, in ascending order.
248 elemIndices :: Eq a => a -> [a] -> [Int]
249 elemIndices x = findIndices (x==)
251 -- | The 'find' function takes a predicate and a list and returns the
252 -- first element in the list matching the predicate, or 'Nothing' if
253 -- there is no such element.
254 find :: (a -> Bool) -> [a] -> Maybe a
255 find p = listToMaybe . filter p
257 -- | The 'findIndex' function takes a predicate and a list and returns
258 -- the index of the first element in the list satisfying the predicate,
259 -- or 'Nothing' if there is no such element.
260 findIndex :: (a -> Bool) -> [a] -> Maybe Int
261 findIndex p = listToMaybe . findIndices p
263 -- | The 'findIndices' function extends 'findIndex', by returning the
264 -- indices of all elements satisfying the predicate, in ascending order.
265 findIndices :: (a -> Bool) -> [a] -> [Int]
267 #if defined(USE_REPORT_PRELUDE) || !defined(__GLASGOW_HASKELL__)
268 findIndices p xs = [ i | (x,i) <- zip xs [0..], p x]
270 -- Efficient definition
271 findIndices p ls = loop 0# ls
274 loop n (x:xs) | p x = I# n : loop (n +# 1#) xs
275 | otherwise = loop (n +# 1#) xs
276 #endif /* USE_REPORT_PRELUDE */
278 -- | The 'isPrefixOf' function takes two lists and returns 'True'
279 -- iff the first list is a prefix of the second.
280 isPrefixOf :: (Eq a) => [a] -> [a] -> Bool
281 isPrefixOf [] _ = True
282 isPrefixOf _ [] = False
283 isPrefixOf (x:xs) (y:ys)= x == y && isPrefixOf xs ys
285 -- | The 'isSuffixOf' function takes two lists and returns 'True'
286 -- iff the first list is a suffix of the second.
287 -- Both lists must be finite.
288 isSuffixOf :: (Eq a) => [a] -> [a] -> Bool
289 isSuffixOf x y = reverse x `isPrefixOf` reverse y
291 -- | The 'isInfixOf' function takes two lists and returns 'True'
292 -- iff the first list is contained, wholly and intact,
293 -- anywhere within the second.
297 -- >isInfixOf "Haskell" "I really like Haskell." -> True
298 -- >isInfixOf "Ial" "I really like Haskell." -> False
299 isInfixOf :: (Eq a) => [a] -> [a] -> Bool
300 isInfixOf needle haystack = any (isPrefixOf needle) (tails haystack)
302 -- | The 'nub' function removes duplicate elements from a list.
303 -- In particular, it keeps only the first occurrence of each element.
304 -- (The name 'nub' means \`essence\'.)
305 -- It is a special case of 'nubBy', which allows the programmer to supply
306 -- their own equality test.
307 nub :: (Eq a) => [a] -> [a]
308 #ifdef USE_REPORT_PRELUDE
312 nub l = nub' l [] -- '
316 | x `elem` ls = nub' xs ls -- '
317 | otherwise = x : nub' xs (x:ls) -- '
320 -- | The 'nubBy' function behaves just like 'nub', except it uses a
321 -- user-supplied equality predicate instead of the overloaded '=='
323 nubBy :: (a -> a -> Bool) -> [a] -> [a]
324 #ifdef USE_REPORT_PRELUDE
326 nubBy eq (x:xs) = x : nubBy eq (filter (\ y -> not (eq x y)) xs)
328 nubBy eq l = nubBy' l []
332 | elem_by eq y xs = nubBy' ys xs
333 | otherwise = y : nubBy' ys (y:xs)
336 -- Note that we keep the call to `eq` with arguments in the
337 -- same order as in the reference implementation
338 -- 'xs' is the list of things we've seen so far,
339 -- 'y' is the potential new element
340 elem_by :: (a -> a -> Bool) -> a -> [a] -> Bool
341 elem_by _ _ [] = False
342 elem_by eq y (x:xs) = x `eq` y || elem_by eq y xs
346 -- | 'delete' @x@ removes the first occurrence of @x@ from its list argument.
349 -- > delete 'a' "banana" == "bnana"
351 -- It is a special case of 'deleteBy', which allows the programmer to
352 -- supply their own equality test.
354 delete :: (Eq a) => a -> [a] -> [a]
355 delete = deleteBy (==)
357 -- | The 'deleteBy' function behaves like 'delete', but takes a
358 -- user-supplied equality predicate.
359 deleteBy :: (a -> a -> Bool) -> a -> [a] -> [a]
361 deleteBy eq x (y:ys) = if x `eq` y then ys else y : deleteBy eq x ys
363 -- | The '\\' function is list difference ((non-associative).
364 -- In the result of @xs@ '\\' @ys@, the first occurrence of each element of
365 -- @ys@ in turn (if any) has been removed from @xs@. Thus
367 -- > (xs ++ ys) \\ xs == ys.
369 -- It is a special case of 'deleteFirstsBy', which allows the programmer
370 -- to supply their own equality test.
372 (\\) :: (Eq a) => [a] -> [a] -> [a]
373 (\\) = foldl (flip delete)
375 -- | The 'union' function returns the list union of the two lists.
378 -- > "dog" `union` "cow" == "dogcw"
380 -- Duplicates, and elements of the first list, are removed from the
381 -- the second list, but if the first list contains duplicates, so will
383 -- It is a special case of 'unionBy', which allows the programmer to supply
384 -- their own equality test.
386 union :: (Eq a) => [a] -> [a] -> [a]
389 -- | The 'unionBy' function is the non-overloaded version of 'union'.
390 unionBy :: (a -> a -> Bool) -> [a] -> [a] -> [a]
391 unionBy eq xs ys = xs ++ foldl (flip (deleteBy eq)) (nubBy eq ys) xs
393 -- | The 'intersect' function takes the list intersection of two lists.
396 -- > [1,2,3,4] `intersect` [2,4,6,8] == [2,4]
398 -- If the first list contains duplicates, so will the result.
399 -- It is a special case of 'intersectBy', which allows the programmer to
400 -- supply their own equality test.
402 intersect :: (Eq a) => [a] -> [a] -> [a]
403 intersect = intersectBy (==)
405 -- | The 'intersectBy' function is the non-overloaded version of 'intersect'.
406 intersectBy :: (a -> a -> Bool) -> [a] -> [a] -> [a]
407 intersectBy eq xs ys = [x | x <- xs, any (eq x) ys]
409 -- | The 'intersperse' function takes an element and a list and
410 -- \`intersperses\' that element between the elements of the list.
413 -- > intersperse ',' "abcde" == "a,b,c,d,e"
415 intersperse :: a -> [a] -> [a]
416 intersperse _ [] = []
417 intersperse _ [x] = [x]
418 intersperse sep (x:xs) = x : sep : intersperse sep xs
420 -- | 'intercalate' @xs xss@ is equivalent to @('concat' ('intersperse' xs xss))@.
421 -- It inserts the list @xs@ in between the lists in @xss@ and concatenates the
423 intercalate :: [a] -> [[a]] -> [a]
424 intercalate xs xss = concat (intersperse xs xss)
426 -- | The 'transpose' function transposes the rows and columns of its argument.
429 -- > transpose [[1,2,3],[4,5,6]] == [[1,4],[2,5],[3,6]]
431 transpose :: [[a]] -> [[a]]
433 transpose ([] : xss) = transpose xss
434 transpose ((x:xs) : xss) = (x : [h | (h:t) <- xss]) : transpose (xs : [ t | (h:t) <- xss])
437 -- | The 'partition' function takes a predicate a list and returns
438 -- the pair of lists of elements which do and do not satisfy the
439 -- predicate, respectively; i.e.,
441 -- > partition p xs == (filter p xs, filter (not . p) xs)
443 partition :: (a -> Bool) -> [a] -> ([a],[a])
444 {-# INLINE partition #-}
445 partition p xs = foldr (select p) ([],[]) xs
447 select p x ~(ts,fs) | p x = (x:ts,fs)
448 | otherwise = (ts, x:fs)
450 -- | The 'mapAccumL' function behaves like a combination of 'map' and
451 -- 'foldl'; it applies a function to each element of a list, passing
452 -- an accumulating parameter from left to right, and returning a final
453 -- value of this accumulator together with the new list.
454 mapAccumL :: (acc -> x -> (acc, y)) -- Function of elt of input list
455 -- and accumulator, returning new
456 -- accumulator and elt of result list
457 -> acc -- Initial accumulator
459 -> (acc, [y]) -- Final accumulator and result list
460 mapAccumL _ s [] = (s, [])
461 mapAccumL f s (x:xs) = (s'',y:ys)
462 where (s', y ) = f s x
463 (s'',ys) = mapAccumL f s' xs
465 -- | The 'mapAccumR' function behaves like a combination of 'map' and
466 -- 'foldr'; it applies a function to each element of a list, passing
467 -- an accumulating parameter from right to left, and returning a final
468 -- value of this accumulator together with the new list.
469 mapAccumR :: (acc -> x -> (acc, y)) -- Function of elt of input list
470 -- and accumulator, returning new
471 -- accumulator and elt of result list
472 -> acc -- Initial accumulator
474 -> (acc, [y]) -- Final accumulator and result list
475 mapAccumR _ s [] = (s, [])
476 mapAccumR f s (x:xs) = (s'', y:ys)
477 where (s'',y ) = f s' x
478 (s', ys) = mapAccumR f s xs
480 -- | The 'insert' function takes an element and a list and inserts the
481 -- element into the list at the last position where it is still less
482 -- than or equal to the next element. In particular, if the list
483 -- is sorted before the call, the result will also be sorted.
484 -- It is a special case of 'insertBy', which allows the programmer to
485 -- supply their own comparison function.
486 insert :: Ord a => a -> [a] -> [a]
487 insert e ls = insertBy (compare) e ls
489 -- | The non-overloaded version of 'insert'.
490 insertBy :: (a -> a -> Ordering) -> a -> [a] -> [a]
491 insertBy _ x [] = [x]
492 insertBy cmp x ys@(y:ys')
494 GT -> y : insertBy cmp x ys'
497 #ifdef __GLASGOW_HASKELL__
499 -- | 'maximum' returns the maximum value from a list,
500 -- which must be non-empty, finite, and of an ordered type.
501 -- It is a special case of 'Data.List.maximumBy', which allows the
502 -- programmer to supply their own comparison function.
503 maximum :: (Ord a) => [a] -> a
504 maximum [] = errorEmptyList "maximum"
505 maximum xs = foldl1 max xs
508 "maximumInt" maximum = (strictMaximum :: [Int] -> Int);
509 "maximumInteger" maximum = (strictMaximum :: [Integer] -> Integer)
512 -- We can't make the overloaded version of maximum strict without
513 -- changing its semantics (max might not be strict), but we can for
514 -- the version specialised to 'Int'.
515 strictMaximum :: (Ord a) => [a] -> a
516 strictMaximum [] = errorEmptyList "maximum"
517 strictMaximum xs = foldl1' max xs
519 -- | 'minimum' returns the minimum value from a list,
520 -- which must be non-empty, finite, and of an ordered type.
521 -- It is a special case of 'Data.List.minimumBy', which allows the
522 -- programmer to supply their own comparison function.
523 minimum :: (Ord a) => [a] -> a
524 minimum [] = errorEmptyList "minimum"
525 minimum xs = foldl1 min xs
528 "minimumInt" minimum = (strictMinimum :: [Int] -> Int);
529 "minimumInteger" minimum = (strictMinimum :: [Integer] -> Integer)
532 strictMinimum :: (Ord a) => [a] -> a
533 strictMinimum [] = errorEmptyList "minimum"
534 strictMinimum xs = foldl1' min xs
536 #endif /* __GLASGOW_HASKELL__ */
538 -- | The 'maximumBy' function takes a comparison function and a list
539 -- and returns the greatest element of the list by the comparison function.
540 -- The list must be finite and non-empty.
541 maximumBy :: (a -> a -> Ordering) -> [a] -> a
542 maximumBy _ [] = error "List.maximumBy: empty list"
543 maximumBy cmp xs = foldl1 max xs
545 max x y = case cmp x y of
549 -- | The 'minimumBy' function takes a comparison function and a list
550 -- and returns the least element of the list by the comparison function.
551 -- The list must be finite and non-empty.
552 minimumBy :: (a -> a -> Ordering) -> [a] -> a
553 minimumBy _ [] = error "List.minimumBy: empty list"
554 minimumBy cmp xs = foldl1 min xs
556 min x y = case cmp x y of
560 -- | The 'genericLength' function is an overloaded version of 'length'. In
561 -- particular, instead of returning an 'Int', it returns any type which is
562 -- an instance of 'Num'. It is, however, less efficient than 'length'.
563 genericLength :: (Num i) => [b] -> i
565 genericLength (_:l) = 1 + genericLength l
567 -- | The 'genericTake' function is an overloaded version of 'take', which
568 -- accepts any 'Integral' value as the number of elements to take.
569 genericTake :: (Integral i) => i -> [a] -> [a]
571 genericTake _ [] = []
572 genericTake n (x:xs) | n > 0 = x : genericTake (n-1) xs
573 genericTake _ _ = error "List.genericTake: negative argument"
575 -- | The 'genericDrop' function is an overloaded version of 'drop', which
576 -- accepts any 'Integral' value as the number of elements to drop.
577 genericDrop :: (Integral i) => i -> [a] -> [a]
578 genericDrop 0 xs = xs
579 genericDrop _ [] = []
580 genericDrop n (_:xs) | n > 0 = genericDrop (n-1) xs
581 genericDrop _ _ = error "List.genericDrop: negative argument"
583 -- | The 'genericSplitAt' function is an overloaded version of 'splitAt', which
584 -- accepts any 'Integral' value as the position at which to split.
585 genericSplitAt :: (Integral i) => i -> [b] -> ([b],[b])
586 genericSplitAt 0 xs = ([],xs)
587 genericSplitAt _ [] = ([],[])
588 genericSplitAt n (x:xs) | n > 0 = (x:xs',xs'') where
589 (xs',xs'') = genericSplitAt (n-1) xs
590 genericSplitAt _ _ = error "List.genericSplitAt: negative argument"
592 -- | The 'genericIndex' function is an overloaded version of '!!', which
593 -- accepts any 'Integral' value as the index.
594 genericIndex :: (Integral a) => [b] -> a -> b
595 genericIndex (x:_) 0 = x
596 genericIndex (_:xs) n
597 | n > 0 = genericIndex xs (n-1)
598 | otherwise = error "List.genericIndex: negative argument."
599 genericIndex _ _ = error "List.genericIndex: index too large."
601 -- | The 'genericReplicate' function is an overloaded version of 'replicate',
602 -- which accepts any 'Integral' value as the number of repetitions to make.
603 genericReplicate :: (Integral i) => i -> a -> [a]
604 genericReplicate n x = genericTake n (repeat x)
606 -- | The 'zip4' function takes four lists and returns a list of
607 -- quadruples, analogous to 'zip'.
608 zip4 :: [a] -> [b] -> [c] -> [d] -> [(a,b,c,d)]
609 zip4 = zipWith4 (,,,)
611 -- | The 'zip5' function takes five lists and returns a list of
612 -- five-tuples, analogous to 'zip'.
613 zip5 :: [a] -> [b] -> [c] -> [d] -> [e] -> [(a,b,c,d,e)]
614 zip5 = zipWith5 (,,,,)
616 -- | The 'zip6' function takes six lists and returns a list of six-tuples,
617 -- analogous to 'zip'.
618 zip6 :: [a] -> [b] -> [c] -> [d] -> [e] -> [f] ->
620 zip6 = zipWith6 (,,,,,)
622 -- | The 'zip7' function takes seven lists and returns a list of
623 -- seven-tuples, analogous to 'zip'.
624 zip7 :: [a] -> [b] -> [c] -> [d] -> [e] -> [f] ->
625 [g] -> [(a,b,c,d,e,f,g)]
626 zip7 = zipWith7 (,,,,,,)
628 -- | The 'zipWith4' function takes a function which combines four
629 -- elements, as well as four lists and returns a list of their point-wise
630 -- combination, analogous to 'zipWith'.
631 zipWith4 :: (a->b->c->d->e) -> [a]->[b]->[c]->[d]->[e]
632 zipWith4 z (a:as) (b:bs) (c:cs) (d:ds)
633 = z a b c d : zipWith4 z as bs cs ds
634 zipWith4 _ _ _ _ _ = []
636 -- | The 'zipWith5' function takes a function which combines five
637 -- elements, as well as five lists and returns a list of their point-wise
638 -- combination, analogous to 'zipWith'.
639 zipWith5 :: (a->b->c->d->e->f) ->
640 [a]->[b]->[c]->[d]->[e]->[f]
641 zipWith5 z (a:as) (b:bs) (c:cs) (d:ds) (e:es)
642 = z a b c d e : zipWith5 z as bs cs ds es
643 zipWith5 _ _ _ _ _ _ = []
645 -- | The 'zipWith6' function takes a function which combines six
646 -- elements, as well as six lists and returns a list of their point-wise
647 -- combination, analogous to 'zipWith'.
648 zipWith6 :: (a->b->c->d->e->f->g) ->
649 [a]->[b]->[c]->[d]->[e]->[f]->[g]
650 zipWith6 z (a:as) (b:bs) (c:cs) (d:ds) (e:es) (f:fs)
651 = z a b c d e f : zipWith6 z as bs cs ds es fs
652 zipWith6 _ _ _ _ _ _ _ = []
654 -- | The 'zipWith7' function takes a function which combines seven
655 -- elements, as well as seven lists and returns a list of their point-wise
656 -- combination, analogous to 'zipWith'.
657 zipWith7 :: (a->b->c->d->e->f->g->h) ->
658 [a]->[b]->[c]->[d]->[e]->[f]->[g]->[h]
659 zipWith7 z (a:as) (b:bs) (c:cs) (d:ds) (e:es) (f:fs) (g:gs)
660 = z a b c d e f g : zipWith7 z as bs cs ds es fs gs
661 zipWith7 _ _ _ _ _ _ _ _ = []
663 -- | The 'unzip4' function takes a list of quadruples and returns four
664 -- lists, analogous to 'unzip'.
665 unzip4 :: [(a,b,c,d)] -> ([a],[b],[c],[d])
666 unzip4 = foldr (\(a,b,c,d) ~(as,bs,cs,ds) ->
667 (a:as,b:bs,c:cs,d:ds))
670 -- | The 'unzip5' function takes a list of five-tuples and returns five
671 -- lists, analogous to 'unzip'.
672 unzip5 :: [(a,b,c,d,e)] -> ([a],[b],[c],[d],[e])
673 unzip5 = foldr (\(a,b,c,d,e) ~(as,bs,cs,ds,es) ->
674 (a:as,b:bs,c:cs,d:ds,e:es))
677 -- | The 'unzip6' function takes a list of six-tuples and returns six
678 -- lists, analogous to 'unzip'.
679 unzip6 :: [(a,b,c,d,e,f)] -> ([a],[b],[c],[d],[e],[f])
680 unzip6 = foldr (\(a,b,c,d,e,f) ~(as,bs,cs,ds,es,fs) ->
681 (a:as,b:bs,c:cs,d:ds,e:es,f:fs))
684 -- | The 'unzip7' function takes a list of seven-tuples and returns
685 -- seven lists, analogous to 'unzip'.
686 unzip7 :: [(a,b,c,d,e,f,g)] -> ([a],[b],[c],[d],[e],[f],[g])
687 unzip7 = foldr (\(a,b,c,d,e,f,g) ~(as,bs,cs,ds,es,fs,gs) ->
688 (a:as,b:bs,c:cs,d:ds,e:es,f:fs,g:gs))
689 ([],[],[],[],[],[],[])
692 -- | The 'deleteFirstsBy' function takes a predicate and two lists and
693 -- returns the first list with the first occurrence of each element of
694 -- the second list removed.
695 deleteFirstsBy :: (a -> a -> Bool) -> [a] -> [a] -> [a]
696 deleteFirstsBy eq = foldl (flip (deleteBy eq))
698 -- | The 'group' function takes a list and returns a list of lists such
699 -- that the concatenation of the result is equal to the argument. Moreover,
700 -- each sublist in the result contains only equal elements. For example,
702 -- > group "Mississippi" = ["M","i","ss","i","ss","i","pp","i"]
704 -- It is a special case of 'groupBy', which allows the programmer to supply
705 -- their own equality test.
706 group :: Eq a => [a] -> [[a]]
709 -- | The 'groupBy' function is the non-overloaded version of 'group'.
710 groupBy :: (a -> a -> Bool) -> [a] -> [[a]]
712 groupBy eq (x:xs) = (x:ys) : groupBy eq zs
713 where (ys,zs) = span (eq x) xs
715 -- | The 'inits' function returns all initial segments of the argument,
716 -- shortest first. For example,
718 -- > inits "abc" == ["","a","ab","abc"]
720 inits :: [a] -> [[a]]
722 inits (x:xs) = [[]] ++ map (x:) (inits xs)
724 -- | The 'tails' function returns all final segments of the argument,
725 -- longest first. For example,
727 -- > tails "abc" == ["abc", "bc", "c",""]
729 tails :: [a] -> [[a]]
731 tails xxs@(_:xs) = xxs : tails xs
734 ------------------------------------------------------------------------------
735 -- Quick Sort algorithm taken from HBC's QSort library.
737 -- | The 'sort' function implements a stable sorting algorithm.
738 -- It is a special case of 'sortBy', which allows the programmer to supply
739 -- their own comparison function.
740 sort :: (Ord a) => [a] -> [a]
742 -- | The 'sortBy' function is the non-overloaded version of 'sort'.
743 sortBy :: (a -> a -> Ordering) -> [a] -> [a]
745 #ifdef USE_REPORT_PRELUDE
746 sort = sortBy compare
747 sortBy cmp = foldr (insertBy cmp) []
750 sortBy cmp l = mergesort cmp l
751 sort l = mergesort compare l
754 Quicksort replaced by mergesort, 14/5/2002.
756 From: Ian Lynagh <igloo@earth.li>
758 I am curious as to why the List.sort implementation in GHC is a
759 quicksort algorithm rather than an algorithm that guarantees n log n
760 time in the worst case? I have attached a mergesort implementation along
761 with a few scripts to time it's performance, the results of which are
762 shown below (* means it didn't finish successfully - in all cases this
763 was due to a stack overflow).
765 If I heap profile the random_list case with only 10000 then I see
766 random_list peaks at using about 2.5M of memory, whereas in the same
767 program using List.sort it uses only 100k.
769 Input style Input length Sort data Sort alg User time
770 stdin 10000 random_list sort 2.82
771 stdin 10000 random_list mergesort 2.96
772 stdin 10000 sorted sort 31.37
773 stdin 10000 sorted mergesort 1.90
774 stdin 10000 revsorted sort 31.21
775 stdin 10000 revsorted mergesort 1.88
776 stdin 100000 random_list sort *
777 stdin 100000 random_list mergesort *
778 stdin 100000 sorted sort *
779 stdin 100000 sorted mergesort *
780 stdin 100000 revsorted sort *
781 stdin 100000 revsorted mergesort *
782 func 10000 random_list sort 0.31
783 func 10000 random_list mergesort 0.91
784 func 10000 sorted sort 19.09
785 func 10000 sorted mergesort 0.15
786 func 10000 revsorted sort 19.17
787 func 10000 revsorted mergesort 0.16
788 func 100000 random_list sort 3.85
789 func 100000 random_list mergesort *
790 func 100000 sorted sort 5831.47
791 func 100000 sorted mergesort 2.23
792 func 100000 revsorted sort 5872.34
793 func 100000 revsorted mergesort 2.24
796 mergesort :: (a -> a -> Ordering) -> [a] -> [a]
797 mergesort cmp = mergesort' cmp . map wrap
799 mergesort' :: (a -> a -> Ordering) -> [[a]] -> [a]
800 mergesort' cmp [] = []
801 mergesort' cmp [xs] = xs
802 mergesort' cmp xss = mergesort' cmp (merge_pairs cmp xss)
804 merge_pairs :: (a -> a -> Ordering) -> [[a]] -> [[a]]
805 merge_pairs cmp [] = []
806 merge_pairs cmp [xs] = [xs]
807 merge_pairs cmp (xs:ys:xss) = merge cmp xs ys : merge_pairs cmp xss
809 merge :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
812 merge cmp (x:xs) (y:ys)
814 GT -> y : merge cmp (x:xs) ys
815 _ -> x : merge cmp xs (y:ys)
823 -- qsort is stable and does not concatenate.
824 qsort :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
827 qsort cmp (x:xs) r = qpart cmp x xs [] [] r
829 -- qpart partitions and sorts the sublists
830 qpart :: (a -> a -> Ordering) -> a -> [a] -> [a] -> [a] -> [a] -> [a]
831 qpart cmp x [] rlt rge r =
832 -- rlt and rge are in reverse order and must be sorted with an
833 -- anti-stable sorting
834 rqsort cmp rlt (x:rqsort cmp rge r)
835 qpart cmp x (y:ys) rlt rge r =
837 GT -> qpart cmp x ys (y:rlt) rge r
838 _ -> qpart cmp x ys rlt (y:rge) r
840 -- rqsort is as qsort but anti-stable, i.e. reverses equal elements
841 rqsort :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
844 rqsort cmp (x:xs) r = rqpart cmp x xs [] [] r
846 rqpart :: (a -> a -> Ordering) -> a -> [a] -> [a] -> [a] -> [a] -> [a]
847 rqpart cmp x [] rle rgt r =
848 qsort cmp rle (x:qsort cmp rgt r)
849 rqpart cmp x (y:ys) rle rgt r =
851 GT -> rqpart cmp x ys rle (y:rgt) r
852 _ -> rqpart cmp x ys (y:rle) rgt r
855 #endif /* USE_REPORT_PRELUDE */
857 -- | The 'unfoldr' function is a \`dual\' to 'foldr': while 'foldr'
858 -- reduces a list to a summary value, 'unfoldr' builds a list from
859 -- a seed value. The function takes the element and returns 'Nothing'
860 -- if it is done producing the list or returns 'Just' @(a,b)@, in which
861 -- case, @a@ is a prepended to the list and @b@ is used as the next
862 -- element in a recursive call. For example,
864 -- > iterate f == unfoldr (\x -> Just (x, f x))
866 -- In some cases, 'unfoldr' can undo a 'foldr' operation:
868 -- > unfoldr f' (foldr f z xs) == xs
870 -- if the following holds:
872 -- > f' (f x y) = Just (x,y)
875 -- A simple use of unfoldr:
877 -- > unfoldr (\b -> if b == 0 then Nothing else Just (b, b-1)) 10
878 -- > [10,9,8,7,6,5,4,3,2,1]
880 unfoldr :: (b -> Maybe (a, b)) -> b -> [a]
883 Just (a,new_b) -> a : unfoldr f new_b
886 -- -----------------------------------------------------------------------------
888 -- | A strict version of 'foldl'.
889 foldl' :: (a -> b -> a) -> a -> [b] -> a
890 #ifdef __GLASGOW_HASKELL__
891 foldl' f z xs = lgo z xs
893 lgo z (x:xs) = let z' = f z x in z' `seq` lgo z' xs
896 foldl' f a (x:xs) = let a' = f a x in a' `seq` foldl' f a' xs
899 #ifdef __GLASGOW_HASKELL__
900 -- | 'foldl1' is a variant of 'foldl' that has no starting value argument,
901 -- and thus must be applied to non-empty lists.
902 foldl1 :: (a -> a -> a) -> [a] -> a
903 foldl1 f (x:xs) = foldl f x xs
904 foldl1 _ [] = errorEmptyList "foldl1"
905 #endif /* __GLASGOW_HASKELL__ */
907 -- | A strict version of 'foldl1'
908 foldl1' :: (a -> a -> a) -> [a] -> a
909 foldl1' f (x:xs) = foldl' f x xs
910 foldl1' _ [] = errorEmptyList "foldl1'"
912 #ifdef __GLASGOW_HASKELL__
913 -- -----------------------------------------------------------------------------
914 -- List sum and product
916 {-# SPECIALISE sum :: [Int] -> Int #-}
917 {-# SPECIALISE sum :: [Integer] -> Integer #-}
918 {-# SPECIALISE product :: [Int] -> Int #-}
919 {-# SPECIALISE product :: [Integer] -> Integer #-}
920 -- | The 'sum' function computes the sum of a finite list of numbers.
921 sum :: (Num a) => [a] -> a
922 -- | The 'product' function computes the product of a finite list of numbers.
923 product :: (Num a) => [a] -> a
924 #ifdef USE_REPORT_PRELUDE
926 product = foldl (*) 1
931 sum' (x:xs) a = sum' xs (a+x)
935 prod (x:xs) a = prod xs (a*x)
938 -- -----------------------------------------------------------------------------
939 -- Functions on strings
941 -- | 'lines' breaks a string up into a list of strings at newline
942 -- characters. The resulting strings do not contain newlines.
943 lines :: String -> [String]
945 lines s = let (l, s') = break (== '\n') s
950 -- | 'unlines' is an inverse operation to 'lines'.
951 -- It joins lines, after appending a terminating newline to each.
952 unlines :: [String] -> String
953 #ifdef USE_REPORT_PRELUDE
954 unlines = concatMap (++ "\n")
956 -- HBC version (stolen)
957 -- here's a more efficient version
959 unlines (l:ls) = l ++ '\n' : unlines ls
962 -- | 'words' breaks a string up into a list of words, which were delimited
964 words :: String -> [String]
965 words s = case dropWhile {-partain:Char.-}isSpace s of
969 break {-partain:Char.-}isSpace s'
971 -- | 'unwords' is an inverse operation to 'words'.
972 -- It joins words with separating spaces.
973 unwords :: [String] -> String
974 #ifdef USE_REPORT_PRELUDE
976 unwords ws = foldr1 (\w s -> w ++ ' ':s) ws
978 -- HBC version (stolen)
979 -- here's a more efficient version
982 unwords (w:ws) = w ++ ' ' : unwords ws
985 #else /* !__GLASGOW_HASKELL__ */
987 errorEmptyList :: String -> a
989 error ("Prelude." ++ fun ++ ": empty list")
991 #endif /* !__GLASGOW_HASKELL__ */