Data/List.hs

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