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