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