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