Add intercalate to Data.List (ticket #971)
[packages/base.git] / Data / List.hs
1 {-# OPTIONS_GHC -fno-implicit-prelude #-}
2 -----------------------------------------------------------------------------
3 -- |
4 -- Module : Data.List
5 -- Copyright : (c) The University of Glasgow 2001
6 -- License : BSD-style (see the file libraries/base/LICENSE)
7 --
8 -- Maintainer : libraries@haskell.org
9 -- Stability : stable
10 -- Portability : portable
11 --
12 -- Operations on lists.
13 --
14 -----------------------------------------------------------------------------
15
16 module Data.List
17 (
18 #ifdef __NHC__
19 [] (..)
20 ,
21 #endif
22
23 -- * Basic functions
24
25 (++) -- :: [a] -> [a] -> [a]
26 , head -- :: [a] -> a
27 , last -- :: [a] -> a
28 , tail -- :: [a] -> [a]
29 , init -- :: [a] -> [a]
30 , null -- :: [a] -> Bool
31 , length -- :: [a] -> Int
32
33 -- * List transformations
34 , map -- :: (a -> b) -> [a] -> [b]
35 , reverse -- :: [a] -> [a]
36
37 , intersperse -- :: a -> [a] -> [a]
38 , intercalate -- :: [a] -> [[a]] -> [a]
39 , transpose -- :: [[a]] -> [[a]]
40
41 -- * Reducing lists (folds)
42
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
49
50 -- ** Special folds
51
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
62
63 -- * Building lists
64
65 -- ** Scans
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]
70
71 -- ** Accumulating maps
72 , mapAccumL -- :: (a -> b -> (a,c)) -> a -> [b] -> (a,[c])
73 , mapAccumR -- :: (a -> b -> (a,c)) -> a -> [b] -> (a,[c])
74
75 -- ** Infinite lists
76 , iterate -- :: (a -> a) -> a -> [a]
77 , repeat -- :: a -> [a]
78 , replicate -- :: Int -> a -> [a]
79 , cycle -- :: [a] -> [a]
80
81 -- ** Unfolding
82 , unfoldr -- :: (b -> Maybe (a, b)) -> b -> [a]
83
84 -- * Sublists
85
86 -- ** Extracting sublists
87 , take -- :: Int -> [a] -> [a]
88 , drop -- :: Int -> [a] -> [a]
89 , splitAt -- :: Int -> [a] -> ([a], [a])
90
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])
95
96 , group -- :: Eq a => [a] -> [[a]]
97
98 , inits -- :: [a] -> [[a]]
99 , tails -- :: [a] -> [[a]]
100
101 -- ** Predicates
102 , isPrefixOf -- :: (Eq a) => [a] -> [a] -> Bool
103 , isSuffixOf -- :: (Eq a) => [a] -> [a] -> Bool
104 , isInfixOf -- :: (Eq a) => [a] -> [a] -> Bool
105
106 -- * Searching lists
107
108 -- ** Searching by equality
109 , elem -- :: a -> [a] -> Bool
110 , notElem -- :: a -> [a] -> Bool
111 , lookup -- :: (Eq a) => a -> [(a,b)] -> Maybe b
112
113 -- ** Searching with a predicate
114 , find -- :: (a -> Bool) -> [a] -> Maybe a
115 , filter -- :: (a -> Bool) -> [a] -> [a]
116 , partition -- :: (a -> Bool) -> [a] -> ([a], [a])
117
118 -- * Indexing lists
119 -- | These functions treat a list @xs@ as a indexed collection,
120 -- with indices ranging from 0 to @'length' xs - 1@.
121
122 , (!!) -- :: [a] -> Int -> a
123
124 , elemIndex -- :: (Eq a) => a -> [a] -> Maybe Int
125 , elemIndices -- :: (Eq a) => a -> [a] -> [Int]
126
127 , findIndex -- :: (a -> Bool) -> [a] -> Maybe Int
128 , findIndices -- :: (a -> Bool) -> [a] -> [Int]
129
130 -- * Zipping and unzipping lists
131
132 , zip -- :: [a] -> [b] -> [(a,b)]
133 , zip3
134 , zip4, zip5, zip6, zip7
135
136 , zipWith -- :: (a -> b -> c) -> [a] -> [b] -> [c]
137 , zipWith3
138 , zipWith4, zipWith5, zipWith6, zipWith7
139
140 , unzip -- :: [(a,b)] -> ([a],[b])
141 , unzip3
142 , unzip4, unzip5, unzip6, unzip7
143
144 -- * Special lists
145
146 -- ** Functions on strings
147 , lines -- :: String -> [String]
148 , words -- :: String -> [String]
149 , unlines -- :: [String] -> String
150 , unwords -- :: [String] -> String
151
152 -- ** \"Set\" operations
153
154 , nub -- :: (Eq a) => [a] -> [a]
155
156 , delete -- :: (Eq a) => a -> [a] -> [a]
157 , (\\) -- :: (Eq a) => [a] -> [a] -> [a]
158
159 , union -- :: (Eq a) => [a] -> [a] -> [a]
160 , intersect -- :: (Eq a) => [a] -> [a] -> [a]
161
162 -- ** Ordered lists
163 , sort -- :: (Ord a) => [a] -> [a]
164 , insert -- :: (Ord a) => a -> [a] -> [a]
165
166 -- * Generalized functions
167
168 -- ** The \"@By@\" operations
169 -- | By convention, overloaded functions have a non-overloaded
170 -- counterpart whose name is suffixed with \`@By@\'.
171
172 -- *** User-supplied equality (replacing an @Eq@ context)
173 -- | The predicate is assumed to define an equivalence.
174 , nubBy -- :: (a -> a -> Bool) -> [a] -> [a]
175 , deleteBy -- :: (a -> a -> Bool) -> a -> [a] -> [a]
176 , deleteFirstsBy -- :: (a -> a -> Bool) -> [a] -> [a] -> [a]
177 , unionBy -- :: (a -> a -> Bool) -> [a] -> [a] -> [a]
178 , intersectBy -- :: (a -> a -> Bool) -> [a] -> [a] -> [a]
179 , groupBy -- :: (a -> a -> Bool) -> [a] -> [[a]]
180
181 -- *** User-supplied comparison (replacing an @Ord@ context)
182 -- | The function is assumed to define a total ordering.
183 , sortBy -- :: (a -> a -> Ordering) -> [a] -> [a]
184 , insertBy -- :: (a -> a -> Ordering) -> a -> [a] -> [a]
185 , maximumBy -- :: (a -> a -> Ordering) -> [a] -> a
186 , minimumBy -- :: (a -> a -> Ordering) -> [a] -> a
187
188 -- ** The \"@generic@\" operations
189 -- | The prefix \`@generic@\' indicates an overloaded function that
190 -- is a generalized version of a "Prelude" function.
191
192 , genericLength -- :: (Integral a) => [b] -> a
193 , genericTake -- :: (Integral a) => a -> [b] -> [b]
194 , genericDrop -- :: (Integral a) => a -> [b] -> [b]
195 , genericSplitAt -- :: (Integral a) => a -> [b] -> ([b], [b])
196 , genericIndex -- :: (Integral a) => [b] -> a -> b
197 , genericReplicate -- :: (Integral a) => a -> b -> [b]
198
199 ) where
200
201 #ifdef __NHC__
202 import Prelude hiding (Maybe(..))
203 #endif
204
205 import Data.Maybe
206 import Data.Char ( isSpace )
207
208 #ifdef __GLASGOW_HASKELL__
209 import GHC.Num
210 import GHC.Real
211 import GHC.List
212 import GHC.Base
213 #endif
214
215 infix 5 \\ -- comment to fool cpp
216
217 -- -----------------------------------------------------------------------------
218 -- List functions
219
220 -- | The 'elemIndex' function returns the index of the first element
221 -- in the given list which is equal (by '==') to the query element,
222 -- or 'Nothing' if there is no such element.
223 elemIndex :: Eq a => a -> [a] -> Maybe Int
224 elemIndex x = findIndex (x==)
225
226 -- | The 'elemIndices' function extends 'elemIndex', by returning the
227 -- indices of all elements equal to the query element, in ascending order.
228 elemIndices :: Eq a => a -> [a] -> [Int]
229 elemIndices x = findIndices (x==)
230
231 -- | The 'find' function takes a predicate and a list and returns the
232 -- first element in the list matching the predicate, or 'Nothing' if
233 -- there is no such element.
234 find :: (a -> Bool) -> [a] -> Maybe a
235 find p = listToMaybe . filter p
236
237 -- | The 'findIndex' function takes a predicate and a list and returns
238 -- the index of the first element in the list satisfying the predicate,
239 -- or 'Nothing' if there is no such element.
240 findIndex :: (a -> Bool) -> [a] -> Maybe Int
241 findIndex p = listToMaybe . findIndices p
242
243 -- | The 'findIndices' function extends 'findIndex', by returning the
244 -- indices of all elements satisfying the predicate, in ascending order.
245 findIndices :: (a -> Bool) -> [a] -> [Int]
246
247 #if defined(USE_REPORT_PRELUDE) || !defined(__GLASGOW_HASKELL__)
248 findIndices p xs = [ i | (x,i) <- zip xs [0..], p x]
249 #else
250 -- Efficient definition
251 findIndices p ls = loop 0# ls
252 where
253 loop _ [] = []
254 loop n (x:xs) | p x = I# n : loop (n +# 1#) xs
255 | otherwise = loop (n +# 1#) xs
256 #endif /* USE_REPORT_PRELUDE */
257
258 -- | The 'isPrefixOf' function takes two lists and returns 'True'
259 -- iff the first list is a prefix of the second.
260 isPrefixOf :: (Eq a) => [a] -> [a] -> Bool
261 isPrefixOf [] _ = True
262 isPrefixOf _ [] = False
263 isPrefixOf (x:xs) (y:ys)= x == y && isPrefixOf xs ys
264
265 -- | The 'isSuffixOf' function takes two lists and returns 'True'
266 -- iff the first list is a suffix of the second.
267 -- Both lists must be finite.
268 isSuffixOf :: (Eq a) => [a] -> [a] -> Bool
269 isSuffixOf x y = reverse x `isPrefixOf` reverse y
270
271 -- | The 'isInfixOf' function takes two lists and returns 'True'
272 -- iff the first list is contained, wholly and intact,
273 -- anywhere within the second.
274 --
275 -- Example:
276 --
277 -- >isInfixOf "Haskell" "I really like Haskell." -> True
278 -- >isInfixOf "Ial" "I really like Haskell." -> False
279 isInfixOf :: (Eq a) => [a] -> [a] -> Bool
280 isInfixOf needle haystack = any (isPrefixOf needle) (tails haystack)
281
282 -- | The 'nub' function removes duplicate elements from a list.
283 -- In particular, it keeps only the first occurrence of each element.
284 -- (The name 'nub' means \`essence\'.)
285 -- It is a special case of 'nubBy', which allows the programmer to supply
286 -- their own equality test.
287 nub :: (Eq a) => [a] -> [a]
288 #ifdef USE_REPORT_PRELUDE
289 nub = nubBy (==)
290 #else
291 -- stolen from HBC
292 nub l = nub' l [] -- '
293 where
294 nub' [] _ = [] -- '
295 nub' (x:xs) ls -- '
296 | x `elem` ls = nub' xs ls -- '
297 | otherwise = x : nub' xs (x:ls) -- '
298 #endif
299
300 -- | The 'nubBy' function behaves just like 'nub', except it uses a
301 -- user-supplied equality predicate instead of the overloaded '=='
302 -- function.
303 nubBy :: (a -> a -> Bool) -> [a] -> [a]
304 #ifdef USE_REPORT_PRELUDE
305 nubBy eq [] = []
306 nubBy eq (x:xs) = x : nubBy eq (filter (\ y -> not (eq x y)) xs)
307 #else
308 nubBy eq l = nubBy' l []
309 where
310 nubBy' [] _ = []
311 nubBy' (y:ys) xs
312 | elem_by eq y xs = nubBy' ys xs
313 | otherwise = y : nubBy' ys (y:xs)
314
315 -- Not exported:
316 -- Note that we keep the call to `eq` with arguments in the
317 -- same order as in the reference implementation
318 -- 'xs' is the list of things we've seen so far,
319 -- 'y' is the potential new element
320 elem_by :: (a -> a -> Bool) -> a -> [a] -> Bool
321 elem_by _ _ [] = False
322 elem_by eq y (x:xs) = x `eq` y || elem_by eq y xs
323 #endif
324
325
326 -- | 'delete' @x@ removes the first occurrence of @x@ from its list argument.
327 -- For example,
328 --
329 -- > delete 'a' "banana" == "bnana"
330 --
331 -- It is a special case of 'deleteBy', which allows the programmer to
332 -- supply their own equality test.
333
334 delete :: (Eq a) => a -> [a] -> [a]
335 delete = deleteBy (==)
336
337 -- | The 'deleteBy' function behaves like 'delete', but takes a
338 -- user-supplied equality predicate.
339 deleteBy :: (a -> a -> Bool) -> a -> [a] -> [a]
340 deleteBy _ _ [] = []
341 deleteBy eq x (y:ys) = if x `eq` y then ys else y : deleteBy eq x ys
342
343 -- | The '\\' function is list difference ((non-associative).
344 -- In the result of @xs@ '\\' @ys@, the first occurrence of each element of
345 -- @ys@ in turn (if any) has been removed from @xs@. Thus
346 --
347 -- > (xs ++ ys) \\ xs == ys.
348 --
349 -- It is a special case of 'deleteFirstsBy', which allows the programmer
350 -- to supply their own equality test.
351
352 (\\) :: (Eq a) => [a] -> [a] -> [a]
353 (\\) = foldl (flip delete)
354
355 -- | The 'union' function returns the list union of the two lists.
356 -- For example,
357 --
358 -- > "dog" `union` "cow" == "dogcw"
359 --
360 -- Duplicates, and elements of the first list, are removed from the
361 -- the second list, but if the first list contains duplicates, so will
362 -- the result.
363 -- It is a special case of 'unionBy', which allows the programmer to supply
364 -- their own equality test.
365
366 union :: (Eq a) => [a] -> [a] -> [a]
367 union = unionBy (==)
368
369 -- | The 'unionBy' function is the non-overloaded version of 'union'.
370 unionBy :: (a -> a -> Bool) -> [a] -> [a] -> [a]
371 unionBy eq xs ys = xs ++ foldl (flip (deleteBy eq)) (nubBy eq ys) xs
372
373 -- | The 'intersect' function takes the list intersection of two lists.
374 -- For example,
375 --
376 -- > [1,2,3,4] `intersect` [2,4,6,8] == [2,4]
377 --
378 -- If the first list contains duplicates, so will the result.
379 -- It is a special case of 'intersectBy', which allows the programmer to
380 -- supply their own equality test.
381
382 intersect :: (Eq a) => [a] -> [a] -> [a]
383 intersect = intersectBy (==)
384
385 -- | The 'intersectBy' function is the non-overloaded version of 'intersect'.
386 intersectBy :: (a -> a -> Bool) -> [a] -> [a] -> [a]
387 intersectBy eq xs ys = [x | x <- xs, any (eq x) ys]
388
389 -- | The 'intersperse' function takes an element and a list and
390 -- \`intersperses\' that element between the elements of the list.
391 -- For example,
392 --
393 -- > intersperse ',' "abcde" == "a,b,c,d,e"
394
395 intersperse :: a -> [a] -> [a]
396 intersperse _ [] = []
397 intersperse _ [x] = [x]
398 intersperse sep (x:xs) = x : sep : intersperse sep xs
399
400 -- | 'intercalate' @xs xss@ is equivalent to @('concat' ('intersperse' xs xss))@.
401 -- It inserts the list @xs@ in between the lists in @xss@ and concatenates the
402 -- result.
403 intercalate :: [a] -> [[a]] -> [a]
404 intercalate xs xss = concat (intersperse xs xss)
405
406 -- | The 'transpose' function transposes the rows and columns of its argument.
407 -- For example,
408 --
409 -- > transpose [[1,2,3],[4,5,6]] == [[1,4],[2,5],[3,6]]
410
411 transpose :: [[a]] -> [[a]]
412 transpose [] = []
413 transpose ([] : xss) = transpose xss
414 transpose ((x:xs) : xss) = (x : [h | (h:t) <- xss]) : transpose (xs : [ t | (h:t) <- xss])
415
416
417 -- | The 'partition' function takes a predicate a list and returns
418 -- the pair of lists of elements which do and do not satisfy the
419 -- predicate, respectively; i.e.,
420 --
421 -- > partition p xs == (filter p xs, filter (not . p) xs)
422
423 partition :: (a -> Bool) -> [a] -> ([a],[a])
424 {-# INLINE partition #-}
425 partition p xs = foldr (select p) ([],[]) xs
426
427 select p x ~(ts,fs) | p x = (x:ts,fs)
428 | otherwise = (ts, x:fs)
429
430 -- | The 'mapAccumL' function behaves like a combination of 'map' and
431 -- 'foldl'; it applies a function to each element of a list, passing
432 -- an accumulating parameter from left to right, and returning a final
433 -- value of this accumulator together with the new list.
434 mapAccumL :: (acc -> x -> (acc, y)) -- Function of elt of input list
435 -- and accumulator, returning new
436 -- accumulator and elt of result list
437 -> acc -- Initial accumulator
438 -> [x] -- Input list
439 -> (acc, [y]) -- Final accumulator and result list
440 mapAccumL _ s [] = (s, [])
441 mapAccumL f s (x:xs) = (s'',y:ys)
442 where (s', y ) = f s x
443 (s'',ys) = mapAccumL f s' xs
444
445 -- | The 'mapAccumR' function behaves like a combination of 'map' and
446 -- 'foldr'; it applies a function to each element of a list, passing
447 -- an accumulating parameter from right to left, and returning a final
448 -- value of this accumulator together with the new list.
449 mapAccumR :: (acc -> x -> (acc, y)) -- Function of elt of input list
450 -- and accumulator, returning new
451 -- accumulator and elt of result list
452 -> acc -- Initial accumulator
453 -> [x] -- Input list
454 -> (acc, [y]) -- Final accumulator and result list
455 mapAccumR _ s [] = (s, [])
456 mapAccumR f s (x:xs) = (s'', y:ys)
457 where (s'',y ) = f s' x
458 (s', ys) = mapAccumR f s xs
459
460 -- | The 'insert' function takes an element and a list and inserts the
461 -- element into the list at the last position where it is still less
462 -- than or equal to the next element. In particular, if the list
463 -- is sorted before the call, the result will also be sorted.
464 -- It is a special case of 'insertBy', which allows the programmer to
465 -- supply their own comparison function.
466 insert :: Ord a => a -> [a] -> [a]
467 insert e ls = insertBy (compare) e ls
468
469 -- | The non-overloaded version of 'insert'.
470 insertBy :: (a -> a -> Ordering) -> a -> [a] -> [a]
471 insertBy _ x [] = [x]
472 insertBy cmp x ys@(y:ys')
473 = case cmp x y of
474 GT -> y : insertBy cmp x ys'
475 _ -> x : ys
476
477 #ifdef __GLASGOW_HASKELL__
478
479 -- | 'maximum' returns the maximum value from a list,
480 -- which must be non-empty, finite, and of an ordered type.
481 -- It is a special case of 'Data.List.maximumBy', which allows the
482 -- programmer to supply their own comparison function.
483 maximum :: (Ord a) => [a] -> a
484 maximum [] = errorEmptyList "maximum"
485 maximum xs = foldl1 max xs
486
487 {-# RULES
488 "maximumInt" maximum = (strictMaximum :: [Int] -> Int);
489 "maximumInteger" maximum = (strictMaximum :: [Integer] -> Integer)
490 #-}
491
492 -- We can't make the overloaded version of maximum strict without
493 -- changing its semantics (max might not be strict), but we can for
494 -- the version specialised to 'Int'.
495 strictMaximum :: (Ord a) => [a] -> a
496 strictMaximum [] = errorEmptyList "maximum"
497 strictMaximum xs = foldl1' max xs
498
499 -- | 'minimum' returns the minimum 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.minimumBy', which allows the
502 -- programmer to supply their own comparison function.
503 minimum :: (Ord a) => [a] -> a
504 minimum [] = errorEmptyList "minimum"
505 minimum xs = foldl1 min xs
506
507 {-# RULES
508 "minimumInt" minimum = (strictMinimum :: [Int] -> Int);
509 "minimumInteger" minimum = (strictMinimum :: [Integer] -> Integer)
510 #-}
511
512 strictMinimum :: (Ord a) => [a] -> a
513 strictMinimum [] = errorEmptyList "minimum"
514 strictMinimum xs = foldl1' min xs
515
516 #endif /* __GLASGOW_HASKELL__ */
517
518 -- | The 'maximumBy' function takes a comparison function and a list
519 -- and returns the greatest element of the list by the comparison function.
520 -- The list must be finite and non-empty.
521 maximumBy :: (a -> a -> Ordering) -> [a] -> a
522 maximumBy _ [] = error "List.maximumBy: empty list"
523 maximumBy cmp xs = foldl1 max xs
524 where
525 max x y = case cmp x y of
526 GT -> x
527 _ -> y
528
529 -- | The 'minimumBy' function takes a comparison function and a list
530 -- and returns the least element of the list by the comparison function.
531 -- The list must be finite and non-empty.
532 minimumBy :: (a -> a -> Ordering) -> [a] -> a
533 minimumBy _ [] = error "List.minimumBy: empty list"
534 minimumBy cmp xs = foldl1 min xs
535 where
536 min x y = case cmp x y of
537 GT -> y
538 _ -> x
539
540 -- | The 'genericLength' function is an overloaded version of 'length'. In
541 -- particular, instead of returning an 'Int', it returns any type which is
542 -- an instance of 'Num'. It is, however, less efficient than 'length'.
543 genericLength :: (Num i) => [b] -> i
544 genericLength [] = 0
545 genericLength (_:l) = 1 + genericLength l
546
547 -- | The 'genericTake' function is an overloaded version of 'take', which
548 -- accepts any 'Integral' value as the number of elements to take.
549 genericTake :: (Integral i) => i -> [a] -> [a]
550 genericTake 0 _ = []
551 genericTake _ [] = []
552 genericTake n (x:xs) | n > 0 = x : genericTake (n-1) xs
553 genericTake _ _ = error "List.genericTake: negative argument"
554
555 -- | The 'genericDrop' function is an overloaded version of 'drop', which
556 -- accepts any 'Integral' value as the number of elements to drop.
557 genericDrop :: (Integral i) => i -> [a] -> [a]
558 genericDrop 0 xs = xs
559 genericDrop _ [] = []
560 genericDrop n (_:xs) | n > 0 = genericDrop (n-1) xs
561 genericDrop _ _ = error "List.genericDrop: negative argument"
562
563 -- | The 'genericSplitAt' function is an overloaded version of 'splitAt', which
564 -- accepts any 'Integral' value as the position at which to split.
565 genericSplitAt :: (Integral i) => i -> [b] -> ([b],[b])
566 genericSplitAt 0 xs = ([],xs)
567 genericSplitAt _ [] = ([],[])
568 genericSplitAt n (x:xs) | n > 0 = (x:xs',xs'') where
569 (xs',xs'') = genericSplitAt (n-1) xs
570 genericSplitAt _ _ = error "List.genericSplitAt: negative argument"
571
572 -- | The 'genericIndex' function is an overloaded version of '!!', which
573 -- accepts any 'Integral' value as the index.
574 genericIndex :: (Integral a) => [b] -> a -> b
575 genericIndex (x:_) 0 = x
576 genericIndex (_:xs) n
577 | n > 0 = genericIndex xs (n-1)
578 | otherwise = error "List.genericIndex: negative argument."
579 genericIndex _ _ = error "List.genericIndex: index too large."
580
581 -- | The 'genericReplicate' function is an overloaded version of 'replicate',
582 -- which accepts any 'Integral' value as the number of repetitions to make.
583 genericReplicate :: (Integral i) => i -> a -> [a]
584 genericReplicate n x = genericTake n (repeat x)
585
586 -- | The 'zip4' function takes four lists and returns a list of
587 -- quadruples, analogous to 'zip'.
588 zip4 :: [a] -> [b] -> [c] -> [d] -> [(a,b,c,d)]
589 zip4 = zipWith4 (,,,)
590
591 -- | The 'zip5' function takes five lists and returns a list of
592 -- five-tuples, analogous to 'zip'.
593 zip5 :: [a] -> [b] -> [c] -> [d] -> [e] -> [(a,b,c,d,e)]
594 zip5 = zipWith5 (,,,,)
595
596 -- | The 'zip6' function takes six lists and returns a list of six-tuples,
597 -- analogous to 'zip'.
598 zip6 :: [a] -> [b] -> [c] -> [d] -> [e] -> [f] ->
599 [(a,b,c,d,e,f)]
600 zip6 = zipWith6 (,,,,,)
601
602 -- | The 'zip7' function takes seven lists and returns a list of
603 -- seven-tuples, analogous to 'zip'.
604 zip7 :: [a] -> [b] -> [c] -> [d] -> [e] -> [f] ->
605 [g] -> [(a,b,c,d,e,f,g)]
606 zip7 = zipWith7 (,,,,,,)
607
608 -- | The 'zipWith4' function takes a function which combines four
609 -- elements, as well as four lists and returns a list of their point-wise
610 -- combination, analogous to 'zipWith'.
611 zipWith4 :: (a->b->c->d->e) -> [a]->[b]->[c]->[d]->[e]
612 zipWith4 z (a:as) (b:bs) (c:cs) (d:ds)
613 = z a b c d : zipWith4 z as bs cs ds
614 zipWith4 _ _ _ _ _ = []
615
616 -- | The 'zipWith5' function takes a function which combines five
617 -- elements, as well as five lists and returns a list of their point-wise
618 -- combination, analogous to 'zipWith'.
619 zipWith5 :: (a->b->c->d->e->f) ->
620 [a]->[b]->[c]->[d]->[e]->[f]
621 zipWith5 z (a:as) (b:bs) (c:cs) (d:ds) (e:es)
622 = z a b c d e : zipWith5 z as bs cs ds es
623 zipWith5 _ _ _ _ _ _ = []
624
625 -- | The 'zipWith6' function takes a function which combines six
626 -- elements, as well as six lists and returns a list of their point-wise
627 -- combination, analogous to 'zipWith'.
628 zipWith6 :: (a->b->c->d->e->f->g) ->
629 [a]->[b]->[c]->[d]->[e]->[f]->[g]
630 zipWith6 z (a:as) (b:bs) (c:cs) (d:ds) (e:es) (f:fs)
631 = z a b c d e f : zipWith6 z as bs cs ds es fs
632 zipWith6 _ _ _ _ _ _ _ = []
633
634 -- | The 'zipWith7' function takes a function which combines seven
635 -- elements, as well as seven lists and returns a list of their point-wise
636 -- combination, analogous to 'zipWith'.
637 zipWith7 :: (a->b->c->d->e->f->g->h) ->
638 [a]->[b]->[c]->[d]->[e]->[f]->[g]->[h]
639 zipWith7 z (a:as) (b:bs) (c:cs) (d:ds) (e:es) (f:fs) (g:gs)
640 = z a b c d e f g : zipWith7 z as bs cs ds es fs gs
641 zipWith7 _ _ _ _ _ _ _ _ = []
642
643 -- | The 'unzip4' function takes a list of quadruples and returns four
644 -- lists, analogous to 'unzip'.
645 unzip4 :: [(a,b,c,d)] -> ([a],[b],[c],[d])
646 unzip4 = foldr (\(a,b,c,d) ~(as,bs,cs,ds) ->
647 (a:as,b:bs,c:cs,d:ds))
648 ([],[],[],[])
649
650 -- | The 'unzip5' function takes a list of five-tuples and returns five
651 -- lists, analogous to 'unzip'.
652 unzip5 :: [(a,b,c,d,e)] -> ([a],[b],[c],[d],[e])
653 unzip5 = foldr (\(a,b,c,d,e) ~(as,bs,cs,ds,es) ->
654 (a:as,b:bs,c:cs,d:ds,e:es))
655 ([],[],[],[],[])
656
657 -- | The 'unzip6' function takes a list of six-tuples and returns six
658 -- lists, analogous to 'unzip'.
659 unzip6 :: [(a,b,c,d,e,f)] -> ([a],[b],[c],[d],[e],[f])
660 unzip6 = foldr (\(a,b,c,d,e,f) ~(as,bs,cs,ds,es,fs) ->
661 (a:as,b:bs,c:cs,d:ds,e:es,f:fs))
662 ([],[],[],[],[],[])
663
664 -- | The 'unzip7' function takes a list of seven-tuples and returns
665 -- seven lists, analogous to 'unzip'.
666 unzip7 :: [(a,b,c,d,e,f,g)] -> ([a],[b],[c],[d],[e],[f],[g])
667 unzip7 = foldr (\(a,b,c,d,e,f,g) ~(as,bs,cs,ds,es,fs,gs) ->
668 (a:as,b:bs,c:cs,d:ds,e:es,f:fs,g:gs))
669 ([],[],[],[],[],[],[])
670
671
672 -- | The 'deleteFirstsBy' function takes a predicate and two lists and
673 -- returns the first list with the first occurrence of each element of
674 -- the second list removed.
675 deleteFirstsBy :: (a -> a -> Bool) -> [a] -> [a] -> [a]
676 deleteFirstsBy eq = foldl (flip (deleteBy eq))
677
678 -- | The 'group' function takes a list and returns a list of lists such
679 -- that the concatenation of the result is equal to the argument. Moreover,
680 -- each sublist in the result contains only equal elements. For example,
681 --
682 -- > group "Mississippi" = ["M","i","ss","i","ss","i","pp","i"]
683 --
684 -- It is a special case of 'groupBy', which allows the programmer to supply
685 -- their own equality test.
686 group :: Eq a => [a] -> [[a]]
687 group = groupBy (==)
688
689 -- | The 'groupBy' function is the non-overloaded version of 'group'.
690 groupBy :: (a -> a -> Bool) -> [a] -> [[a]]
691 groupBy _ [] = []
692 groupBy eq (x:xs) = (x:ys) : groupBy eq zs
693 where (ys,zs) = span (eq x) xs
694
695 -- | The 'inits' function returns all initial segments of the argument,
696 -- shortest first. For example,
697 --
698 -- > inits "abc" == ["","a","ab","abc"]
699 --
700 inits :: [a] -> [[a]]
701 inits [] = [[]]
702 inits (x:xs) = [[]] ++ map (x:) (inits xs)
703
704 -- | The 'tails' function returns all final segments of the argument,
705 -- longest first. For example,
706 --
707 -- > tails "abc" == ["abc", "bc", "c",""]
708 --
709 tails :: [a] -> [[a]]
710 tails [] = [[]]
711 tails xxs@(_:xs) = xxs : tails xs
712
713
714 ------------------------------------------------------------------------------
715 -- Quick Sort algorithm taken from HBC's QSort library.
716
717 -- | The 'sort' function implements a stable sorting algorithm.
718 -- It is a special case of 'sortBy', which allows the programmer to supply
719 -- their own comparison function.
720 sort :: (Ord a) => [a] -> [a]
721
722 -- | The 'sortBy' function is the non-overloaded version of 'sort'.
723 sortBy :: (a -> a -> Ordering) -> [a] -> [a]
724
725 #ifdef USE_REPORT_PRELUDE
726 sort = sortBy compare
727 sortBy cmp = foldr (insertBy cmp) []
728 #else
729
730 sortBy cmp l = mergesort cmp l
731 sort l = mergesort compare l
732
733 {-
734 Quicksort replaced by mergesort, 14/5/2002.
735
736 From: Ian Lynagh <igloo@earth.li>
737
738 I am curious as to why the List.sort implementation in GHC is a
739 quicksort algorithm rather than an algorithm that guarantees n log n
740 time in the worst case? I have attached a mergesort implementation along
741 with a few scripts to time it's performance, the results of which are
742 shown below (* means it didn't finish successfully - in all cases this
743 was due to a stack overflow).
744
745 If I heap profile the random_list case with only 10000 then I see
746 random_list peaks at using about 2.5M of memory, whereas in the same
747 program using List.sort it uses only 100k.
748
749 Input style Input length Sort data Sort alg User time
750 stdin 10000 random_list sort 2.82
751 stdin 10000 random_list mergesort 2.96
752 stdin 10000 sorted sort 31.37
753 stdin 10000 sorted mergesort 1.90
754 stdin 10000 revsorted sort 31.21
755 stdin 10000 revsorted mergesort 1.88
756 stdin 100000 random_list sort *
757 stdin 100000 random_list mergesort *
758 stdin 100000 sorted sort *
759 stdin 100000 sorted mergesort *
760 stdin 100000 revsorted sort *
761 stdin 100000 revsorted mergesort *
762 func 10000 random_list sort 0.31
763 func 10000 random_list mergesort 0.91
764 func 10000 sorted sort 19.09
765 func 10000 sorted mergesort 0.15
766 func 10000 revsorted sort 19.17
767 func 10000 revsorted mergesort 0.16
768 func 100000 random_list sort 3.85
769 func 100000 random_list mergesort *
770 func 100000 sorted sort 5831.47
771 func 100000 sorted mergesort 2.23
772 func 100000 revsorted sort 5872.34
773 func 100000 revsorted mergesort 2.24
774 -}
775
776 mergesort :: (a -> a -> Ordering) -> [a] -> [a]
777 mergesort cmp = mergesort' cmp . map wrap
778
779 mergesort' :: (a -> a -> Ordering) -> [[a]] -> [a]
780 mergesort' cmp [] = []
781 mergesort' cmp [xs] = xs
782 mergesort' cmp xss = mergesort' cmp (merge_pairs cmp xss)
783
784 merge_pairs :: (a -> a -> Ordering) -> [[a]] -> [[a]]
785 merge_pairs cmp [] = []
786 merge_pairs cmp [xs] = [xs]
787 merge_pairs cmp (xs:ys:xss) = merge cmp xs ys : merge_pairs cmp xss
788
789 merge :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
790 merge cmp xs [] = xs
791 merge cmp [] ys = ys
792 merge cmp (x:xs) (y:ys)
793 = case x `cmp` y of
794 GT -> y : merge cmp (x:xs) ys
795 _ -> x : merge cmp xs (y:ys)
796
797 wrap :: a -> [a]
798 wrap x = [x]
799
800 {-
801 OLD: qsort version
802
803 -- qsort is stable and does not concatenate.
804 qsort :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
805 qsort _ [] r = r
806 qsort _ [x] r = x:r
807 qsort cmp (x:xs) r = qpart cmp x xs [] [] r
808
809 -- qpart partitions and sorts the sublists
810 qpart :: (a -> a -> Ordering) -> a -> [a] -> [a] -> [a] -> [a] -> [a]
811 qpart cmp x [] rlt rge r =
812 -- rlt and rge are in reverse order and must be sorted with an
813 -- anti-stable sorting
814 rqsort cmp rlt (x:rqsort cmp rge r)
815 qpart cmp x (y:ys) rlt rge r =
816 case cmp x y of
817 GT -> qpart cmp x ys (y:rlt) rge r
818 _ -> qpart cmp x ys rlt (y:rge) r
819
820 -- rqsort is as qsort but anti-stable, i.e. reverses equal elements
821 rqsort :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
822 rqsort _ [] r = r
823 rqsort _ [x] r = x:r
824 rqsort cmp (x:xs) r = rqpart cmp x xs [] [] r
825
826 rqpart :: (a -> a -> Ordering) -> a -> [a] -> [a] -> [a] -> [a] -> [a]
827 rqpart cmp x [] rle rgt r =
828 qsort cmp rle (x:qsort cmp rgt r)
829 rqpart cmp x (y:ys) rle rgt r =
830 case cmp y x of
831 GT -> rqpart cmp x ys rle (y:rgt) r
832 _ -> rqpart cmp x ys (y:rle) rgt r
833 -}
834
835 #endif /* USE_REPORT_PRELUDE */
836
837 -- | The 'unfoldr' function is a \`dual\' to 'foldr': while 'foldr'
838 -- reduces a list to a summary value, 'unfoldr' builds a list from
839 -- a seed value. The function takes the element and returns 'Nothing'
840 -- if it is done producing the list or returns 'Just' @(a,b)@, in which
841 -- case, @a@ is a prepended to the list and @b@ is used as the next
842 -- element in a recursive call. For example,
843 --
844 -- > iterate f == unfoldr (\x -> Just (x, f x))
845 --
846 -- In some cases, 'unfoldr' can undo a 'foldr' operation:
847 --
848 -- > unfoldr f' (foldr f z xs) == xs
849 --
850 -- if the following holds:
851 --
852 -- > f' (f x y) = Just (x,y)
853 -- > f' z = Nothing
854
855 unfoldr :: (b -> Maybe (a, b)) -> b -> [a]
856 unfoldr f b =
857 case f b of
858 Just (a,new_b) -> a : unfoldr f new_b
859 Nothing -> []
860
861 -- -----------------------------------------------------------------------------
862
863 -- | A strict version of 'foldl'.
864 foldl' :: (a -> b -> a) -> a -> [b] -> a
865 foldl' f a [] = a
866 foldl' f a (x:xs) = let a' = f a x in a' `seq` foldl' f a' xs
867
868 #ifdef __GLASGOW_HASKELL__
869 -- | 'foldl1' is a variant of 'foldl' that has no starting value argument,
870 -- and thus must be applied to non-empty lists.
871 foldl1 :: (a -> a -> a) -> [a] -> a
872 foldl1 f (x:xs) = foldl f x xs
873 foldl1 _ [] = errorEmptyList "foldl1"
874 #endif /* __GLASGOW_HASKELL__ */
875
876 -- | A strict version of 'foldl1'
877 foldl1' :: (a -> a -> a) -> [a] -> a
878 foldl1' f (x:xs) = foldl' f x xs
879 foldl1' _ [] = errorEmptyList "foldl1'"
880
881 #ifdef __GLASGOW_HASKELL__
882 -- -----------------------------------------------------------------------------
883 -- List sum and product
884
885 {-# SPECIALISE sum :: [Int] -> Int #-}
886 {-# SPECIALISE sum :: [Integer] -> Integer #-}
887 {-# SPECIALISE product :: [Int] -> Int #-}
888 {-# SPECIALISE product :: [Integer] -> Integer #-}
889 -- | The 'sum' function computes the sum of a finite list of numbers.
890 sum :: (Num a) => [a] -> a
891 -- | The 'product' function computes the product of a finite list of numbers.
892 product :: (Num a) => [a] -> a
893 #ifdef USE_REPORT_PRELUDE
894 sum = foldl (+) 0
895 product = foldl (*) 1
896 #else
897 sum l = sum' l 0
898 where
899 sum' [] a = a
900 sum' (x:xs) a = sum' xs (a+x)
901 product l = prod l 1
902 where
903 prod [] a = a
904 prod (x:xs) a = prod xs (a*x)
905 #endif
906
907 -- -----------------------------------------------------------------------------
908 -- Functions on strings
909
910 -- | 'lines' breaks a string up into a list of strings at newline
911 -- characters. The resulting strings do not contain newlines.
912 lines :: String -> [String]
913 lines "" = []
914 lines s = let (l, s') = break (== '\n') s
915 in l : case s' of
916 [] -> []
917 (_:s'') -> lines s''
918
919 -- | 'unlines' is an inverse operation to 'lines'.
920 -- It joins lines, after appending a terminating newline to each.
921 unlines :: [String] -> String
922 #ifdef USE_REPORT_PRELUDE
923 unlines = concatMap (++ "\n")
924 #else
925 -- HBC version (stolen)
926 -- here's a more efficient version
927 unlines [] = []
928 unlines (l:ls) = l ++ '\n' : unlines ls
929 #endif
930
931 -- | 'words' breaks a string up into a list of words, which were delimited
932 -- by white space.
933 words :: String -> [String]
934 words s = case dropWhile {-partain:Char.-}isSpace s of
935 "" -> []
936 s' -> w : words s''
937 where (w, s'') =
938 break {-partain:Char.-}isSpace s'
939
940 -- | 'unwords' is an inverse operation to 'words'.
941 -- It joins words with separating spaces.
942 unwords :: [String] -> String
943 #ifdef USE_REPORT_PRELUDE
944 unwords [] = ""
945 unwords ws = foldr1 (\w s -> w ++ ' ':s) ws
946 #else
947 -- HBC version (stolen)
948 -- here's a more efficient version
949 unwords [] = ""
950 unwords [w] = w
951 unwords (w:ws) = w ++ ' ' : unwords ws
952 #endif
953
954 #else /* !__GLASGOW_HASKELL__ */
955
956 errorEmptyList :: String -> a
957 errorEmptyList fun =
958 error ("Prelude." ++ fun ++ ": empty list")
959
960 #endif /* !__GLASGOW_HASKELL__ */