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