1 {-# OPTIONS -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 , transpose -- :: [[a]] -> [[a]]
40 -- * Reducing lists (folds)
42 , foldl -- :: (a -> b -> a) -> a -> [b] -> a
43 , foldl' -- :: (a -> b -> a) -> a -> [b] -> a
44 , foldl1 -- :: (a -> a -> a) -> [a] -> a
45 , foldr -- :: (a -> b -> b) -> b -> [a] -> b
46 , foldr1 -- :: (a -> a -> a) -> [a] -> a
50 , concat -- :: [[a]] -> [a]
51 , concatMap -- :: (a -> [b]) -> [a] -> [b]
52 , and -- :: [Bool] -> Bool
53 , or -- :: [Bool] -> Bool
54 , any -- :: (a -> Bool) -> [a] -> Bool
55 , all -- :: (a -> Bool) -> [a] -> Bool
56 , sum -- :: (Num a) => [a] -> a
57 , product -- :: (Num a) => [a] -> a
58 , maximum -- :: (Ord a) => [a] -> a
59 , minimum -- :: (Ord a) => [a] -> a
64 , scanl -- :: (a -> b -> a) -> a -> [b] -> [a]
65 , scanl1 -- :: (a -> a -> a) -> [a] -> [a]
66 , scanr -- :: (a -> b -> b) -> b -> [a] -> [b]
67 , scanr1 -- :: (a -> a -> a) -> [a] -> [a]
69 -- ** Accumulating maps
70 , mapAccumL -- :: (a -> b -> (a,c)) -> a -> [b] -> (a,[c])
71 , mapAccumR -- :: (a -> b -> (a,c)) -> a -> [b] -> (a,[c])
74 , iterate -- :: (a -> a) -> a -> [a]
75 , repeat -- :: a -> [a]
76 , replicate -- :: Int -> a -> [a]
77 , cycle -- :: [a] -> [a]
80 , unfoldr -- :: (b -> Maybe (a, b)) -> b -> [a]
84 -- ** Extracting sublists
85 , take -- :: Int -> [a] -> [a]
86 , drop -- :: Int -> [a] -> [a]
87 , splitAt -- :: Int -> [a] -> ([a], [a])
89 , takeWhile -- :: (a -> Bool) -> [a] -> [a]
90 , dropWhile -- :: (a -> Bool) -> [a] -> [a]
91 , span -- :: (a -> Bool) -> [a] -> ([a], [a])
92 , break -- :: (a -> Bool) -> [a] -> ([a], [a])
94 , group -- :: Eq a => [a] -> [[a]]
96 , inits -- :: [a] -> [[a]]
97 , tails -- :: [a] -> [[a]]
100 , isPrefixOf -- :: (Eq a) => [a] -> [a] -> Bool
101 , isSuffixOf -- :: (Eq a) => [a] -> [a] -> Bool
105 -- ** Searching by equality
106 , elem -- :: a -> [a] -> Bool
107 , notElem -- :: a -> [a] -> Bool
108 , lookup -- :: (Eq a) => a -> [(a,b)] -> Maybe b
110 -- ** Searching with a predicate
111 , find -- :: (a -> Bool) -> [a] -> Maybe a
112 , filter -- :: (a -> Bool) -> [a] -> [a]
113 , partition -- :: (a -> Bool) -> [a] -> ([a], [a])
116 -- | These functions treat a list @xs@ as a indexed collection,
117 -- with indices ranging from 0 to @'length' xs - 1@.
119 , (!!) -- :: [a] -> Int -> a
121 , elemIndex -- :: (Eq a) => a -> [a] -> Maybe Int
122 , elemIndices -- :: (Eq a) => a -> [a] -> [Int]
124 , findIndex -- :: (a -> Bool) -> [a] -> Maybe Int
125 , findIndices -- :: (a -> Bool) -> [a] -> [Int]
127 -- * Zipping and unzipping lists
129 , zip -- :: [a] -> [b] -> [(a,b)]
131 , zip4, zip5, zip6, zip7
133 , zipWith -- :: (a -> b -> c) -> [a] -> [b] -> [c]
135 , zipWith4, zipWith5, zipWith6, zipWith7
137 , unzip -- :: [(a,b)] -> ([a],[b])
139 , unzip4, unzip5, unzip6, unzip7
143 -- ** Functions on strings
144 , lines -- :: String -> [String]
145 , words -- :: String -> [String]
146 , unlines -- :: [String] -> String
147 , unwords -- :: [String] -> String
149 -- ** \"Set\" operations
151 , nub -- :: (Eq a) => [a] -> [a]
153 , delete -- :: (Eq a) => a -> [a] -> [a]
154 , (\\) -- :: (Eq a) => [a] -> [a] -> [a]
156 , union -- :: (Eq a) => [a] -> [a] -> [a]
157 , intersect -- :: (Eq a) => [a] -> [a] -> [a]
160 , sort -- :: (Ord a) => [a] -> [a]
161 , insert -- :: (Ord a) => a -> [a] -> [a]
163 -- * Generalized functions
165 -- ** The \"@By@\" operations
166 -- | By convention, overloaded functions have a non-overloaded
167 -- counterpart whose name is suffixed with \`@By@\'.
169 -- *** User-supplied equality (replacing an @Eq@ context)
170 -- | The predicate is assumed to define an equivalence.
171 , nubBy -- :: (a -> a -> Bool) -> [a] -> [a]
172 , deleteBy -- :: (a -> a -> Bool) -> a -> [a] -> [a]
173 , deleteFirstsBy -- :: (a -> a -> Bool) -> [a] -> [a] -> [a]
174 , unionBy -- :: (a -> a -> Bool) -> [a] -> [a] -> [a]
175 , intersectBy -- :: (a -> a -> Bool) -> [a] -> [a] -> [a]
176 , groupBy -- :: (a -> a -> Bool) -> [a] -> [[a]]
178 -- *** User-supplied comparison (replacing an @Ord@ context)
179 -- | The function is assumed to define a total ordering.
180 , sortBy -- :: (a -> a -> Ordering) -> [a] -> [a]
181 , insertBy -- :: (a -> a -> Ordering) -> a -> [a] -> [a]
182 , maximumBy -- :: (a -> a -> Ordering) -> [a] -> a
183 , minimumBy -- :: (a -> a -> Ordering) -> [a] -> a
185 -- ** The \"@generic@\" operations
186 -- | The prefix \`@generic@\' indicates an overloaded function that
187 -- is a generalized version of a "Prelude" function.
189 , genericLength -- :: (Integral a) => [b] -> a
190 , genericTake -- :: (Integral a) => a -> [b] -> [b]
191 , genericDrop -- :: (Integral a) => a -> [b] -> [b]
192 , genericSplitAt -- :: (Integral a) => a -> [b] -> ([b], [b])
193 , genericIndex -- :: (Integral a) => [b] -> a -> b
194 , genericReplicate -- :: (Integral a) => a -> b -> [b]
199 import Prelude hiding (Maybe(..))
203 import Data.Char ( isSpace )
205 #ifdef __GLASGOW_HASKELL__
212 infix 5 \\ -- comment to fool cpp
214 -- -----------------------------------------------------------------------------
217 -- | The 'elemIndex' function returns the index of the first element
218 -- in the given list which is equal (by '==') to the query element,
219 -- or 'Nothing' if there is no such element.
220 elemIndex :: Eq a => a -> [a] -> Maybe Int
221 elemIndex x = findIndex (x==)
223 -- | The 'elemIndices' function extends 'elemIndex', by returning the
224 -- indices of all elements equal to the query element, in ascending order.
225 elemIndices :: Eq a => a -> [a] -> [Int]
226 elemIndices x = findIndices (x==)
228 -- | The 'find' function takes a predicate and a list and returns the
229 -- first element in the list matching the predicate, or 'Nothing' if
230 -- there is no such element.
231 find :: (a -> Bool) -> [a] -> Maybe a
232 find p = listToMaybe . filter p
234 -- | The 'findIndex' function takes a predicate and a list and returns
235 -- the index of the first element in the list satisfying the predicate,
236 -- or 'Nothing' if there is no such element.
237 findIndex :: (a -> Bool) -> [a] -> Maybe Int
238 findIndex p = listToMaybe . findIndices p
240 -- | The 'findIndices' function extends 'findIndex', by returning the
241 -- indices of all elements satisfying the predicate, in ascending order.
242 findIndices :: (a -> Bool) -> [a] -> [Int]
244 #if defined(USE_REPORT_PRELUDE) || !defined(__GLASGOW_HASKELL__)
245 findIndices p xs = [ i | (x,i) <- zip xs [0..], p x]
247 -- Efficient definition
248 findIndices p ls = loop 0# ls
251 loop n (x:xs) | p x = I# n : loop (n +# 1#) xs
252 | otherwise = loop (n +# 1#) xs
253 #endif /* USE_REPORT_PRELUDE */
255 -- | The 'isPrefixOf' function takes two lists and returns 'True'
256 -- iff the first list is a prefix of the second.
257 isPrefixOf :: (Eq a) => [a] -> [a] -> Bool
258 isPrefixOf [] _ = True
259 isPrefixOf _ [] = False
260 isPrefixOf (x:xs) (y:ys)= x == y && isPrefixOf xs ys
262 -- | The 'isSuffixOf' function takes two lists and returns 'True'
263 -- iff the first list is a suffix of the second.
264 -- Both lists must be finite.
265 isSuffixOf :: (Eq a) => [a] -> [a] -> Bool
266 isSuffixOf x y = reverse x `isPrefixOf` reverse y
268 -- | The 'nub' function removes duplicate elements from a list.
269 -- In particular, it keeps only the first occurrence of each element.
270 -- (The name 'nub' means \`essence\'.)
271 -- It is a special case of 'nubBy', which allows the programmer to supply
272 -- their own equality test.
273 nub :: (Eq a) => [a] -> [a]
274 #ifdef USE_REPORT_PRELUDE
278 nub l = nub' l [] -- '
282 | x `elem` ls = nub' xs ls -- '
283 | otherwise = x : nub' xs (x:ls) -- '
286 -- | The 'nubBy' function behaves just like 'nub', except it uses a
287 -- user-supplied equality predicate instead of the overloaded '=='
289 nubBy :: (a -> a -> Bool) -> [a] -> [a]
290 #ifdef USE_REPORT_PRELUDE
292 nubBy eq (x:xs) = x : nubBy eq (filter (\ y -> not (eq x y)) xs)
294 nubBy eq l = nubBy' l []
298 | elem_by eq y xs = nubBy' ys xs
299 | otherwise = y : nubBy' ys (y:xs)
302 -- Note that we keep the call to `eq` with arguments in the
303 -- same order as in the reference implementation
304 -- 'xs' is the list of things we've seen so far,
305 -- 'y' is the potential new element
306 elem_by :: (a -> a -> Bool) -> a -> [a] -> Bool
307 elem_by _ _ [] = False
308 elem_by eq y (x:xs) = x `eq` y || elem_by eq y xs
312 -- | 'delete' @x@ removes the first occurrence of @x@ from its list argument.
315 -- > delete 'a' "banana" == "bnana"
317 -- It is a special case of 'deleteBy', which allows the programmer to
318 -- supply their own equality test.
320 delete :: (Eq a) => a -> [a] -> [a]
321 delete = deleteBy (==)
323 -- | The 'deleteBy' function behaves like 'delete', but takes a
324 -- user-supplied equality predicate.
325 deleteBy :: (a -> a -> Bool) -> a -> [a] -> [a]
327 deleteBy eq x (y:ys) = if x `eq` y then ys else y : deleteBy eq x ys
329 -- | The '\\' function is list difference ((non-associative).
330 -- In the result of @xs@ '\\' @ys@, the first occurrence of each element of
331 -- @ys@ in turn (if any) has been removed from @xs@. Thus
333 -- > (xs ++ ys) \\ xs == ys.
335 -- It is a special case of 'deleteFirstsBy', which allows the programmer
336 -- to supply their own equality test.
338 (\\) :: (Eq a) => [a] -> [a] -> [a]
339 (\\) = foldl (flip delete)
341 -- | The 'union' function returns the list union of the two lists.
344 -- > "dog" `union` "cow" == "dogcw"
346 -- Duplicates, and elements of the first list, are removed from the
347 -- the second list, but if the first list contains duplicates, so will
349 -- It is a special case of 'unionBy', which allows the programmer to supply
350 -- their own equality test.
352 union :: (Eq a) => [a] -> [a] -> [a]
355 -- | The 'unionBy' function is the non-overloaded version of 'union'.
356 unionBy :: (a -> a -> Bool) -> [a] -> [a] -> [a]
357 unionBy eq xs ys = xs ++ foldl (flip (deleteBy eq)) (nubBy eq ys) xs
359 -- | The 'intersect' function takes the list intersection of two lists.
362 -- > [1,2,3,4] `intersect` [2,4,6,8] == [2,4]
364 -- If the first list contains duplicates, so will the result.
365 -- It is a special case of 'intersectBy', which allows the programmer to
366 -- supply their own equality test.
368 intersect :: (Eq a) => [a] -> [a] -> [a]
369 intersect = intersectBy (==)
371 -- | The 'intersectBy' function is the non-overloaded version of 'intersect'.
372 intersectBy :: (a -> a -> Bool) -> [a] -> [a] -> [a]
373 intersectBy eq xs ys = [x | x <- xs, any (eq x) ys]
375 -- | The 'intersperse' function takes an element and a list and
376 -- \`intersperses\' that element between the elements of the list.
379 -- > intersperse ',' "abcde" == "a,b,c,d,e"
381 intersperse :: a -> [a] -> [a]
382 intersperse _ [] = []
383 intersperse _ [x] = [x]
384 intersperse sep (x:xs) = x : sep : intersperse sep xs
386 -- | The 'transpose' function transposes the rows and columns of its argument.
389 -- > transpose [[1,2,3],[4,5,6]] == [[1,4],[2,5],[3,6]]
391 transpose :: [[a]] -> [[a]]
393 transpose ([] : xss) = transpose xss
394 transpose ((x:xs) : xss) = (x : [h | (h:t) <- xss]) : transpose (xs : [ t | (h:t) <- xss])
397 -- | The 'partition' function takes a predicate a list and returns
398 -- the pair of lists of elements which do and do not satisfy the
399 -- predicate, respectively; i.e.,
401 -- > partition p xs == (filter p xs, filter (not . p) xs)
403 partition :: (a -> Bool) -> [a] -> ([a],[a])
404 {-# INLINE partition #-}
405 partition p xs = foldr (select p) ([],[]) xs
407 select p x ~(ts,fs) | p x = (x:ts,fs)
408 | otherwise = (ts, x:fs)
410 -- | The 'mapAccumL' function behaves like a combination of 'map' and
411 -- 'foldl'; it applies a function to each element of a list, passing
412 -- an accumulating parameter from left to right, and returning a final
413 -- value of this accumulator together with the new list.
414 mapAccumL :: (acc -> x -> (acc, y)) -- Function of elt of input list
415 -- and accumulator, returning new
416 -- accumulator and elt of result list
417 -> acc -- Initial accumulator
419 -> (acc, [y]) -- Final accumulator and result list
420 mapAccumL _ s [] = (s, [])
421 mapAccumL f s (x:xs) = (s'',y:ys)
422 where (s', y ) = f s x
423 (s'',ys) = mapAccumL f s' xs
425 -- | The 'mapAccumR' function behaves like a combination of 'map' and
426 -- 'foldr'; it applies a function to each element of a list, passing
427 -- an accumulating parameter from right to left, and returning a final
428 -- value of this accumulator together with the new list.
429 mapAccumR :: (acc -> x -> (acc, y)) -- Function of elt of input list
430 -- and accumulator, returning new
431 -- accumulator and elt of result list
432 -> acc -- Initial accumulator
434 -> (acc, [y]) -- Final accumulator and result list
435 mapAccumR _ s [] = (s, [])
436 mapAccumR f s (x:xs) = (s'', y:ys)
437 where (s'',y ) = f s' x
438 (s', ys) = mapAccumR f s xs
440 -- | The 'insert' function takes an element and a list and inserts the
441 -- element into the list at the last position where it is still less
442 -- than or equal to the next element. In particular, if the list
443 -- is sorted before the call, the result will also be sorted.
444 -- It is a special case of 'insertBy', which allows the programmer to
445 -- supply their own comparison function.
446 insert :: Ord a => a -> [a] -> [a]
447 insert e ls = insertBy (compare) e ls
449 -- | The non-overloaded version of 'insert'.
450 insertBy :: (a -> a -> Ordering) -> a -> [a] -> [a]
451 insertBy _ x [] = [x]
452 insertBy cmp x ys@(y:ys')
454 GT -> y : insertBy cmp x ys'
457 -- | 'maximum' returns the maximum value from a list,
458 -- which must be non-empty, finite, and of an ordered type.
459 -- It is a special case of 'Data.List.maximumBy', which allows the
460 -- programmer to supply their own comparison function.
461 maximum :: (Ord a) => [a] -> a
462 maximum [] = errorEmptyList "maximum"
463 maximum xs = foldl1 max xs
465 {-# RULES "maximumInt" maximum = maximumInt #-}
467 -- We can't make the overloaded version of maximum strict without
468 -- changing its semantics (max might not be strict), but we can for
469 -- the version specialised to 'Int'.
470 maximumInt :: [Int] -> Int
471 maximumInt [] = errorEmptyList "maximum"
472 maximumInt xs = foldl1' max xs
474 -- | 'minimum' returns the minimum value from a list,
475 -- which must be non-empty, finite, and of an ordered type.
476 -- It is a special case of 'Data.List.minimumBy', which allows the
477 -- programmer to supply their own comparison function.
478 minimum :: (Ord a) => [a] -> a
479 minimum [] = errorEmptyList "minimum"
480 minimum xs = foldl1 min xs
482 {-# RULES "minimumInt" minimum = minimumInt #-}
484 minimumInt :: [Int] -> Int
485 minimumInt [] = errorEmptyList "minimum"
486 minimumInt xs = foldl1' min xs
488 -- | The 'maximumBy' function takes a comparison function and a list
489 -- and returns the greatest element of the list by the comparison function.
490 -- The list must be finite and non-empty.
491 maximumBy :: (a -> a -> Ordering) -> [a] -> a
492 maximumBy _ [] = error "List.maximumBy: empty list"
493 maximumBy cmp xs = foldl1 max xs
495 max x y = case cmp x y of
499 -- | The 'minimumBy' function takes a comparison function and a list
500 -- and returns the least element of the list by the comparison function.
501 -- The list must be finite and non-empty.
502 minimumBy :: (a -> a -> Ordering) -> [a] -> a
503 minimumBy _ [] = error "List.minimumBy: empty list"
504 minimumBy cmp xs = foldl1 min xs
506 min x y = case cmp x y of
510 -- | The 'genericLength' function is an overloaded version of 'length'. In
511 -- particular, instead of returning an 'Int', it returns any type which is
512 -- an instance of 'Num'. It is, however, less efficient than 'length'.
513 genericLength :: (Num i) => [b] -> i
515 genericLength (_:l) = 1 + genericLength l
517 -- | The 'genericTake' function is an overloaded version of 'take', which
518 -- accepts any 'Integral' value as the number of elements to take.
519 genericTake :: (Integral i) => i -> [a] -> [a]
521 genericTake _ [] = []
522 genericTake n (x:xs) | n > 0 = x : genericTake (n-1) xs
523 genericTake _ _ = error "List.genericTake: negative argument"
525 -- | The 'genericDrop' function is an overloaded version of 'drop', which
526 -- accepts any 'Integral' value as the number of elements to drop.
527 genericDrop :: (Integral i) => i -> [a] -> [a]
528 genericDrop 0 xs = xs
529 genericDrop _ [] = []
530 genericDrop n (_:xs) | n > 0 = genericDrop (n-1) xs
531 genericDrop _ _ = error "List.genericDrop: negative argument"
533 -- | The 'genericSplitAt' function is an overloaded version of 'splitAt', which
534 -- accepts any 'Integral' value as the position at which to split.
535 genericSplitAt :: (Integral i) => i -> [b] -> ([b],[b])
536 genericSplitAt 0 xs = ([],xs)
537 genericSplitAt _ [] = ([],[])
538 genericSplitAt n (x:xs) | n > 0 = (x:xs',xs'') where
539 (xs',xs'') = genericSplitAt (n-1) xs
540 genericSplitAt _ _ = error "List.genericSplitAt: negative argument"
542 -- | The 'genericIndex' function is an overloaded version of '!!', which
543 -- accepts any 'Integral' value as the index.
544 genericIndex :: (Integral a) => [b] -> a -> b
545 genericIndex (x:_) 0 = x
546 genericIndex (_:xs) n
547 | n > 0 = genericIndex xs (n-1)
548 | otherwise = error "List.genericIndex: negative argument."
549 genericIndex _ _ = error "List.genericIndex: index too large."
551 -- | The 'genericReplicate' function is an overloaded version of 'replicate',
552 -- which accepts any 'Integral' value as the number of repetitions to make.
553 genericReplicate :: (Integral i) => i -> a -> [a]
554 genericReplicate n x = genericTake n (repeat x)
556 -- | The 'zip4' function takes four lists and returns a list of
557 -- quadruples, analogous to 'zip'.
558 zip4 :: [a] -> [b] -> [c] -> [d] -> [(a,b,c,d)]
559 zip4 = zipWith4 (,,,)
561 -- | The 'zip5' function takes five lists and returns a list of
562 -- five-tuples, analogous to 'zip'.
563 zip5 :: [a] -> [b] -> [c] -> [d] -> [e] -> [(a,b,c,d,e)]
564 zip5 = zipWith5 (,,,,)
566 -- | The 'zip6' function takes six lists and returns a list of six-tuples,
567 -- analogous to 'zip'.
568 zip6 :: [a] -> [b] -> [c] -> [d] -> [e] -> [f] ->
570 zip6 = zipWith6 (,,,,,)
572 -- | The 'zip7' function takes seven lists and returns a list of
573 -- seven-tuples, analogous to 'zip'.
574 zip7 :: [a] -> [b] -> [c] -> [d] -> [e] -> [f] ->
575 [g] -> [(a,b,c,d,e,f,g)]
576 zip7 = zipWith7 (,,,,,,)
578 -- | The 'zipWith4' function takes a function which combines four
579 -- elements, as well as four lists and returns a list of their point-wise
580 -- combination, analogous to 'zipWith'.
581 zipWith4 :: (a->b->c->d->e) -> [a]->[b]->[c]->[d]->[e]
582 zipWith4 z (a:as) (b:bs) (c:cs) (d:ds)
583 = z a b c d : zipWith4 z as bs cs ds
584 zipWith4 _ _ _ _ _ = []
586 -- | The 'zipWith5' function takes a function which combines five
587 -- elements, as well as five lists and returns a list of their point-wise
588 -- combination, analogous to 'zipWith'.
589 zipWith5 :: (a->b->c->d->e->f) ->
590 [a]->[b]->[c]->[d]->[e]->[f]
591 zipWith5 z (a:as) (b:bs) (c:cs) (d:ds) (e:es)
592 = z a b c d e : zipWith5 z as bs cs ds es
593 zipWith5 _ _ _ _ _ _ = []
595 -- | The 'zipWith6' function takes a function which combines six
596 -- elements, as well as six lists and returns a list of their point-wise
597 -- combination, analogous to 'zipWith'.
598 zipWith6 :: (a->b->c->d->e->f->g) ->
599 [a]->[b]->[c]->[d]->[e]->[f]->[g]
600 zipWith6 z (a:as) (b:bs) (c:cs) (d:ds) (e:es) (f:fs)
601 = z a b c d e f : zipWith6 z as bs cs ds es fs
602 zipWith6 _ _ _ _ _ _ _ = []
604 -- | The 'zipWith7' function takes a function which combines seven
605 -- elements, as well as seven lists and returns a list of their point-wise
606 -- combination, analogous to 'zipWith'.
607 zipWith7 :: (a->b->c->d->e->f->g->h) ->
608 [a]->[b]->[c]->[d]->[e]->[f]->[g]->[h]
609 zipWith7 z (a:as) (b:bs) (c:cs) (d:ds) (e:es) (f:fs) (g:gs)
610 = z a b c d e f g : zipWith7 z as bs cs ds es fs gs
611 zipWith7 _ _ _ _ _ _ _ _ = []
613 -- | The 'unzip4' function takes a list of quadruples and returns four
614 -- lists, analogous to 'unzip'.
615 unzip4 :: [(a,b,c,d)] -> ([a],[b],[c],[d])
616 unzip4 = foldr (\(a,b,c,d) ~(as,bs,cs,ds) ->
617 (a:as,b:bs,c:cs,d:ds))
620 -- | The 'unzip5' function takes a list of five-tuples and returns five
621 -- lists, analogous to 'unzip'.
622 unzip5 :: [(a,b,c,d,e)] -> ([a],[b],[c],[d],[e])
623 unzip5 = foldr (\(a,b,c,d,e) ~(as,bs,cs,ds,es) ->
624 (a:as,b:bs,c:cs,d:ds,e:es))
627 -- | The 'unzip6' function takes a list of six-tuples and returns six
628 -- lists, analogous to 'unzip'.
629 unzip6 :: [(a,b,c,d,e,f)] -> ([a],[b],[c],[d],[e],[f])
630 unzip6 = foldr (\(a,b,c,d,e,f) ~(as,bs,cs,ds,es,fs) ->
631 (a:as,b:bs,c:cs,d:ds,e:es,f:fs))
634 -- | The 'unzip7' function takes a list of seven-tuples and returns
635 -- seven lists, analogous to 'unzip'.
636 unzip7 :: [(a,b,c,d,e,f,g)] -> ([a],[b],[c],[d],[e],[f],[g])
637 unzip7 = foldr (\(a,b,c,d,e,f,g) ~(as,bs,cs,ds,es,fs,gs) ->
638 (a:as,b:bs,c:cs,d:ds,e:es,f:fs,g:gs))
639 ([],[],[],[],[],[],[])
642 -- | The 'deleteFirstsBy' function takes a predicate and two lists and
643 -- returns the first list with the first occurrence of each element of
644 -- the second list removed.
645 deleteFirstsBy :: (a -> a -> Bool) -> [a] -> [a] -> [a]
646 deleteFirstsBy eq = foldl (flip (deleteBy eq))
648 -- | The 'group' function takes a list and returns a list of lists such
649 -- that the concatenation of the result is equal to the argument. Moreover,
650 -- each sublist in the result contains only equal elements. For example,
652 -- > group "Mississippi" = ["M","i","ss","i","ss","i","pp","i"]
654 -- It is a special case of 'groupBy', which allows the programmer to supply
655 -- their own equality test.
656 group :: Eq a => [a] -> [[a]]
659 -- | The 'groupBy' function is the non-overloaded version of 'group'.
660 groupBy :: (a -> a -> Bool) -> [a] -> [[a]]
662 groupBy eq (x:xs) = (x:ys) : groupBy eq zs
663 where (ys,zs) = span (eq x) xs
665 -- | The 'inits' function returns all initial segments of the argument,
666 -- shortest first. For example,
668 -- > inits "abc" == ["","a","ab","abc"]
670 inits :: [a] -> [[a]]
672 inits (x:xs) = [[]] ++ map (x:) (inits xs)
674 -- | The 'tails' function returns all final segments of the argument,
675 -- longest first. For example,
677 -- > tails "abc" == ["abc", "bc", "c",""]
679 tails :: [a] -> [[a]]
681 tails xxs@(_:xs) = xxs : tails xs
684 ------------------------------------------------------------------------------
685 -- Quick Sort algorithm taken from HBC's QSort library.
687 -- | The 'sort' function implements a stable sorting algorithm.
688 -- It is a special case of 'sortBy', which allows the programmer to supply
689 -- their own comparison function.
690 sort :: (Ord a) => [a] -> [a]
692 -- | The 'sortBy' function is the non-overloaded version of 'sort'.
693 sortBy :: (a -> a -> Ordering) -> [a] -> [a]
695 #ifdef USE_REPORT_PRELUDE
696 sort = sortBy compare
697 sortBy cmp = foldr (insertBy cmp) []
700 sortBy cmp l = mergesort cmp l
701 sort l = mergesort compare l
704 Quicksort replaced by mergesort, 14/5/2002.
706 From: Ian Lynagh <igloo@earth.li>
708 I am curious as to why the List.sort implementation in GHC is a
709 quicksort algorithm rather than an algorithm that guarantees n log n
710 time in the worst case? I have attached a mergesort implementation along
711 with a few scripts to time it's performance, the results of which are
712 shown below (* means it didn't finish successfully - in all cases this
713 was due to a stack overflow).
715 If I heap profile the random_list case with only 10000 then I see
716 random_list peaks at using about 2.5M of memory, whereas in the same
717 program using List.sort it uses only 100k.
719 Input style Input length Sort data Sort alg User time
720 stdin 10000 random_list sort 2.82
721 stdin 10000 random_list mergesort 2.96
722 stdin 10000 sorted sort 31.37
723 stdin 10000 sorted mergesort 1.90
724 stdin 10000 revsorted sort 31.21
725 stdin 10000 revsorted mergesort 1.88
726 stdin 100000 random_list sort *
727 stdin 100000 random_list mergesort *
728 stdin 100000 sorted sort *
729 stdin 100000 sorted mergesort *
730 stdin 100000 revsorted sort *
731 stdin 100000 revsorted mergesort *
732 func 10000 random_list sort 0.31
733 func 10000 random_list mergesort 0.91
734 func 10000 sorted sort 19.09
735 func 10000 sorted mergesort 0.15
736 func 10000 revsorted sort 19.17
737 func 10000 revsorted mergesort 0.16
738 func 100000 random_list sort 3.85
739 func 100000 random_list mergesort *
740 func 100000 sorted sort 5831.47
741 func 100000 sorted mergesort 2.23
742 func 100000 revsorted sort 5872.34
743 func 100000 revsorted mergesort 2.24
746 mergesort :: (a -> a -> Ordering) -> [a] -> [a]
747 mergesort cmp = mergesort' cmp . map wrap
749 mergesort' :: (a -> a -> Ordering) -> [[a]] -> [a]
750 mergesort' cmp [] = []
751 mergesort' cmp [xs] = xs
752 mergesort' cmp xss = mergesort' cmp (merge_pairs cmp xss)
754 merge_pairs :: (a -> a -> Ordering) -> [[a]] -> [[a]]
755 merge_pairs cmp [] = []
756 merge_pairs cmp [xs] = [xs]
757 merge_pairs cmp (xs:ys:xss) = merge cmp xs ys : merge_pairs cmp xss
759 merge :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
762 merge cmp (x:xs) (y:ys)
764 GT -> y : merge cmp (x:xs) ys
765 _ -> x : merge cmp xs (y:ys)
773 -- qsort is stable and does not concatenate.
774 qsort :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
777 qsort cmp (x:xs) r = qpart cmp x xs [] [] r
779 -- qpart partitions and sorts the sublists
780 qpart :: (a -> a -> Ordering) -> a -> [a] -> [a] -> [a] -> [a] -> [a]
781 qpart cmp x [] rlt rge r =
782 -- rlt and rge are in reverse order and must be sorted with an
783 -- anti-stable sorting
784 rqsort cmp rlt (x:rqsort cmp rge r)
785 qpart cmp x (y:ys) rlt rge r =
787 GT -> qpart cmp x ys (y:rlt) rge r
788 _ -> qpart cmp x ys rlt (y:rge) r
790 -- rqsort is as qsort but anti-stable, i.e. reverses equal elements
791 rqsort :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
794 rqsort cmp (x:xs) r = rqpart cmp x xs [] [] r
796 rqpart :: (a -> a -> Ordering) -> a -> [a] -> [a] -> [a] -> [a] -> [a]
797 rqpart cmp x [] rle rgt r =
798 qsort cmp rle (x:qsort cmp rgt r)
799 rqpart cmp x (y:ys) rle rgt r =
801 GT -> rqpart cmp x ys rle (y:rgt) r
802 _ -> rqpart cmp x ys (y:rle) rgt r
805 #endif /* USE_REPORT_PRELUDE */
807 -- | The 'unfoldr' function is a \`dual\' to 'foldr': while 'foldr'
808 -- reduces a list to a summary value, 'unfoldr' builds a list from
809 -- a seed value. The function takes the element and returns 'Nothing'
810 -- if it is done producing the list or returns 'Just' @(a,b)@, in which
811 -- case, @a@ is a prepended to the list and @b@ is used as the next
812 -- element in a recursive call. For example,
814 -- > iterate f == unfoldr (\x -> Just (x, f x))
816 -- In some cases, 'unfoldr' can undo a 'foldr' operation:
818 -- > unfoldr f' (foldr f z xs) == xs
820 -- if the following holds:
822 -- > f' (f x y) = Just (x,y)
825 unfoldr :: (b -> Maybe (a, b)) -> b -> [a]
828 Just (a,new_b) -> a : unfoldr f new_b
831 -- -----------------------------------------------------------------------------
833 -- | A strict version of 'foldl'.
834 foldl' :: (a -> b -> a) -> a -> [b] -> a
836 foldl' f a (x:xs) = let a' = f a x in a' `seq` foldl' f a' xs
838 -- | 'foldl1' is a variant of 'foldl' that has no starting value argument,
839 -- and thus must be applied to non-empty lists.
840 foldl1 :: (a -> a -> a) -> [a] -> a
841 foldl1 f (x:xs) = foldl f x xs
842 foldl1 _ [] = errorEmptyList "foldl1"
844 -- | A strict version of 'foldl1'
845 foldl1' :: (a -> a -> a) -> [a] -> a
846 foldl1' f (x:xs) = foldl' f x xs
847 foldl1' _ [] = errorEmptyList "foldl1'"
849 #ifdef __GLASGOW_HASKELL__
850 -- -----------------------------------------------------------------------------
851 -- List sum and product
853 {-# SPECIALISE sum :: [Int] -> Int #-}
854 {-# SPECIALISE sum :: [Integer] -> Integer #-}
855 {-# SPECIALISE product :: [Int] -> Int #-}
856 {-# SPECIALISE product :: [Integer] -> Integer #-}
857 -- | The 'sum' function computes the sum of a finite list of numbers.
858 sum :: (Num a) => [a] -> a
859 -- | The 'product' function computes the product of a finite list of numbers.
860 product :: (Num a) => [a] -> a
861 #ifdef USE_REPORT_PRELUDE
863 product = foldl (*) 1
868 sum' (x:xs) a = sum' xs (a+x)
872 prod (x:xs) a = prod xs (a*x)
875 -- -----------------------------------------------------------------------------
876 -- Functions on strings
878 -- | 'lines' breaks a string up into a list of strings at newline
879 -- characters. The resulting strings do not contain newlines.
880 lines :: String -> [String]
882 lines s = let (l, s') = break (== '\n') s
887 -- | 'unlines' is an inverse operation to 'lines'.
888 -- It joins lines, after appending a terminating newline to each.
889 unlines :: [String] -> String
890 #ifdef USE_REPORT_PRELUDE
891 unlines = concatMap (++ "\n")
893 -- HBC version (stolen)
894 -- here's a more efficient version
896 unlines (l:ls) = l ++ '\n' : unlines ls
899 -- | 'words' breaks a string up into a list of words, which were delimited
901 words :: String -> [String]
902 words s = case dropWhile {-partain:Char.-}isSpace s of
906 break {-partain:Char.-}isSpace s'
908 -- | 'unwords' is an inverse operation to 'words'.
909 -- It joins words with separating spaces.
910 unwords :: [String] -> String
911 #ifdef USE_REPORT_PRELUDE
913 unwords ws = foldr1 (\w s -> w ++ ' ':s) ws
915 -- HBC version (stolen)
916 -- here's a more efficient version
919 unwords (w:ws) = w ++ ' ' : unwords ws
921 #endif /* __GLASGOW_HASKELL__ */