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 -- | /O(n^2)/. 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 --
 403 -- > [1,2,2,3,4] `intersect` [6,4,4,2] == [2,2,4]
 404 --
 405 -- It is a special case of 'intersectBy', which allows the programmer to
 406 -- supply their own equality test.
 407
 408 intersect               :: (Eq a) => [a] -> [a] -> [a]
 409 intersect               =  intersectBy (==)
 410
 411 -- | The 'intersectBy' function is the non-overloaded version of 'intersect'.
 412 intersectBy             :: (a -> a -> Bool) -> [a] -> [a] -> [a]
 413 intersectBy _  [] _     =  []
 414 intersectBy _  _  []    =  []
 415 intersectBy eq xs ys    =  [x | x <- xs, any (eq x) ys]
 416
 417 -- | The 'intersperse' function takes an element and a list and
 418 -- \`intersperses\' that element between the elements of the list.
 419 -- For example,
 420 --
 421 -- > intersperse ',' "abcde" == "a,b,c,d,e"
 422
 423 intersperse             :: a -> [a] -> [a]
 424 intersperse _   []      = []
 425 intersperse sep (x:xs)  = x : prependToAll sep xs
 426
 427
 428 -- Not exported:
 429 -- We want to make every element in the 'intersperse'd list available
 430 -- as soon as possible to avoid space leaks. Experiments suggested that
 431 -- a separate top-level helper is more efficient than a local worker.
 432 prependToAll            :: a -> [a] -> [a]
 433 prependToAll _   []     = []
 434 prependToAll sep (x:xs) = sep : x : prependToAll sep xs
 435
 436 -- | 'intercalate' @xs xss@ is equivalent to @('concat' ('intersperse' xs xss))@.
 437 -- It inserts the list @xs@ in between the lists in @xss@ and concatenates the
 438 -- result.
 439 intercalate :: [a] -> [[a]] -> [a]
 440 intercalate xs xss = concat (intersperse xs xss)
 441
 442 -- | The 'transpose' function transposes the rows and columns of its argument.
 443 -- For example,
 444 --
 445 -- > transpose [[1,2,3],[4,5,6]] == [[1,4],[2,5],[3,6]]
 446
 447 transpose               :: [[a]] -> [[a]]
 448 transpose []             = []
 449 transpose ([]   : xss)   = transpose xss
 450 transpose ((x:xs) : xss) = (x : [h | (h:_) <- xss]) : transpose (xs : [ t | (_:t) <- xss])
 451
 452
 453 -- | The 'partition' function takes a predicate a list and returns
 454 -- the pair of lists of elements which do and do not satisfy the
 455 -- predicate, respectively; i.e.,
 456 --
 457 -- > partition p xs == (filter p xs, filter (not . p) xs)
 458
 459 partition               :: (a -> Bool) -> [a] -> ([a],[a])
 460 {-# INLINE partition #-}
 461 partition p xs = foldr (select p) ([],[]) xs
 462
 463 select :: (a -> Bool) -> a -> ([a], [a]) -> ([a], [a])
 464 select p x ~(ts,fs) | p x       = (x:ts,fs)
 465                     | otherwise = (ts, x:fs)
 466
 467 -- | The 'mapAccumL' function behaves like a combination of 'map' and
 468 -- 'foldl'; it applies a function to each element of a list, passing
 469 -- an accumulating parameter from left to right, and returning a final
 470 -- value of this accumulator together with the new list.
 471 mapAccumL :: (acc -> x -> (acc, y)) -- Function of elt of input list
 472                                     -- and accumulator, returning new
 473                                     -- accumulator and elt of result list
 474           -> acc            -- Initial accumulator
 475           -> [x]            -- Input list
 476           -> (acc, [y])     -- Final accumulator and result list
 477 mapAccumL _ s []        =  (s, [])
 478 mapAccumL f s (x:xs)    =  (s'',y:ys)
 479                            where (s', y ) = f s x
 480                                  (s'',ys) = mapAccumL f s' xs
 481
 482 -- | The 'mapAccumR' function behaves like a combination of 'map' and
 483 -- 'foldr'; it applies a function to each element of a list, passing
 484 -- an accumulating parameter from right to left, and returning a final
 485 -- value of this accumulator together with the new list.
 486 mapAccumR :: (acc -> x -> (acc, y))     -- Function of elt of input list
 487                                         -- and accumulator, returning new
 488                                         -- accumulator and elt of result list
 489             -> acc              -- Initial accumulator
 490             -> [x]              -- Input list
 491             -> (acc, [y])               -- Final accumulator and result list
 492 mapAccumR _ s []        =  (s, [])
 493 mapAccumR f s (x:xs)    =  (s'', y:ys)
 494                            where (s'',y ) = f s' x
 495                                  (s', ys) = mapAccumR f s xs
 496
 497 -- | The 'insert' function takes an element and a list and inserts the
 498 -- element into the list at the last position where it is still less
 499 -- than or equal to the next element.  In particular, if the list
 500 -- is sorted before the call, the result will also be sorted.
 501 -- It is a special case of 'insertBy', which allows the programmer to
 502 -- supply their own comparison function.
 503 insert :: Ord a => a -> [a] -> [a]
 504 insert e ls = insertBy (compare) e ls
 505
 506 -- | The non-overloaded version of 'insert'.
 507 insertBy :: (a -> a -> Ordering) -> a -> [a] -> [a]
 508 insertBy _   x [] = [x]
 509 insertBy cmp x ys@(y:ys')
 510  = case cmp x y of
 511      GT -> y : insertBy cmp x ys'
 512      _  -> x : ys
 513
 514 #ifdef __GLASGOW_HASKELL__
 515
 516 -- | 'maximum' returns the maximum value from a list,
 517 -- which must be non-empty, finite, and of an ordered type.
 518 -- It is a special case of 'Data.List.maximumBy', which allows the
 519 -- programmer to supply their own comparison function.
 520 maximum                 :: (Ord a) => [a] -> a
 521 maximum []              =  errorEmptyList "maximum"
 522 maximum xs              =  foldl1 max xs
 523
 524 {-# RULES
 525   "maximumInt"     maximum = (strictMaximum :: [Int]     -> Int);
 526   "maximumInteger" maximum = (strictMaximum :: [Integer] -> Integer)
 527  #-}
 528
 529 -- We can't make the overloaded version of maximum strict without
 530 -- changing its semantics (max might not be strict), but we can for
 531 -- the version specialised to 'Int'.
 532 strictMaximum           :: (Ord a) => [a] -> a
 533 strictMaximum []        =  errorEmptyList "maximum"
 534 strictMaximum xs        =  foldl1' max xs
 535
 536 -- | 'minimum' returns the minimum value from a list,
 537 -- which must be non-empty, finite, and of an ordered type.
 538 -- It is a special case of 'Data.List.minimumBy', which allows the
 539 -- programmer to supply their own comparison function.
 540 minimum                 :: (Ord a) => [a] -> a
 541 minimum []              =  errorEmptyList "minimum"
 542 minimum xs              =  foldl1 min xs
 543
 544 {-# RULES
 545   "minimumInt"     minimum = (strictMinimum :: [Int]     -> Int);
 546   "minimumInteger" minimum = (strictMinimum :: [Integer] -> Integer)
 547  #-}
 548
 549 strictMinimum           :: (Ord a) => [a] -> a
 550 strictMinimum []        =  errorEmptyList "minimum"
 551 strictMinimum xs        =  foldl1' min xs
 552
 553 #endif /* __GLASGOW_HASKELL__ */
 554
 555 -- | The 'maximumBy' function takes a comparison function and a list
 556 -- and returns the greatest element of the list by the comparison function.
 557 -- The list must be finite and non-empty.
 558 maximumBy               :: (a -> a -> Ordering) -> [a] -> a
 559 maximumBy _ []          =  error "List.maximumBy: empty list"
 560 maximumBy cmp xs        =  foldl1 maxBy xs
 561                         where
 562                            maxBy x y = case cmp x y of
 563                                        GT -> x
 564                                        _  -> y
 565
 566 -- | The 'minimumBy' function takes a comparison function and a list
 567 -- and returns the least element of the list by the comparison function.
 568 -- The list must be finite and non-empty.
 569 minimumBy               :: (a -> a -> Ordering) -> [a] -> a
 570 minimumBy _ []          =  error "List.minimumBy: empty list"
 571 minimumBy cmp xs        =  foldl1 minBy xs
 572                         where
 573                            minBy x y = case cmp x y of
 574                                        GT -> y
 575                                        _  -> x
 576
 577 -- | The 'genericLength' function is an overloaded version of 'length'.  In
 578 -- particular, instead of returning an 'Int', it returns any type which is
 579 -- an instance of 'Num'.  It is, however, less efficient than 'length'.
 580 genericLength           :: (Num i) => [b] -> i
 581 genericLength []        =  0
 582 genericLength (_:l)     =  1 + genericLength l
 583
 584 {-# RULES
 585   "genericLengthInt"     genericLength = (strictGenericLength :: [a] -> Int);
 586   "genericLengthInteger" genericLength = (strictGenericLength :: [a] -> Integer);
 587  #-}
 588
 589 strictGenericLength     :: (Num i) => [b] -> i
 590 strictGenericLength l   =  gl l 0
 591                         where
 592                            gl [] a     = a
 593                            gl (_:xs) a = let a' = a + 1 in a' `seq` gl xs a'
 594
 595 -- | The 'genericTake' function is an overloaded version of 'take', which
 596 -- accepts any 'Integral' value as the number of elements to take.
 597 genericTake             :: (Integral i) => i -> [a] -> [a]
 598 genericTake n _ | n <= 0 = []
 599 genericTake _ []        =  []
 600 genericTake n (x:xs)    =  x : genericTake (n-1) xs
 601
 602 -- | The 'genericDrop' function is an overloaded version of 'drop', which
 603 -- accepts any 'Integral' value as the number of elements to drop.
 604 genericDrop             :: (Integral i) => i -> [a] -> [a]
 605 genericDrop n xs | n <= 0 = xs
 606 genericDrop _ []        =  []
 607 genericDrop n (_:xs)    =  genericDrop (n-1) xs
 608
 609
 610 -- | The 'genericSplitAt' function is an overloaded version of 'splitAt', which
 611 -- accepts any 'Integral' value as the position at which to split.
 612 genericSplitAt          :: (Integral i) => i -> [b] -> ([b],[b])
 613 genericSplitAt n xs | n <= 0 =  ([],xs)
 614 genericSplitAt _ []     =  ([],[])
 615 genericSplitAt n (x:xs) =  (x:xs',xs'') where
 616     (xs',xs'') = genericSplitAt (n-1) xs
 617
 618 -- | The 'genericIndex' function is an overloaded version of '!!', which
 619 -- accepts any 'Integral' value as the index.
 620 genericIndex :: (Integral a) => [b] -> a -> b
 621 genericIndex (x:_)  0 = x
 622 genericIndex (_:xs) n
 623  | n > 0     = genericIndex xs (n-1)
 624  | otherwise = error "List.genericIndex: negative argument."
 625 genericIndex _ _      = error "List.genericIndex: index too large."
 626
 627 -- | The 'genericReplicate' function is an overloaded version of 'replicate',
 628 -- which accepts any 'Integral' value as the number of repetitions to make.
 629 genericReplicate        :: (Integral i) => i -> a -> [a]
 630 genericReplicate n x    =  genericTake n (repeat x)
 631
 632 -- | The 'zip4' function takes four lists and returns a list of
 633 -- quadruples, analogous to 'zip'.
 634 zip4                    :: [a] -> [b] -> [c] -> [d] -> [(a,b,c,d)]
 635 zip4                    =  zipWith4 (,,,)
 636
 637 -- | The 'zip5' function takes five lists and returns a list of
 638 -- five-tuples, analogous to 'zip'.
 639 zip5                    :: [a] -> [b] -> [c] -> [d] -> [e] -> [(a,b,c,d,e)]
 640 zip5                    =  zipWith5 (,,,,)
 641
 642 -- | The 'zip6' function takes six lists and returns a list of six-tuples,
 643 -- analogous to 'zip'.
 644 zip6                    :: [a] -> [b] -> [c] -> [d] -> [e] -> [f] ->
 645                               [(a,b,c,d,e,f)]
 646 zip6                    =  zipWith6 (,,,,,)
 647
 648 -- | The 'zip7' function takes seven lists and returns a list of
 649 -- seven-tuples, analogous to 'zip'.
 650 zip7                    :: [a] -> [b] -> [c] -> [d] -> [e] -> [f] ->
 651                               [g] -> [(a,b,c,d,e,f,g)]
 652 zip7                    =  zipWith7 (,,,,,,)
 653
 654 -- | The 'zipWith4' function takes a function which combines four
 655 -- elements, as well as four lists and returns a list of their point-wise
 656 -- combination, analogous to 'zipWith'.
 657 zipWith4                :: (a->b->c->d->e) -> [a]->[b]->[c]->[d]->[e]
 658 zipWith4 z (a:as) (b:bs) (c:cs) (d:ds)
 659                         =  z a b c d : zipWith4 z as bs cs ds
 660 zipWith4 _ _ _ _ _      =  []
 661
 662 -- | The 'zipWith5' function takes a function which combines five
 663 -- elements, as well as five lists and returns a list of their point-wise
 664 -- combination, analogous to 'zipWith'.
 665 zipWith5                :: (a->b->c->d->e->f) ->
 666                            [a]->[b]->[c]->[d]->[e]->[f]
 667 zipWith5 z (a:as) (b:bs) (c:cs) (d:ds) (e:es)
 668                         =  z a b c d e : zipWith5 z as bs cs ds es
 669 zipWith5 _ _ _ _ _ _    = []
 670
 671 -- | The 'zipWith6' function takes a function which combines six
 672 -- elements, as well as six lists and returns a list of their point-wise
 673 -- combination, analogous to 'zipWith'.
 674 zipWith6                :: (a->b->c->d->e->f->g) ->
 675                            [a]->[b]->[c]->[d]->[e]->[f]->[g]
 676 zipWith6 z (a:as) (b:bs) (c:cs) (d:ds) (e:es) (f:fs)
 677                         =  z a b c d e f : zipWith6 z as bs cs ds es fs
 678 zipWith6 _ _ _ _ _ _ _  = []
 679
 680 -- | The 'zipWith7' function takes a function which combines seven
 681 -- elements, as well as seven lists and returns a list of their point-wise
 682 -- combination, analogous to 'zipWith'.
 683 zipWith7                :: (a->b->c->d->e->f->g->h) ->
 684                            [a]->[b]->[c]->[d]->[e]->[f]->[g]->[h]
 685 zipWith7 z (a:as) (b:bs) (c:cs) (d:ds) (e:es) (f:fs) (g:gs)
 686                    =  z a b c d e f g : zipWith7 z as bs cs ds es fs gs
 687 zipWith7 _ _ _ _ _ _ _ _ = []
 688
 689 -- | The 'unzip4' function takes a list of quadruples and returns four
 690 -- lists, analogous to 'unzip'.
 691 unzip4                  :: [(a,b,c,d)] -> ([a],[b],[c],[d])
 692 unzip4                  =  foldr (\(a,b,c,d) ~(as,bs,cs,ds) ->
 693                                         (a:as,b:bs,c:cs,d:ds))
 694                                  ([],[],[],[])
 695
 696 -- | The 'unzip5' function takes a list of five-tuples and returns five
 697 -- lists, analogous to 'unzip'.
 698 unzip5                  :: [(a,b,c,d,e)] -> ([a],[b],[c],[d],[e])
 699 unzip5                  =  foldr (\(a,b,c,d,e) ~(as,bs,cs,ds,es) ->
 700                                         (a:as,b:bs,c:cs,d:ds,e:es))
 701                                  ([],[],[],[],[])
 702
 703 -- | The 'unzip6' function takes a list of six-tuples and returns six
 704 -- lists, analogous to 'unzip'.
 705 unzip6                  :: [(a,b,c,d,e,f)] -> ([a],[b],[c],[d],[e],[f])
 706 unzip6                  =  foldr (\(a,b,c,d,e,f) ~(as,bs,cs,ds,es,fs) ->
 707                                         (a:as,b:bs,c:cs,d:ds,e:es,f:fs))
 708                                  ([],[],[],[],[],[])
 709
 710 -- | The 'unzip7' function takes a list of seven-tuples and returns
 711 -- seven lists, analogous to 'unzip'.
 712 unzip7          :: [(a,b,c,d,e,f,g)] -> ([a],[b],[c],[d],[e],[f],[g])
 713 unzip7          =  foldr (\(a,b,c,d,e,f,g) ~(as,bs,cs,ds,es,fs,gs) ->
 714                                 (a:as,b:bs,c:cs,d:ds,e:es,f:fs,g:gs))
 715                          ([],[],[],[],[],[],[])
 716
 717
 718 -- | The 'deleteFirstsBy' function takes a predicate and two lists and
 719 -- returns the first list with the first occurrence of each element of
 720 -- the second list removed.
 721 deleteFirstsBy          :: (a -> a -> Bool) -> [a] -> [a] -> [a]
 722 deleteFirstsBy eq       =  foldl (flip (deleteBy eq))
 723
 724 -- | The 'group' function takes a list and returns a list of lists such
 725 -- that the concatenation of the result is equal to the argument.  Moreover,
 726 -- each sublist in the result contains only equal elements.  For example,
 727 --
 728 -- > group "Mississippi" = ["M","i","ss","i","ss","i","pp","i"]
 729 --
 730 -- It is a special case of 'groupBy', which allows the programmer to supply
 731 -- their own equality test.
 732 group                   :: Eq a => [a] -> [[a]]
 733 group                   =  groupBy (==)
 734
 735 -- | The 'groupBy' function is the non-overloaded version of 'group'.
 736 groupBy                 :: (a -> a -> Bool) -> [a] -> [[a]]
 737 groupBy _  []           =  []
 738 groupBy eq (x:xs)       =  (x:ys) : groupBy eq zs
 739                            where (ys,zs) = span (eq x) xs
 740
 741 -- | The 'inits' function returns all initial segments of the argument,
 742 -- shortest first.  For example,
 743 --
 744 -- > inits "abc" == ["","a","ab","abc"]
 745 --
 746 inits                   :: [a] -> [[a]]
 747 inits []                =  [[]]
 748 inits (x:xs)            =  [[]] ++ map (x:) (inits xs)
 749
 750 -- | The 'tails' function returns all final segments of the argument,
 751 -- longest first.  For example,
 752 --
 753 -- > tails "abc" == ["abc", "bc", "c",""]
 754 --
 755 tails                   :: [a] -> [[a]]
 756 tails []                =  [[]]
 757 tails xxs@(_:xs)        =  xxs : tails xs
 758
 759
 760 -- | The 'subsequences' function returns the list of all subsequences of the argument.
 761 --
 762 -- > subsequences "abc" == ["","a","b","ab","c","ac","bc","abc"]
 763 subsequences            :: [a] -> [[a]]
 764 subsequences xs         =  [] : nonEmptySubsequences xs
 765
 766 -- | The 'nonEmptySubsequences' function returns the list of all subsequences of the argument,
 767 --   except for the empty list.
 768 --
 769 -- > nonEmptySubsequences "abc" == ["a","b","ab","c","ac","bc","abc"]
 770 nonEmptySubsequences         :: [a] -> [[a]]
 771 nonEmptySubsequences []      =  []
 772 nonEmptySubsequences (x:xs)  =  [x] : foldr f [] (nonEmptySubsequences xs)
 773   where f ys r = ys : (x : ys) : r
 774
 775
 776 -- | The 'permutations' function returns the list of all permutations of the argument.
 777 --
 778 -- > permutations "abc" == ["abc","bac","cba","bca","cab","acb"]
 779 permutations            :: [a] -> [[a]]
 780 permutations xs0        =  xs0 : perms xs0 []
 781   where
 782     perms []     _  = []
 783     perms (t:ts) is = foldr interleave (perms ts (t:is)) (permutations is)
 784       where interleave    xs     r = let (_,zs) = interleave' id xs r in zs
 785             interleave' _ []     r = (ts, r)
 786             interleave' f (y:ys) r = let (us,zs) = interleave' (f . (y:)) ys r
 787                                      in  (y:us, f (t:y:us) : zs)
 788
 789
 790 ------------------------------------------------------------------------------
 791 -- Quick Sort algorithm taken from HBC's QSort library.
 792
 793 -- | The 'sort' function implements a stable sorting algorithm.
 794 -- It is a special case of 'sortBy', which allows the programmer to supply
 795 -- their own comparison function.
 796 sort :: (Ord a) => [a] -> [a]
 797
 798 -- | The 'sortBy' function is the non-overloaded version of 'sort'.
 799 sortBy :: (a -> a -> Ordering) -> [a] -> [a]
 800
 801 #ifdef USE_REPORT_PRELUDE
 802 sort = sortBy compare
 803 sortBy cmp = foldr (insertBy cmp) []
 804 #else
 805
 806 {-
 807 GHC's mergesort replaced by a better implementation, 24/12/2009.
 808 This code originally contributed to the nhc12 compiler by Thomas Nordin
 809 in 2002.  Rumoured to have been based on code by Lennart Augustsson, e.g.
 810     http://www.mail-archive.com/haskell@haskell.org/msg01822.html
 811 and possibly to bear similarities to a 1982 paper by Richard O'Keefe:
 812 "A smooth applicative merge sort".
 813
 814 Benchmarks show it to be often 2x the speed of the previous implementation.
 815 Fixes ticket http://hackage.haskell.org/trac/ghc/ticket/2143
 816 -}
 817
 818 sort = sortBy compare
 819 sortBy cmp = mergeAll . sequences
 820   where
 821     sequences (a:b:xs)
 822       | a `cmp` b == GT = descending b [a]  xs
 823       | otherwise       = ascending  b (a:) xs
 824     sequences xs = [xs]
 825
 826     descending a as (b:bs)
 827       | a `cmp` b == GT = descending b (a:as) bs
 828     descending a as bs  = (a:as): sequences bs
 829
 830     ascending a as (b:bs)
 831       | a `cmp` b /= GT = ascending b (\ys -> as (a:ys)) bs
 832     ascending a as bs   = as [a]: sequences bs
 833
 834     mergeAll [x] = x
 835     mergeAll xs  = mergeAll (mergePairs xs)
 836
 837     mergePairs (a:b:xs) = merge a b: mergePairs xs
 838     mergePairs xs       = xs
 839
 840     merge as@(a:as') bs@(b:bs')
 841       | a `cmp` b == GT = b:merge as  bs'
 842       | otherwise       = a:merge as' bs
 843     merge [] bs         = bs
 844     merge as []         = as
 845
 846 {-
 847 sortBy cmp l = mergesort cmp l
 848 sort l = mergesort compare l
 849
 850 Quicksort replaced by mergesort, 14/5/2002.
 851
 852 From: Ian Lynagh <igloo@earth.li>
 853
 854 I am curious as to why the List.sort implementation in GHC is a
 855 quicksort algorithm rather than an algorithm that guarantees n log n
 856 time in the worst case? I have attached a mergesort implementation along
 857 with a few scripts to time it's performance, the results of which are
 858 shown below (* means it didn't finish successfully - in all cases this
 859 was due to a stack overflow).
 860
 861 If I heap profile the random_list case with only 10000 then I see
 862 random_list peaks at using about 2.5M of memory, whereas in the same
 863 program using List.sort it uses only 100k.
 864
 865 Input style     Input length     Sort data     Sort alg    User time
 866 stdin           10000            random_list   sort        2.82
 867 stdin           10000            random_list   mergesort   2.96
 868 stdin           10000            sorted        sort        31.37
 869 stdin           10000            sorted        mergesort   1.90
 870 stdin           10000            revsorted     sort        31.21
 871 stdin           10000            revsorted     mergesort   1.88
 872 stdin           100000           random_list   sort        *
 873 stdin           100000           random_list   mergesort   *
 874 stdin           100000           sorted        sort        *
 875 stdin           100000           sorted        mergesort   *
 876 stdin           100000           revsorted     sort        *
 877 stdin           100000           revsorted     mergesort   *
 878 func            10000            random_list   sort        0.31
 879 func            10000            random_list   mergesort   0.91
 880 func            10000            sorted        sort        19.09
 881 func            10000            sorted        mergesort   0.15
 882 func            10000            revsorted     sort        19.17
 883 func            10000            revsorted     mergesort   0.16
 884 func            100000           random_list   sort        3.85
 885 func            100000           random_list   mergesort   *
 886 func            100000           sorted        sort        5831.47
 887 func            100000           sorted        mergesort   2.23
 888 func            100000           revsorted     sort        5872.34
 889 func            100000           revsorted     mergesort   2.24
 890
 891 mergesort :: (a -> a -> Ordering) -> [a] -> [a]
 892 mergesort cmp = mergesort' cmp . map wrap
 893
 894 mergesort' :: (a -> a -> Ordering) -> [[a]] -> [a]
 895 mergesort' _   [] = []
 896 mergesort' _   [xs] = xs
 897 mergesort' cmp xss = mergesort' cmp (merge_pairs cmp xss)
 898
 899 merge_pairs :: (a -> a -> Ordering) -> [[a]] -> [[a]]
 900 merge_pairs _   [] = []
 901 merge_pairs _   [xs] = [xs]
 902 merge_pairs cmp (xs:ys:xss) = merge cmp xs ys : merge_pairs cmp xss
 903
 904 merge :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
 905 merge _   [] ys = ys
 906 merge _   xs [] = xs
 907 merge cmp (x:xs) (y:ys)
 908  = case x `cmp` y of
 909         GT -> y : merge cmp (x:xs)   ys
 910         _  -> x : merge cmp    xs (y:ys)
 911
 912 wrap :: a -> [a]
 913 wrap x = [x]
 914
 915
 916
 917 OLDER: qsort version
 918
 919 -- qsort is stable and does not concatenate.
 920 qsort :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
 921 qsort _   []     r = r
 922 qsort _   [x]    r = x:r
 923 qsort cmp (x:xs) r = qpart cmp x xs [] [] r
 924
 925 -- qpart partitions and sorts the sublists
 926 qpart :: (a -> a -> Ordering) -> a -> [a] -> [a] -> [a] -> [a] -> [a]
 927 qpart cmp x [] rlt rge r =
 928     -- rlt and rge are in reverse order and must be sorted with an
 929     -- anti-stable sorting
 930     rqsort cmp rlt (x:rqsort cmp rge r)
 931 qpart cmp x (y:ys) rlt rge r =
 932     case cmp x y of
 933         GT -> qpart cmp x ys (y:rlt) rge r
 934         _  -> qpart cmp x ys rlt (y:rge) r
 935
 936 -- rqsort is as qsort but anti-stable, i.e. reverses equal elements
 937 rqsort :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
 938 rqsort _   []     r = r
 939 rqsort _   [x]    r = x:r
 940 rqsort cmp (x:xs) r = rqpart cmp x xs [] [] r
 941
 942 rqpart :: (a -> a -> Ordering) -> a -> [a] -> [a] -> [a] -> [a] -> [a]
 943 rqpart cmp x [] rle rgt r =
 944     qsort cmp rle (x:qsort cmp rgt r)
 945 rqpart cmp x (y:ys) rle rgt r =
 946     case cmp y x of
 947         GT -> rqpart cmp x ys rle (y:rgt) r
 948         _  -> rqpart cmp x ys (y:rle) rgt r
 949 -}
 950
 951 #endif /* USE_REPORT_PRELUDE */
 952
 953 -- | The 'unfoldr' function is a \`dual\' to 'foldr': while 'foldr'
 954 -- reduces a list to a summary value, 'unfoldr' builds a list from
 955 -- a seed value.  The function takes the element and returns 'Nothing'
 956 -- if it is done producing the list or returns 'Just' @(a,b)@, in which
 957 -- case, @a@ is a prepended to the list and @b@ is used as the next
 958 -- element in a recursive call.  For example,
 959 --
 960 -- > iterate f == unfoldr (\x -> Just (x, f x))
 961 --
 962 -- In some cases, 'unfoldr' can undo a 'foldr' operation:
 963 --
 964 -- > unfoldr f' (foldr f z xs) == xs
 965 --
 966 -- if the following holds:
 967 --
 968 -- > f' (f x y) = Just (x,y)
 969 -- > f' z       = Nothing
 970 --
 971 -- A simple use of unfoldr:
 972 --
 973 -- > unfoldr (\b -> if b == 0 then Nothing else Just (b, b-1)) 10
 974 -- >  [10,9,8,7,6,5,4,3,2,1]
 975 --
 976 unfoldr      :: (b -> Maybe (a, b)) -> b -> [a]
 977 unfoldr f b  =
 978   case f b of
 979    Just (a,new_b) -> a : unfoldr f new_b
 980    Nothing        -> []
 981
 982 -- -----------------------------------------------------------------------------
 983
 984 -- | A strict version of 'foldl'.
 985 foldl'           :: (a -> b -> a) -> a -> [b] -> a
 986 #ifdef __GLASGOW_HASKELL__
 987 foldl' f z0 xs0 = lgo z0 xs0
 988     where lgo z []     = z
 989           lgo z (x:xs) = let z' = f z x in z' `seq` lgo z' xs
 990 #else
 991 foldl' f a []     = a
 992 foldl' f a (x:xs) = let a' = f a x in a' `seq` foldl' f a' xs
 993 #endif
 994
 995 #ifdef __GLASGOW_HASKELL__
 996 -- | 'foldl1' is a variant of 'foldl' that has no starting value argument,
 997 -- and thus must be applied to non-empty lists.
 998 foldl1                  :: (a -> a -> a) -> [a] -> a
 999 foldl1 f (x:xs)         =  foldl f x xs
1000 foldl1 _ []             =  errorEmptyList "foldl1"
1001 #endif /* __GLASGOW_HASKELL__ */
1002
1003 -- | A strict version of 'foldl1'
1004 foldl1'                  :: (a -> a -> a) -> [a] -> a
1005 foldl1' f (x:xs)         =  foldl' f x xs
1006 foldl1' _ []             =  errorEmptyList "foldl1'"
1007
1008 #ifdef __GLASGOW_HASKELL__
1009 -- -----------------------------------------------------------------------------
1010 -- List sum and product
1011
1012 {-# SPECIALISE sum     :: [Int] -> Int #-}
1013 {-# SPECIALISE sum     :: [Integer] -> Integer #-}
1014 {-# SPECIALISE product :: [Int] -> Int #-}
1015 {-# SPECIALISE product :: [Integer] -> Integer #-}
1016 -- | The 'sum' function computes the sum of a finite list of numbers.
1017 sum                     :: (Num a) => [a] -> a
1018 -- | The 'product' function computes the product of a finite list of numbers.
1019 product                 :: (Num a) => [a] -> a
1020 #ifdef USE_REPORT_PRELUDE
1021 sum                     =  foldl (+) 0
1022 product                 =  foldl (*) 1
1023 #else
1024 sum     l       = sum' l 0
1025   where
1026     sum' []     a = a
1027     sum' (x:xs) a = sum' xs (a+x)
1028 product l       = prod l 1
1029   where
1030     prod []     a = a
1031     prod (x:xs) a = prod xs (a*x)
1032 #endif
1033
1034 -- -----------------------------------------------------------------------------
1035 -- Functions on strings
1036
1037 -- | 'lines' breaks a string up into a list of strings at newline
1038 -- characters.  The resulting strings do not contain newlines.
1039 lines                   :: String -> [String]
1040 lines ""                =  []
1041 #ifdef __GLASGOW_HASKELL__
1042 -- Somehow GHC doesn't detect the selector thunks in the below code,
1043 -- so s' keeps a reference to the first line via the pair and we have
1044 -- a space leak (cf. #4334).
1045 -- So we need to make GHC see the selector thunks with a trick.
1046 lines s                 =  cons (case break (== '\n') s of
1047                                     (l, s') -> (l, case s' of
1048                                                     []      -> []
1049                                                     _:s''   -> lines s''))
1050   where
1051     cons ~(h, t)        =  h : t
1052 #else
1053 lines s                 =  let (l, s') = break (== '\n') s
1054                            in  l : case s' of
1055                                         []      -> []
1056                                         (_:s'') -> lines s''
1057 #endif
1058
1059 -- | 'unlines' is an inverse operation to 'lines'.
1060 -- It joins lines, after appending a terminating newline to each.
1061 unlines                 :: [String] -> String
1062 #ifdef USE_REPORT_PRELUDE
1063 unlines                 =  concatMap (++ "\n")
1064 #else
1065 -- HBC version (stolen)
1066 -- here's a more efficient version
1067 unlines [] = []
1068 unlines (l:ls) = l ++ '\n' : unlines ls
1069 #endif
1070
1071 -- | 'words' breaks a string up into a list of words, which were delimited
1072 -- by white space.
1073 words                   :: String -> [String]
1074 words s                 =  case dropWhile {-partain:Char.-}isSpace s of
1075                                 "" -> []
1076                                 s' -> w : words s''
1077                                       where (w, s'') =
1078                                              break {-partain:Char.-}isSpace s'
1079
1080 -- | 'unwords' is an inverse operation to 'words'.
1081 -- It joins words with separating spaces.
1082 unwords                 :: [String] -> String
1083 #ifdef USE_REPORT_PRELUDE
1084 unwords []              =  ""
1085 unwords ws              =  foldr1 (\w s -> w ++ ' ':s) ws
1086 #else
1087 -- HBC version (stolen)
1088 -- here's a more efficient version
1089 unwords []              =  ""
1090 unwords [w]             = w
1091 unwords (w:ws)          = w ++ ' ' : unwords ws
1092 #endif
1093
1094 #else  /* !__GLASGOW_HASKELL__ */
1095
1096 errorEmptyList :: String -> a
1097 errorEmptyList fun =
1098   error ("Prelude." ++ fun ++ ": empty list")
1099
1100 #endif /* !__GLASGOW_HASKELL__ */