Data/List.hs

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