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