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