1 {-# OPTIONS -fno-implicit-prelude #-}
2 -----------------------------------------------------------------------------
3 -- |
4 -- Module : Data.List
5 -- Copyright : (c) The University of Glasgow 2001
7 --
9 -- Stability : provisional
10 -- Portability : portable
11 --
12 -- Operations on lists.
13 --
14 -----------------------------------------------------------------------------
16 module Data.List
17 (
18 #ifdef __NHC__
19 [] (..)
20 ,
21 #endif
22 elemIndex -- :: (Eq a) => a -> [a] -> Maybe Int
23 , elemIndices -- :: (Eq a) => a -> [a] -> [Int]
25 , find -- :: (a -> Bool) -> [a] -> Maybe a
26 , findIndex -- :: (a -> Bool) -> [a] -> Maybe Int
27 , findIndices -- :: (a -> Bool) -> [a] -> [Int]
29 , nub -- :: (Eq a) => [a] -> [a]
30 , nubBy -- :: (a -> a -> Bool) -> [a] -> [a]
32 , delete -- :: (Eq a) => a -> [a] -> [a]
33 , deleteBy -- :: (a -> a -> Bool) -> a -> [a] -> [a]
34 , (\\) -- :: (Eq a) => [a] -> [a] -> [a]
35 , deleteFirstsBy -- :: (a -> a -> Bool) -> [a] -> [a] -> [a]
37 , union -- :: (Eq a) => [a] -> [a] -> [a]
38 , unionBy -- :: (a -> a -> Bool) -> [a] -> [a] -> [a]
40 , intersect -- :: (Eq a) => [a] -> [a] -> [a]
41 , intersectBy -- :: (a -> a -> Bool) -> [a] -> [a] -> [a]
43 , intersperse -- :: a -> [a] -> [a]
44 , transpose -- :: [[a]] -> [[a]]
45 , partition -- :: (a -> Bool) -> [a] -> ([a], [a])
47 , group -- :: Eq a => [a] -> [[a]]
48 , groupBy -- :: (a -> a -> Bool) -> [a] -> [[a]]
50 , inits -- :: [a] -> [[a]]
51 , tails -- :: [a] -> [[a]]
53 , isPrefixOf -- :: (Eq a) => [a] -> [a] -> Bool
54 , isSuffixOf -- :: (Eq a) => [a] -> [a] -> Bool
56 , mapAccumL -- :: (a -> b -> (a,c)) -> a -> [b] -> (a,[c])
57 , mapAccumR -- :: (a -> b -> (a,c)) -> a -> [b] -> (a,[c])
59 , sort -- :: (Ord a) => [a] -> [a]
60 , sortBy -- :: (a -> a -> Ordering) -> [a] -> [a]
62 , insert -- :: (Ord a) => a -> [a] -> [a]
63 , insertBy -- :: (a -> a -> Ordering) -> a -> [a] -> [a]
65 , maximumBy -- :: (a -> a -> Ordering) -> [a] -> a
66 , minimumBy -- :: (a -> a -> Ordering) -> [a] -> a
68 , genericLength -- :: (Integral a) => [b] -> a
69 , genericTake -- :: (Integral a) => a -> [b] -> [b]
70 , genericDrop -- :: (Integral a) => a -> [b] -> [b]
71 , genericSplitAt -- :: (Integral a) => a -> [b] -> ([b], [b])
72 , genericIndex -- :: (Integral a) => [b] -> a -> b
73 , genericReplicate -- :: (Integral a) => a -> b -> [b]
75 , unfoldr -- :: (b -> Maybe (a, b)) -> b -> [a]
77 , zip4, zip5, zip6, zip7
78 , zipWith4, zipWith5, zipWith6, zipWith7
79 , unzip4, unzip5, unzip6, unzip7
81 , map -- :: ( a -> b ) -> [a] -> [b]
82 , (++) -- :: [a] -> [a] -> [a]
83 , concat -- :: [[a]] -> [a]
84 , filter -- :: (a -> Bool) -> [a] -> [a]
85 , head -- :: [a] -> a
86 , last -- :: [a] -> a
87 , tail -- :: [a] -> [a]
88 , init -- :: [a] -> [a]
89 , null -- :: [a] -> Bool
90 , length -- :: [a] -> Int
91 , (!!) -- :: [a] -> Int -> a
92 , foldl -- :: (a -> b -> a) -> a -> [b] -> a
93 , foldl' -- :: (a -> b -> a) -> a -> [b] -> a
94 , foldl1 -- :: (a -> a -> a) -> [a] -> a
95 , scanl -- :: (a -> b -> a) -> a -> [b] -> [a]
96 , scanl1 -- :: (a -> a -> a) -> [a] -> [a]
97 , foldr -- :: (a -> b -> b) -> b -> [a] -> b
98 , foldr1 -- :: (a -> a -> a) -> [a] -> a
99 , scanr -- :: (a -> b -> b) -> b -> [a] -> [b]
100 , scanr1 -- :: (a -> a -> a) -> [a] -> [a]
101 , iterate -- :: (a -> a) -> a -> [a]
102 , repeat -- :: a -> [a]
103 , replicate -- :: Int -> a -> [a]
104 , cycle -- :: [a] -> [a]
105 , take -- :: Int -> [a] -> [a]
106 , drop -- :: Int -> [a] -> [a]
107 , splitAt -- :: Int -> [a] -> ([a], [a])
108 , takeWhile -- :: (a -> Bool) -> [a] -> [a]
109 , dropWhile -- :: (a -> Bool) -> [a] -> [a]
110 , span -- :: (a -> Bool) -> [a] -> ([a], [a])
111 , break -- :: (a -> Bool) -> [a] -> ([a], [a])
113 , lines -- :: String -> [String]
114 , words -- :: String -> [String]
115 , unlines -- :: [String] -> String
116 , unwords -- :: [String] -> String
117 , reverse -- :: [a] -> [a]
118 , and -- :: [Bool] -> Bool
119 , or -- :: [Bool] -> Bool
120 , any -- :: (a -> Bool) -> [a] -> Bool
121 , all -- :: (a -> Bool) -> [a] -> Bool
122 , elem -- :: a -> [a] -> Bool
123 , notElem -- :: a -> [a] -> Bool
124 , lookup -- :: (Eq a) => a -> [(a,b)] -> Maybe b
125 , sum -- :: (Num a) => [a] -> a
126 , product -- :: (Num a) => [a] -> a
127 , maximum -- :: (Ord a) => [a] -> a
128 , minimum -- :: (Ord a) => [a] -> a
129 , concatMap -- :: (a -> [b]) -> [a] -> [b]
130 , zip -- :: [a] -> [b] -> [(a,b)]
131 , zip3
132 , zipWith -- :: (a -> b -> c) -> [a] -> [b] -> [c]
133 , zipWith3
134 , unzip -- :: [(a,b)] -> ([a],[b])
135 , unzip3
137 ) where
139 #ifdef __NHC__
140 import Prelude hiding (Maybe(..))
141 #endif
143 import Data.Maybe
144 import Data.Char ( isSpace )
147 import GHC.Num
148 import GHC.Real
149 import GHC.List
150 import GHC.Base
151 #endif
153 infix 5 \\
155 -- -----------------------------------------------------------------------------
156 -- List functions
158 -- | The 'elemIndex' function finds the first element in the given list
159 -- which is equal (by '(==)') to the query element. It returns the 0-based
160 -- index of that element. The function returns 'Nothing' if the element
162 elemIndex :: Eq a => a -> [a] -> Maybe Int
163 elemIndex x = findIndex (x==)
165 -- | The 'elemIndices' function behaves similarly to 'elemIndex', except
166 -- it returns the indices of all matching elements, not just the first.
167 elemIndices :: Eq a => a -> [a] -> [Int]
168 elemIndices x = findIndices (x==)
170 -- | The 'find' function takes a predicate and a list and returns the
171 -- first element in the list matching the predicate, or Nothing if no
172 -- such element exists.
173 find :: (a -> Bool) -> [a] -> Maybe a
174 find p = listToMaybe . filter p
176 -- | The 'findIndex' function takes a predicate and a list and returns
177 -- the index of the first elemen in the list matching the predicate, or
178 -- Nothing if no such element exists.
179 findIndex :: (a -> Bool) -> [a] -> Maybe Int
180 findIndex p = listToMaybe . findIndices p
182 -- | The 'findIndices' function behaves like 'findIndex', but returns
183 -- all matching indices.
184 findIndices :: (a -> Bool) -> [a] -> [Int]
187 findIndices p xs = [ i | (x,i) <- zip xs [0..], p x]
188 #else
189 -- Efficient definition
190 findIndices p ls = loop 0# ls
191 where
192 loop _ [] = []
193 loop n (x:xs) | p x = I# n : loop (n +# 1#) xs
194 | otherwise = loop (n +# 1#) xs
195 #endif /* USE_REPORT_PRELUDE */
197 -- | The 'isPrefixOf' function takes two lists and returns True
198 -- iff the first list is a prefix of the second.
199 isPrefixOf :: (Eq a) => [a] -> [a] -> Bool
200 isPrefixOf [] _ = True
201 isPrefixOf _ [] = False
202 isPrefixOf (x:xs) (y:ys)= x == y && isPrefixOf xs ys
204 isSuffixOf :: (Eq a) => [a] -> [a] -> Bool
205 isSuffixOf x y = reverse x isPrefixOf reverse y
207 -- nub (meaning "essence") remove duplicate elements from its list argument.
208 -- | The 'nub' function removes duplicate elements from a list. In particular,
209 -- it keeps only the first occurance of each element. (The name nub' means essence'.)
210 nub :: (Eq a) => [a] -> [a]
211 #ifdef USE_REPORT_PRELUDE
212 nub = nubBy (==)
213 #else
214 -- stolen from HBC
215 nub l = nub' l [] -- '
216 where
217 nub' [] _ = [] -- '
218 nub' (x:xs) ls -- '
219 | x elem ls = nub' xs ls -- '
220 | otherwise = x : nub' xs (x:ls) -- '
221 #endif
223 -- | The 'nubBy' function behaves just like 'nub', except it uses a
225 -- function.
226 nubBy :: (a -> a -> Bool) -> [a] -> [a]
227 #ifdef USE_REPORT_PRELUDE
228 nubBy eq [] = []
229 nubBy eq (x:xs) = x : nubBy eq (filter (\ y -> not (eq x y)) xs)
230 #else
231 nubBy eq l = nubBy' l []
232 where
233 nubBy' [] _ = []
234 nubBy' (y:ys) xs
235 | elem_by eq y xs = nubBy' ys xs
236 | otherwise = y : nubBy' ys (y:xs)
238 -- Not exported:
239 -- Note that we keep the call to eq with arguments in the
240 -- same order as in the reference implementation
241 -- 'xs' is the list of things we've seen so far,
242 -- 'y' is the potential new element
243 elem_by :: (a -> a -> Bool) -> a -> [a] -> Bool
244 elem_by _ _ [] = False
245 elem_by eq y (x:xs) = x eq y || elem_by eq y xs
246 #endif
249 -- delete x removes the first occurrence of x from its list argument.
250 -- | The 'delete' function takes an element and a list and removes the
251 -- first occurance of the elemtn from the list.
252 delete :: (Eq a) => a -> [a] -> [a]
253 delete = deleteBy (==)
255 -- | The 'deleteBy' function behaves like 'delete', but takes a
256 -- user-supplied equality predicate.
257 deleteBy :: (a -> a -> Bool) -> a -> [a] -> [a]
258 deleteBy _ _ [] = []
259 deleteBy eq x (y:ys) = if x eq y then ys else y : deleteBy eq x ys
261 -- list difference (non-associative). In the result of xs \\ ys,
262 -- the first occurrence of each element of ys in turn (if any)
263 -- has been removed from xs. Thus, (xs ++ ys) \\ xs == ys.
264 -- | The '(\\)' function is list difference. In particular, the
265 -- first occurance of each element of the second argument is
266 -- removed from the first argument (once).
267 (\\) :: (Eq a) => [a] -> [a] -> [a]
268 (\\) = foldl (flip delete)
270 -- List union, remove the elements of first list from second.
271 -- | The 'union' function returns the list union of the two lists.
272 -- If the first list contains duplicates, so will the result.
273 union :: (Eq a) => [a] -> [a] -> [a]
274 union = unionBy (==)
276 -- | The 'unionBy' function is the non-overloaded version of 'union'.
277 unionBy :: (a -> a -> Bool) -> [a] -> [a] -> [a]
278 unionBy eq xs ys = xs ++ foldl (flip (deleteBy eq)) (nubBy eq ys) xs
280 -- | The 'intersect' function takes the list intersection of two lists.
281 -- If the first list contains duplicates, so will the result.
282 intersect :: (Eq a) => [a] -> [a] -> [a]
283 intersect = intersectBy (==)
285 -- | The 'intersectBy' function is the non-overloaded version of 'intersect'.
286 intersectBy :: (a -> a -> Bool) -> [a] -> [a] -> [a]
287 intersectBy eq xs ys = [x | x <- xs, any (eq x) ys]
289 -- intersperse sep inserts sep between the elements of its list argument.
290 -- e.g. intersperse ',' "abcde" == "a,b,c,d,e"
291 -- | The 'intersperse' function takes an element and a list and intersperses'
292 -- that element between the elements of the list.
293 intersperse :: a -> [a] -> [a]
294 intersperse _ [] = []
295 intersperse _ [x] = [x]
296 intersperse sep (x:xs) = x : sep : intersperse sep xs
298 -- | The 'transpose' function performs matrix transposition on its argument.
299 transpose :: [[a]] -> [[a]]
300 transpose [] = []
301 transpose ([] : xss) = transpose xss
302 transpose ((x:xs) : xss) = (x : [h | (h:t) <- xss]) : transpose (xs : [ t | (h:t) <- xss])
305 -- partition takes a predicate and a list and returns a pair of lists:
306 -- those elements of the argument list that do and do not satisfy the
307 -- predicate, respectively; i,e,,
308 -- partition p xs == (filter p xs, filter (not . p) xs).
309 -- | The 'partition' function takes a predicate a list and returns
310 -- the pair of lists of elements which do and do not satisfy the
311 -- predicate.
312 partition :: (a -> Bool) -> [a] -> ([a],[a])
313 {-# INLINE partition #-}
314 partition p xs = foldr (select p) ([],[]) xs
316 select p x (ts,fs) | p x = (x:ts,fs)
317 | otherwise = (ts, x:fs)
319 -- @mapAccumL@ behaves like a combination
320 -- of @map@ and @foldl@;
321 -- it applies a function to each element of a list, passing an accumulating
322 -- parameter from left to right, and returning a final value of this
323 -- accumulator together with the new list.
325 -- | The 'mapAccumL' function behaves like a combination of 'map' and
326 -- 'foldl'. In particular, it applies a function to each element of alist,
327 -- passing an accumulating parameter from left to right, and returning a
328 -- final value of this accumulator together with the new list.
329 mapAccumL :: (acc -> x -> (acc, y)) -- Function of elt of input list
330 -- and accumulator, returning new
331 -- accumulator and elt of result list
332 -> acc -- Initial accumulator
333 -> [x] -- Input list
334 -> (acc, [y]) -- Final accumulator and result list
335 mapAccumL _ s [] = (s, [])
336 mapAccumL f s (x:xs) = (s'',y:ys)
337 where (s', y ) = f s x
338 (s'',ys) = mapAccumL f s' xs
340 -- @mapAccumR@ does the same, but working from right to left instead.
341 -- Its type is the same as @mapAccumL@, though.
343 -- | The 'mapAccumR' function behaves like a combination of 'map' and
344 -- 'foldr'. In particular, it applies a function to each element of alist,
345 -- passing an accumulating parameter from right to left, and returning a
346 -- final value of this accumulator together with the new list.
347 mapAccumR :: (acc -> x -> (acc, y)) -- Function of elt of input list
348 -- and accumulator, returning new
349 -- accumulator and elt of result list
350 -> acc -- Initial accumulator
351 -> [x] -- Input list
352 -> (acc, [y]) -- Final accumulator and result list
353 mapAccumR _ s [] = (s, [])
354 mapAccumR f s (x:xs) = (s'', y:ys)
355 where (s'',y ) = f s' x
356 (s', ys) = mapAccumR f s xs
358 -- | The 'insert' function takes an element and a list and inserts the
359 -- element into the list at the last position where it is still less
360 -- than or equal to the next element. In particular, if the list
361 -- is sorted before the call, the result will also be sorted.
362 insert :: Ord a => a -> [a] -> [a]
363 insert e ls = insertBy (compare) e ls
365 -- | The non-overloaded version of 'insert'.
366 insertBy :: (a -> a -> Ordering) -> a -> [a] -> [a]
367 insertBy _ x [] = [x]
368 insertBy cmp x ys@(y:ys')
369 = case cmp x y of
370 GT -> y : insertBy cmp x ys'
371 _ -> x : ys
373 -- | The 'maximumBy' function takes a comparison function and a list
374 -- and returns the greatest element of the list by the comparison function.
375 -- It is an error on an empty list.
376 maximumBy :: (a -> a -> Ordering) -> [a] -> a
377 maximumBy _ [] = error "List.maximumBy: empty list"
378 maximumBy cmp xs = foldl1 max xs
379 where
380 max x y = case cmp x y of
381 GT -> x
382 _ -> y
384 -- | The 'minimumBy' function takes a comparison function and a list
385 -- and returns the least element of the list by the comparison function.
386 -- It is an error on an empty list.
387 minimumBy :: (a -> a -> Ordering) -> [a] -> a
388 minimumBy _ [] = error "List.minimumBy: empty list"
389 minimumBy cmp xs = foldl1 min xs
390 where
391 min x y = case cmp x y of
392 GT -> y
393 _ -> x
395 -- | The 'genericLength' function is an overloaded version of 'length'. In
396 -- particular, instead of returning an Int, it returns any type which is
397 -- an instance of Num. It is, however, less efficient than 'length'.
398 genericLength :: (Num i) => [b] -> i
399 genericLength [] = 0
400 genericLength (_:l) = 1 + genericLength l
402 -- | The 'genericTake' function is an overloaded version of 'take', which
403 -- accepts any Integral value as the number of elements to take.
404 genericTake :: (Integral i) => i -> [a] -> [a]
405 genericTake 0 _ = []
406 genericTake _ [] = []
407 genericTake n (x:xs) | n > 0 = x : genericTake (n-1) xs
408 genericTake _ _ = error "List.genericTake: negative argument"
410 -- | The 'genericDrop' function is an overloaded version of 'drop', which
411 -- accepts any Integral value as the number of elements to drop.
412 genericDrop :: (Integral i) => i -> [a] -> [a]
413 genericDrop 0 xs = xs
414 genericDrop _ [] = []
415 genericDrop n (_:xs) | n > 0 = genericDrop (n-1) xs
416 genericDrop _ _ = error "List.genericDrop: negative argument"
418 -- | The 'genericSplitAt' function is an overloaded version of 'splitAt', which
419 -- accepts any Integral value as the position at which to split.
420 genericSplitAt :: (Integral i) => i -> [b] -> ([b],[b])
421 genericSplitAt 0 xs = ([],xs)
422 genericSplitAt _ [] = ([],[])
423 genericSplitAt n (x:xs) | n > 0 = (x:xs',xs'') where
424 (xs',xs'') = genericSplitAt (n-1) xs
425 genericSplitAt _ _ = error "List.genericSplitAt: negative argument"
427 -- | The 'genericIndex' function is an overloaded version of 'index', which
428 -- accepts any Integral value as the index to return.
429 genericIndex :: (Integral a) => [b] -> a -> b
430 genericIndex (x:_) 0 = x
431 genericIndex (_:xs) n
432 | n > 0 = genericIndex xs (n-1)
433 | otherwise = error "List.genericIndex: negative argument."
434 genericIndex _ _ = error "List.genericIndex: index too large."
436 -- | The 'genericReplicate' function is an overloaded version of 'replicate', which
437 -- accepts any Integral value as the number of repetitions to make.
438 genericReplicate :: (Integral i) => i -> a -> [a]
439 genericReplicate n x = genericTake n (repeat x)
441 -- | The 'zip4' function takes four lists and returns a list of quadruples, analogous to 'zip'.
442 zip4 :: [a] -> [b] -> [c] -> [d] -> [(a,b,c,d)]
443 zip4 = zipWith4 (,,,)
445 -- | The 'zip5' function takes five lists and returns a list of five-tuples, analogous to 'zip'.
446 zip5 :: [a] -> [b] -> [c] -> [d] -> [e] -> [(a,b,c,d,e)]
447 zip5 = zipWith5 (,,,,)
449 -- | The 'zip6' function takes six lists and returns a list of six-tuples, analogous to 'zip'.
450 zip6 :: [a] -> [b] -> [c] -> [d] -> [e] -> [f] ->
451 [(a,b,c,d,e,f)]
452 zip6 = zipWith6 (,,,,,)
454 -- | The 'zip7' function takes seven lists and returns a list of seven-tuples, analogous to 'zip'.
455 zip7 :: [a] -> [b] -> [c] -> [d] -> [e] -> [f] ->
456 [g] -> [(a,b,c,d,e,f,g)]
457 zip7 = zipWith7 (,,,,,,)
459 -- | The 'zipWith4' function takes a function which combines four elements, as well as four lists and returns a list of their point-wise combination, analogous to 'zipWith'.
460 zipWith4 :: (a->b->c->d->e) -> [a]->[b]->[c]->[d]->[e]
461 zipWith4 z (a:as) (b:bs) (c:cs) (d:ds)
462 = z a b c d : zipWith4 z as bs cs ds
463 zipWith4 _ _ _ _ _ = []
465 -- | The 'zipWith5' function takes a function which combines five elements, as well as five lists and returns a list of their point-wise combination, analogous to 'zipWith'.
466 zipWith5 :: (a->b->c->d->e->f) ->
467 [a]->[b]->[c]->[d]->[e]->[f]
468 zipWith5 z (a:as) (b:bs) (c:cs) (d:ds) (e:es)
469 = z a b c d e : zipWith5 z as bs cs ds es
470 zipWith5 _ _ _ _ _ _ = []
472 -- | The 'zipWith6' function takes a function which combines six elements, as well as six lists and returns a list of their point-wise combination, analogous to 'zipWith'.
473 zipWith6 :: (a->b->c->d->e->f->g) ->
474 [a]->[b]->[c]->[d]->[e]->[f]->[g]
475 zipWith6 z (a:as) (b:bs) (c:cs) (d:ds) (e:es) (f:fs)
476 = z a b c d e f : zipWith6 z as bs cs ds es fs
477 zipWith6 _ _ _ _ _ _ _ = []
479 -- | The 'zipWith7' function takes a function which combines seven elements, as well as seven lists and returns a list of their point-wise combination, analogous to 'zipWith'.
480 zipWith7 :: (a->b->c->d->e->f->g->h) ->
481 [a]->[b]->[c]->[d]->[e]->[f]->[g]->[h]
482 zipWith7 z (a:as) (b:bs) (c:cs) (d:ds) (e:es) (f:fs) (g:gs)
483 = z a b c d e f g : zipWith7 z as bs cs ds es fs gs
484 zipWith7 _ _ _ _ _ _ _ _ = []
486 -- | The 'unzip4' function takes a list of quadruples and returns four lists, analogous to 'unzip'.
487 unzip4 :: [(a,b,c,d)] -> ([a],[b],[c],[d])
488 unzip4 = foldr (\(a,b,c,d) ~(as,bs,cs,ds) ->
489 (a:as,b:bs,c:cs,d:ds))
490 ([],[],[],[])
492 -- | The 'unzip5' function takes a list of five-tuples and returns five lists, analogous to 'unzip'.
493 unzip5 :: [(a,b,c,d,e)] -> ([a],[b],[c],[d],[e])
494 unzip5 = foldr (\(a,b,c,d,e) ~(as,bs,cs,ds,es) ->
495 (a:as,b:bs,c:cs,d:ds,e:es))
496 ([],[],[],[],[])
498 -- | The 'unzip6' function takes a list of six-tuples and returns six lists, analogous to 'unzip'.
499 unzip6 :: [(a,b,c,d,e,f)] -> ([a],[b],[c],[d],[e],[f])
500 unzip6 = foldr (\(a,b,c,d,e,f) ~(as,bs,cs,ds,es,fs) ->
501 (a:as,b:bs,c:cs,d:ds,e:es,f:fs))
502 ([],[],[],[],[],[])
504 -- | The 'unzip7' function takes a list of seven-tuples and returns seven lists, analogous to 'unzip'.
505 unzip7 :: [(a,b,c,d,e,f,g)] -> ([a],[b],[c],[d],[e],[f],[g])
506 unzip7 = foldr (\(a,b,c,d,e,f,g) ~(as,bs,cs,ds,es,fs,gs) ->
507 (a:as,b:bs,c:cs,d:ds,e:es,f:fs,g:gs))
508 ([],[],[],[],[],[],[])
511 -- | The 'deleteFirstsBy' function takes a predicate and two lists and returns the first
512 -- list with the first occurance of each element of the second list removed.
513 deleteFirstsBy :: (a -> a -> Bool) -> [a] -> [a] -> [a]
514 deleteFirstsBy eq = foldl (flip (deleteBy eq))
517 -- group splits its list argument into a list of lists of equal, adjacent
518 -- elements. e.g.,
519 -- group "Mississippi" == ["M","i","ss","i","ss","i","pp","i"]
520 -- | The 'group' function takes a list and returns a list of lists such
521 -- that the concatenation of the result is equal to the argument. Moreover,
522 -- each sublist in the result contains only equal elements. For example,
523 -- when applied to the string \"Mississippi\", the result is @[\"M\",\"i\",\"ss\",\"i\",\"ss\",\"i\",\"pp\",\"i\"]@.
524 group :: (Eq a) => [a] -> [[a]]
525 group = groupBy (==)
527 -- | The 'groupBy' function is the non-overloaded version of 'group'.
528 groupBy :: (a -> a -> Bool) -> [a] -> [[a]]
529 groupBy _ [] = []
530 groupBy eq (x:xs) = (x:ys) : groupBy eq zs
531 where (ys,zs) = span (eq x) xs
533 -- inits xs returns the list of initial segments of xs, shortest first.
534 -- e.g., inits "abc" == ["","a","ab","abc"]
535 -- | The 'inits' function returns all initial segements of the argument, short to long.
536 inits :: [a] -> [[a]]
537 inits [] = [[]]
538 inits (x:xs) = [[]] ++ map (x:) (inits xs)
540 -- tails xs returns the list of all final segments of xs, longest first.
541 -- e.g., tails "abc" == ["abc", "bc", "c",""]
542 -- | The 'tails' function returns all final segements of the argument, long to short.
543 tails :: [a] -> [[a]]
544 tails [] = [[]]
545 tails xxs@(_:xs) = xxs : tails xs
548 ------------------------------------------------------------------------------
549 -- Quick Sort algorithm taken from HBC's QSort library.
551 -- | The 'sort' function sorts a list with the overloaded 'compare' function.
552 sort :: (Ord a) => [a] -> [a]
553 -- | The 'sortBy' function is the non-overloaded version of 'sort'.
554 sortBy :: (a -> a -> Ordering) -> [a] -> [a]
556 #ifdef USE_REPORT_PRELUDE
557 sort = sortBy compare
558 sortBy cmp = foldr (insertBy cmp) []
559 #else
561 sortBy cmp l = mergesort cmp l
562 sort l = mergesort compare l
564 {-
565 Quicksort replaced by mergesort, 14/5/2002.
567 From: Ian Lynagh <igloo@earth.li>
569 I am curious as to why the List.sort implementation in GHC is a
570 quicksort algorithm rather than an algorithm that guarantees n log n
571 time in the worst case? I have attached a mergesort implementation along
572 with a few scripts to time it's performance, the results of which are
573 shown below (* means it didn't finish successfully - in all cases this
574 was due to a stack overflow).
576 If I heap profile the random_list case with only 10000 then I see
577 random_list peaks at using about 2.5M of memory, whereas in the same
578 program using List.sort it uses only 100k.
580 Input style Input length Sort data Sort alg User time
581 stdin 10000 random_list sort 2.82
582 stdin 10000 random_list mergesort 2.96
583 stdin 10000 sorted sort 31.37
584 stdin 10000 sorted mergesort 1.90
585 stdin 10000 revsorted sort 31.21
586 stdin 10000 revsorted mergesort 1.88
587 stdin 100000 random_list sort *
588 stdin 100000 random_list mergesort *
589 stdin 100000 sorted sort *
590 stdin 100000 sorted mergesort *
591 stdin 100000 revsorted sort *
592 stdin 100000 revsorted mergesort *
593 func 10000 random_list sort 0.31
594 func 10000 random_list mergesort 0.91
595 func 10000 sorted sort 19.09
596 func 10000 sorted mergesort 0.15
597 func 10000 revsorted sort 19.17
598 func 10000 revsorted mergesort 0.16
599 func 100000 random_list sort 3.85
600 func 100000 random_list mergesort *
601 func 100000 sorted sort 5831.47
602 func 100000 sorted mergesort 2.23
603 func 100000 revsorted sort 5872.34
604 func 100000 revsorted mergesort 2.24
605 -}
607 mergesort :: (a -> a -> Ordering) -> [a] -> [a]
608 mergesort cmp = mergesort' cmp . map wrap
610 mergesort' :: (a -> a -> Ordering) -> [[a]] -> [a]
611 mergesort' cmp [] = []
612 mergesort' cmp [xs] = xs
613 mergesort' cmp xss = mergesort' cmp (merge_pairs cmp xss)
615 merge_pairs :: (a -> a -> Ordering) -> [[a]] -> [[a]]
616 merge_pairs cmp [] = []
617 merge_pairs cmp [xs] = [xs]
618 merge_pairs cmp (xs:ys:xss) = merge cmp xs ys : merge_pairs cmp xss
620 merge :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
621 merge cmp xs [] = xs
622 merge cmp [] ys = ys
623 merge cmp (x:xs) (y:ys)
624 = case x cmp y of
625 GT -> y : merge cmp (x:xs) ys
626 _ -> x : merge cmp xs (y:ys)
628 wrap :: a -> [a]
629 wrap x = [x]
631 {-
632 OLD: qsort version
634 -- qsort is stable and does not concatenate.
635 qsort :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
636 qsort _ [] r = r
637 qsort _ [x] r = x:r
638 qsort cmp (x:xs) r = qpart cmp x xs [] [] r
640 -- qpart partitions and sorts the sublists
641 qpart :: (a -> a -> Ordering) -> a -> [a] -> [a] -> [a] -> [a] -> [a]
642 qpart cmp x [] rlt rge r =
643 -- rlt and rge are in reverse order and must be sorted with an
644 -- anti-stable sorting
645 rqsort cmp rlt (x:rqsort cmp rge r)
646 qpart cmp x (y:ys) rlt rge r =
647 case cmp x y of
648 GT -> qpart cmp x ys (y:rlt) rge r
649 _ -> qpart cmp x ys rlt (y:rge) r
651 -- rqsort is as qsort but anti-stable, i.e. reverses equal elements
652 rqsort :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
653 rqsort _ [] r = r
654 rqsort _ [x] r = x:r
655 rqsort cmp (x:xs) r = rqpart cmp x xs [] [] r
657 rqpart :: (a -> a -> Ordering) -> a -> [a] -> [a] -> [a] -> [a] -> [a]
658 rqpart cmp x [] rle rgt r =
659 qsort cmp rle (x:qsort cmp rgt r)
660 rqpart cmp x (y:ys) rle rgt r =
661 case cmp y x of
662 GT -> rqpart cmp x ys rle (y:rgt) r
663 _ -> rqpart cmp x ys (y:rle) rgt r
664 -}
666 #endif /* USE_REPORT_PRELUDE */
668 {-
669 \begin{verbatim}
670 unfoldr f' (foldr f z xs) == (z,xs)
672 if the following holds:
674 f' (f x y) = Just (x,y)
675 f' z = Nothing
676 \end{verbatim}
677 -}
679 -- | The 'unfoldr' function produces a list from an element. The function
680 -- takes the element and returns 'Nothing' if it is done producing the list
681 -- or returns @Just (a,b)@, in which case, @a@ is a prepended to the list
682 -- and @b@ is used as the next element in a recursive call.
683 unfoldr :: (b -> Maybe (a, b)) -> b -> [a]
684 unfoldr f b =
685 case f b of
686 Just (a,new_b) -> a : unfoldr f new_b
687 Nothing -> []
690 -- -----------------------------------------------------------------------------
691 -- strict version of foldl
693 -- | A strict version of 'foldl'
694 foldl' :: (a -> b -> a) -> a -> [b] -> a
695 foldl' f a [] = a
696 foldl' f a (x:xs) = let a' = f a x in a' seq` foldl' f a' xs
699 -- -----------------------------------------------------------------------------
700 -- List sum and product
702 -- sum and product compute the sum or product of a finite list of numbers.
703 {-# SPECIALISE sum :: [Int] -> Int #-}
704 {-# SPECIALISE sum :: [Integer] -> Integer #-}
705 {-# SPECIALISE product :: [Int] -> Int #-}
706 {-# SPECIALISE product :: [Integer] -> Integer #-}
707 sum, product :: (Num a) => [a] -> a
708 #ifdef USE_REPORT_PRELUDE
709 -- | The 'sum' function sums the elements of a list.
710 sum = foldl (+) 0
711 -- | The 'product' function computes the product of the elements of a list.
712 product = foldl (*) 1
713 #else
714 -- | The 'sum' function sums the elements of a list.
715 sum l = sum' l 0
716 where
717 sum' [] a = a
718 sum' (x:xs) a = sum' xs (a+x)
719 -- | The 'product' function computes the product of the elements of a list.
720 product l = prod l 1
721 where
722 prod [] a = a
723 prod (x:xs) a = prod xs (a*x)
724 #endif
726 -- -----------------------------------------------------------------------------
727 -- Functions on strings
729 -- lines breaks a string up into a list of strings at newline characters.
730 -- The resulting strings do not contain newlines. Similary, words
731 -- breaks a string up into a list of words, which were delimited by
732 -- white space. unlines and unwords are the inverse operations.
733 -- unlines joins lines with terminating newlines, and unwords joins
734 -- words with separating spaces.
736 lines :: String -> [String]
737 lines "" = []
738 lines s = let (l, s') = break (== '\n') s
739 in l : case s' of
740 [] -> []
741 (_:s'') -> lines s''
743 unlines :: [String] -> String
744 #ifdef USE_REPORT_PRELUDE
745 unlines = concatMap (++ "\n")
746 #else
747 -- HBC version (stolen)
748 -- here's a more efficient version
749 unlines [] = []
750 unlines (l:ls) = l ++ '\n' : unlines ls
751 #endif
753 words :: String -> [String]
754 words s = case dropWhile {-partain:Char.-}isSpace s of
755 "" -> []
756 s' -> w : words s''
757 where (w, s'') =
758 break {-partain:Char.-}isSpace s'
760 unwords :: [String] -> String
761 #ifdef USE_REPORT_PRELUDE
762 unwords [] = ""
763 unwords ws = foldr1 (\w s -> w ++ ' ':s) ws
764 #else
765 -- HBC version (stolen)
766 -- here's a more efficient version
767 unwords [] = ""
768 unwords [w] = w
769 unwords (w:ws) = w ++ ' ' : unwords ws
770 #endif