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 {-# RULES
 572   "genericLengthInt"     genericLength = (strictGenericLength :: [a] -> Int);
 573   "genericLengthInteger" genericLength = (strictGenericLength :: [a] -> Integer);
 574  #-}
 575
 576 strictGenericLength     :: (Num i) => [b] -> i
 577 strictGenericLength l   =  gl l 0
 578                         where
 579                            gl [] a     = a
 580                            gl (_:xs) a = let a' = a + 1 in a' `seq` gl xs a'
 581
 582 -- | The 'genericTake' function is an overloaded version of 'take', which
 583 -- accepts any 'Integral' value as the number of elements to take.
 584 genericTake             :: (Integral i) => i -> [a] -> [a]
 585 genericTake n _ | n <= 0 = []
 586 genericTake _ []        =  []
 587 genericTake n (x:xs)    =  x : genericTake (n-1) xs
 588
 589 -- | The 'genericDrop' function is an overloaded version of 'drop', which
 590 -- accepts any 'Integral' value as the number of elements to drop.
 591 genericDrop             :: (Integral i) => i -> [a] -> [a]
 592 genericDrop n xs | n <= 0 = xs
 593 genericDrop _ []        =  []
 594 genericDrop n (_:xs)    =  genericDrop (n-1) xs
 595
 596
 597 -- | The 'genericSplitAt' function is an overloaded version of 'splitAt', which
 598 -- accepts any 'Integral' value as the position at which to split.
 599 genericSplitAt          :: (Integral i) => i -> [b] -> ([b],[b])
 600 genericSplitAt n xs | n <= 0 =  ([],xs)
 601 genericSplitAt _ []     =  ([],[])
 602 genericSplitAt n (x:xs) =  (x:xs',xs'') where
 603     (xs',xs'') = genericSplitAt (n-1) xs
 604
 605 -- | The 'genericIndex' function is an overloaded version of '!!', which
 606 -- accepts any 'Integral' value as the index.
 607 genericIndex :: (Integral a) => [b] -> a -> b
 608 genericIndex (x:_)  0 = x
 609 genericIndex (_:xs) n
 610  | n > 0     = genericIndex xs (n-1)
 611  | otherwise = error "List.genericIndex: negative argument."
 612 genericIndex _ _      = error "List.genericIndex: index too large."
 613
 614 -- | The 'genericReplicate' function is an overloaded version of 'replicate',
 615 -- which accepts any 'Integral' value as the number of repetitions to make.
 616 genericReplicate        :: (Integral i) => i -> a -> [a]
 617 genericReplicate n x    =  genericTake n (repeat x)
 618
 619 -- | The 'zip4' function takes four lists and returns a list of
 620 -- quadruples, analogous to 'zip'.
 621 zip4                    :: [a] -> [b] -> [c] -> [d] -> [(a,b,c,d)]
 622 zip4                    =  zipWith4 (,,,)
 623
 624 -- | The 'zip5' function takes five lists and returns a list of
 625 -- five-tuples, analogous to 'zip'.
 626 zip5                    :: [a] -> [b] -> [c] -> [d] -> [e] -> [(a,b,c,d,e)]
 627 zip5                    =  zipWith5 (,,,,)
 628
 629 -- | The 'zip6' function takes six lists and returns a list of six-tuples,
 630 -- analogous to 'zip'.
 631 zip6                    :: [a] -> [b] -> [c] -> [d] -> [e] -> [f] ->
 632                               [(a,b,c,d,e,f)]
 633 zip6                    =  zipWith6 (,,,,,)
 634
 635 -- | The 'zip7' function takes seven lists and returns a list of
 636 -- seven-tuples, analogous to 'zip'.
 637 zip7                    :: [a] -> [b] -> [c] -> [d] -> [e] -> [f] ->
 638                               [g] -> [(a,b,c,d,e,f,g)]
 639 zip7                    =  zipWith7 (,,,,,,)
 640
 641 -- | The 'zipWith4' function takes a function which combines four
 642 -- elements, as well as four lists and returns a list of their point-wise
 643 -- combination, analogous to 'zipWith'.
 644 zipWith4                :: (a->b->c->d->e) -> [a]->[b]->[c]->[d]->[e]
 645 zipWith4 z (a:as) (b:bs) (c:cs) (d:ds)
 646                         =  z a b c d : zipWith4 z as bs cs ds
 647 zipWith4 _ _ _ _ _      =  []
 648
 649 -- | The 'zipWith5' function takes a function which combines five
 650 -- elements, as well as five lists and returns a list of their point-wise
 651 -- combination, analogous to 'zipWith'.
 652 zipWith5                :: (a->b->c->d->e->f) ->
 653                            [a]->[b]->[c]->[d]->[e]->[f]
 654 zipWith5 z (a:as) (b:bs) (c:cs) (d:ds) (e:es)
 655                         =  z a b c d e : zipWith5 z as bs cs ds es
 656 zipWith5 _ _ _ _ _ _    = []
 657
 658 -- | The 'zipWith6' function takes a function which combines six
 659 -- elements, as well as six lists and returns a list of their point-wise
 660 -- combination, analogous to 'zipWith'.
 661 zipWith6                :: (a->b->c->d->e->f->g) ->
 662                            [a]->[b]->[c]->[d]->[e]->[f]->[g]
 663 zipWith6 z (a:as) (b:bs) (c:cs) (d:ds) (e:es) (f:fs)
 664                         =  z a b c d e f : zipWith6 z as bs cs ds es fs
 665 zipWith6 _ _ _ _ _ _ _  = []
 666
 667 -- | The 'zipWith7' function takes a function which combines seven
 668 -- elements, as well as seven lists and returns a list of their point-wise
 669 -- combination, analogous to 'zipWith'.
 670 zipWith7                :: (a->b->c->d->e->f->g->h) ->
 671                            [a]->[b]->[c]->[d]->[e]->[f]->[g]->[h]
 672 zipWith7 z (a:as) (b:bs) (c:cs) (d:ds) (e:es) (f:fs) (g:gs)
 673                    =  z a b c d e f g : zipWith7 z as bs cs ds es fs gs
 674 zipWith7 _ _ _ _ _ _ _ _ = []
 675
 676 -- | The 'unzip4' function takes a list of quadruples and returns four
 677 -- lists, analogous to 'unzip'.
 678 unzip4                  :: [(a,b,c,d)] -> ([a],[b],[c],[d])
 679 unzip4                  =  foldr (\(a,b,c,d) ~(as,bs,cs,ds) ->
 680                                         (a:as,b:bs,c:cs,d:ds))
 681                                  ([],[],[],[])
 682
 683 -- | The 'unzip5' function takes a list of five-tuples and returns five
 684 -- lists, analogous to 'unzip'.
 685 unzip5                  :: [(a,b,c,d,e)] -> ([a],[b],[c],[d],[e])
 686 unzip5                  =  foldr (\(a,b,c,d,e) ~(as,bs,cs,ds,es) ->
 687                                         (a:as,b:bs,c:cs,d:ds,e:es))
 688                                  ([],[],[],[],[])
 689
 690 -- | The 'unzip6' function takes a list of six-tuples and returns six
 691 -- lists, analogous to 'unzip'.
 692 unzip6                  :: [(a,b,c,d,e,f)] -> ([a],[b],[c],[d],[e],[f])
 693 unzip6                  =  foldr (\(a,b,c,d,e,f) ~(as,bs,cs,ds,es,fs) ->
 694                                         (a:as,b:bs,c:cs,d:ds,e:es,f:fs))
 695                                  ([],[],[],[],[],[])
 696
 697 -- | The 'unzip7' function takes a list of seven-tuples and returns
 698 -- seven lists, analogous to 'unzip'.
 699 unzip7          :: [(a,b,c,d,e,f,g)] -> ([a],[b],[c],[d],[e],[f],[g])
 700 unzip7          =  foldr (\(a,b,c,d,e,f,g) ~(as,bs,cs,ds,es,fs,gs) ->
 701                                 (a:as,b:bs,c:cs,d:ds,e:es,f:fs,g:gs))
 702                          ([],[],[],[],[],[],[])
 703
 704
 705 -- | The 'deleteFirstsBy' function takes a predicate and two lists and
 706 -- returns the first list with the first occurrence of each element of
 707 -- the second list removed.
 708 deleteFirstsBy          :: (a -> a -> Bool) -> [a] -> [a] -> [a]
 709 deleteFirstsBy eq       =  foldl (flip (deleteBy eq))
 710
 711 -- | The 'group' function takes a list and returns a list of lists such
 712 -- that the concatenation of the result is equal to the argument.  Moreover,
 713 -- each sublist in the result contains only equal elements.  For example,
 714 --
 715 -- > group "Mississippi" = ["M","i","ss","i","ss","i","pp","i"]
 716 --
 717 -- It is a special case of 'groupBy', which allows the programmer to supply
 718 -- their own equality test.
 719 group                   :: Eq a => [a] -> [[a]]
 720 group                   =  groupBy (==)
 721
 722 -- | The 'groupBy' function is the non-overloaded version of 'group'.
 723 groupBy                 :: (a -> a -> Bool) -> [a] -> [[a]]
 724 groupBy _  []           =  []
 725 groupBy eq (x:xs)       =  (x:ys) : groupBy eq zs
 726                            where (ys,zs) = span (eq x) xs
 727
 728 -- | The 'inits' function returns all initial segments of the argument,
 729 -- shortest first.  For example,
 730 --
 731 -- > inits "abc" == ["","a","ab","abc"]
 732 --
 733 inits                   :: [a] -> [[a]]
 734 inits []                =  [[]]
 735 inits (x:xs)            =  [[]] ++ map (x:) (inits xs)
 736
 737 -- | The 'tails' function returns all final segments of the argument,
 738 -- longest first.  For example,
 739 --
 740 -- > tails "abc" == ["abc", "bc", "c",""]
 741 --
 742 tails                   :: [a] -> [[a]]
 743 tails []                =  [[]]
 744 tails xxs@(_:xs)        =  xxs : tails xs
 745
 746
 747 -- | The 'subsequences' function returns the list of all subsequences of the argument.
 748 --
 749 -- > subsequences "abc" == ["","a","b","ab","c","ac","bc","abc"]
 750 subsequences            :: [a] -> [[a]]
 751 subsequences xs         =  [] : nonEmptySubsequences xs
 752
 753 -- | The 'nonEmptySubsequences' function returns the list of all subsequences of the argument,
 754 --   except for the empty list.
 755 --
 756 -- > nonEmptySubsequences "abc" == ["a","b","ab","c","ac","bc","abc"]
 757 nonEmptySubsequences         :: [a] -> [[a]]
 758 nonEmptySubsequences []      =  []
 759 nonEmptySubsequences (x:xs)  =  [x] : foldr f [] (nonEmptySubsequences xs)
 760   where f ys r = ys : (x : ys) : r
 761
 762
 763 -- | The 'permutations' function returns the list of all permutations of the argument.
 764 --
 765 -- > permutations "abc" == ["abc","bac","cba","bca","cab","acb"]
 766 permutations            :: [a] -> [[a]]
 767 permutations xs0        =  xs0 : perms xs0 []
 768   where
 769     perms []     _  = []
 770     perms (t:ts) is = foldr interleave (perms ts (t:is)) (permutations is)
 771       where interleave    xs     r = let (_,zs) = interleave' id xs r in zs
 772             interleave' _ []     r = (ts, r)
 773             interleave' f (y:ys) r = let (us,zs) = interleave' (f . (y:)) ys r
 774                                      in  (y:us, f (t:y:us) : zs)
 775
 776
 777 ------------------------------------------------------------------------------
 778 -- Quick Sort algorithm taken from HBC's QSort library.
 779
 780 -- | The 'sort' function implements a stable sorting algorithm.
 781 -- It is a special case of 'sortBy', which allows the programmer to supply
 782 -- their own comparison function.
 783 sort :: (Ord a) => [a] -> [a]
 784
 785 -- | The 'sortBy' function is the non-overloaded version of 'sort'.
 786 sortBy :: (a -> a -> Ordering) -> [a] -> [a]
 787
 788 #ifdef USE_REPORT_PRELUDE
 789 sort = sortBy compare
 790 sortBy cmp = foldr (insertBy cmp) []
 791 #else
 792
 793 sortBy cmp l = mergesort cmp l
 794 sort l = mergesort compare l
 795
 796 {-
 797 Quicksort replaced by mergesort, 14/5/2002.
 798
 799 From: Ian Lynagh <igloo@earth.li>
 800
 801 I am curious as to why the List.sort implementation in GHC is a
 802 quicksort algorithm rather than an algorithm that guarantees n log n
 803 time in the worst case? I have attached a mergesort implementation along
 804 with a few scripts to time it's performance, the results of which are
 805 shown below (* means it didn't finish successfully - in all cases this
 806 was due to a stack overflow).
 807
 808 If I heap profile the random_list case with only 10000 then I see
 809 random_list peaks at using about 2.5M of memory, whereas in the same
 810 program using List.sort it uses only 100k.
 811
 812 Input style     Input length     Sort data     Sort alg    User time
 813 stdin           10000            random_list   sort        2.82
 814 stdin           10000            random_list   mergesort   2.96
 815 stdin           10000            sorted        sort        31.37
 816 stdin           10000            sorted        mergesort   1.90
 817 stdin           10000            revsorted     sort        31.21
 818 stdin           10000            revsorted     mergesort   1.88
 819 stdin           100000           random_list   sort        *
 820 stdin           100000           random_list   mergesort   *
 821 stdin           100000           sorted        sort        *
 822 stdin           100000           sorted        mergesort   *
 823 stdin           100000           revsorted     sort        *
 824 stdin           100000           revsorted     mergesort   *
 825 func            10000            random_list   sort        0.31
 826 func            10000            random_list   mergesort   0.91
 827 func            10000            sorted        sort        19.09
 828 func            10000            sorted        mergesort   0.15
 829 func            10000            revsorted     sort        19.17
 830 func            10000            revsorted     mergesort   0.16
 831 func            100000           random_list   sort        3.85
 832 func            100000           random_list   mergesort   *
 833 func            100000           sorted        sort        5831.47
 834 func            100000           sorted        mergesort   2.23
 835 func            100000           revsorted     sort        5872.34
 836 func            100000           revsorted     mergesort   2.24
 837 -}
 838
 839 mergesort :: (a -> a -> Ordering) -> [a] -> [a]
 840 mergesort cmp = mergesort' cmp . map wrap
 841
 842 mergesort' :: (a -> a -> Ordering) -> [[a]] -> [a]
 843 mergesort' _   [] = []
 844 mergesort' _   [xs] = xs
 845 mergesort' cmp xss = mergesort' cmp (merge_pairs cmp xss)
 846
 847 merge_pairs :: (a -> a -> Ordering) -> [[a]] -> [[a]]
 848 merge_pairs _   [] = []
 849 merge_pairs _   [xs] = [xs]
 850 merge_pairs cmp (xs:ys:xss) = merge cmp xs ys : merge_pairs cmp xss
 851
 852 merge :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
 853 merge _   [] ys = ys
 854 merge _   xs [] = xs
 855 merge cmp (x:xs) (y:ys)
 856  = case x `cmp` y of
 857         GT -> y : merge cmp (x:xs)   ys
 858         _  -> x : merge cmp    xs (y:ys)
 859
 860 wrap :: a -> [a]
 861 wrap x = [x]
 862
 863 {-
 864 OLD: qsort version
 865
 866 -- qsort is stable and does not concatenate.
 867 qsort :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
 868 qsort _   []     r = r
 869 qsort _   [x]    r = x:r
 870 qsort cmp (x:xs) r = qpart cmp x xs [] [] r
 871
 872 -- qpart partitions and sorts the sublists
 873 qpart :: (a -> a -> Ordering) -> a -> [a] -> [a] -> [a] -> [a] -> [a]
 874 qpart cmp x [] rlt rge r =
 875     -- rlt and rge are in reverse order and must be sorted with an
 876     -- anti-stable sorting
 877     rqsort cmp rlt (x:rqsort cmp rge r)
 878 qpart cmp x (y:ys) rlt rge r =
 879     case cmp x y of
 880         GT -> qpart cmp x ys (y:rlt) rge r
 881         _  -> qpart cmp x ys rlt (y:rge) r
 882
 883 -- rqsort is as qsort but anti-stable, i.e. reverses equal elements
 884 rqsort :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
 885 rqsort _   []     r = r
 886 rqsort _   [x]    r = x:r
 887 rqsort cmp (x:xs) r = rqpart cmp x xs [] [] r
 888
 889 rqpart :: (a -> a -> Ordering) -> a -> [a] -> [a] -> [a] -> [a] -> [a]
 890 rqpart cmp x [] rle rgt r =
 891     qsort cmp rle (x:qsort cmp rgt r)
 892 rqpart cmp x (y:ys) rle rgt r =
 893     case cmp y x of
 894         GT -> rqpart cmp x ys rle (y:rgt) r
 895         _  -> rqpart cmp x ys (y:rle) rgt r
 896 -}
 897
 898 #endif /* USE_REPORT_PRELUDE */
 899
 900 -- | The 'unfoldr' function is a \`dual\' to 'foldr': while 'foldr'
 901 -- reduces a list to a summary value, 'unfoldr' builds a list from
 902 -- a seed value.  The function takes the element and returns 'Nothing'
 903 -- if it is done producing the list or returns 'Just' @(a,b)@, in which
 904 -- case, @a@ is a prepended to the list and @b@ is used as the next
 905 -- element in a recursive call.  For example,
 906 --
 907 -- > iterate f == unfoldr (\x -> Just (x, f x))
 908 --
 909 -- In some cases, 'unfoldr' can undo a 'foldr' operation:
 910 --
 911 -- > unfoldr f' (foldr f z xs) == xs
 912 --
 913 -- if the following holds:
 914 --
 915 -- > f' (f x y) = Just (x,y)
 916 -- > f' z       = Nothing
 917 --
 918 -- A simple use of unfoldr:
 919 --
 920 -- > unfoldr (\b -> if b == 0 then Nothing else Just (b, b-1)) 10
 921 -- >  [10,9,8,7,6,5,4,3,2,1]
 922 --
 923 unfoldr      :: (b -> Maybe (a, b)) -> b -> [a]
 924 unfoldr f b  =
 925   case f b of
 926    Just (a,new_b) -> a : unfoldr f new_b
 927    Nothing        -> []
 928
 929 -- -----------------------------------------------------------------------------
 930
 931 -- | A strict version of 'foldl'.
 932 foldl'           :: (a -> b -> a) -> a -> [b] -> a
 933 #ifdef __GLASGOW_HASKELL__
 934 foldl' f z0 xs0 = lgo z0 xs0
 935     where lgo z []     = z
 936           lgo z (x:xs) = let z' = f z x in z' `seq` lgo z' xs
 937 #else
 938 foldl' f a []     = a
 939 foldl' f a (x:xs) = let a' = f a x in a' `seq` foldl' f a' xs
 940 #endif
 941
 942 #ifdef __GLASGOW_HASKELL__
 943 -- | 'foldl1' is a variant of 'foldl' that has no starting value argument,
 944 -- and thus must be applied to non-empty lists.
 945 foldl1                  :: (a -> a -> a) -> [a] -> a
 946 foldl1 f (x:xs)         =  foldl f x xs
 947 foldl1 _ []             =  errorEmptyList "foldl1"
 948 #endif /* __GLASGOW_HASKELL__ */
 949
 950 -- | A strict version of 'foldl1'
 951 foldl1'                  :: (a -> a -> a) -> [a] -> a
 952 foldl1' f (x:xs)         =  foldl' f x xs
 953 foldl1' _ []             =  errorEmptyList "foldl1'"
 954
 955 #ifdef __GLASGOW_HASKELL__
 956 -- -----------------------------------------------------------------------------
 957 -- List sum and product
 958
 959 {-# SPECIALISE sum     :: [Int] -> Int #-}
 960 {-# SPECIALISE sum     :: [Integer] -> Integer #-}
 961 {-# SPECIALISE product :: [Int] -> Int #-}
 962 {-# SPECIALISE product :: [Integer] -> Integer #-}
 963 -- | The 'sum' function computes the sum of a finite list of numbers.
 964 sum                     :: (Num a) => [a] -> a
 965 -- | The 'product' function computes the product of a finite list of numbers.
 966 product                 :: (Num a) => [a] -> a
 967 #ifdef USE_REPORT_PRELUDE
 968 sum                     =  foldl (+) 0
 969 product                 =  foldl (*) 1
 970 #else
 971 sum     l       = sum' l 0
 972   where
 973     sum' []     a = a
 974     sum' (x:xs) a = sum' xs (a+x)
 975 product l       = prod l 1
 976   where
 977     prod []     a = a
 978     prod (x:xs) a = prod xs (a*x)
 979 #endif
 980
 981 -- -----------------------------------------------------------------------------
 982 -- Functions on strings
 983
 984 -- | 'lines' breaks a string up into a list of strings at newline
 985 -- characters.  The resulting strings do not contain newlines.
 986 lines                   :: String -> [String]
 987 lines ""                =  []
 988 lines s                 =  let (l, s') = break (== '\n') s
 989                            in  l : case s' of
 990                                         []      -> []
 991                                         (_:s'') -> lines s''
 992
 993 -- | 'unlines' is an inverse operation to 'lines'.
 994 -- It joins lines, after appending a terminating newline to each.
 995 unlines                 :: [String] -> String
 996 #ifdef USE_REPORT_PRELUDE
 997 unlines                 =  concatMap (++ "\n")
 998 #else
 999 -- HBC version (stolen)
1000 -- here's a more efficient version
1001 unlines [] = []
1002 unlines (l:ls) = l ++ '\n' : unlines ls
1003 #endif
1004
1005 -- | 'words' breaks a string up into a list of words, which were delimited
1006 -- by white space.
1007 words                   :: String -> [String]
1008 words s                 =  case dropWhile {-partain:Char.-}isSpace s of
1009                                 "" -> []
1010                                 s' -> w : words s''
1011                                       where (w, s'') =
1012                                              break {-partain:Char.-}isSpace s'
1013
1014 -- | 'unwords' is an inverse operation to 'words'.
1015 -- It joins words with separating spaces.
1016 unwords                 :: [String] -> String
1017 #ifdef USE_REPORT_PRELUDE
1018 unwords []              =  ""
1019 unwords ws              =  foldr1 (\w s -> w ++ ' ':s) ws
1020 #else
1021 -- HBC version (stolen)
1022 -- here's a more efficient version
1023 unwords []              =  ""
1024 unwords [w]             = w
1025 unwords (w:ws)          = w ++ ' ' : unwords ws
1026 #endif
1027
1028 #else  /* !__GLASGOW_HASKELL__ */
1029
1030 errorEmptyList :: String -> a
1031 errorEmptyList fun =
1032   error ("Prelude." ++ fun ++ ": empty list")
1033
1034 #endif /* !__GLASGOW_HASKELL__ */