Data/List.hs

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