Data/List.hs

   1 {-# OPTIONS_GHC -XNoImplicitPrelude #-}
   2 -----------------------------------------------------------------------------
   3 -- |
   4 -- Module      :  Data.List
   5 -- Copyright   :  (c) The University of Glasgow 2001
   6 -- License     :  BSD-style (see the file libraries/base/LICENSE)
   7 --
   8 -- Maintainer  :  libraries@haskell.org
   9 -- Stability   :  stable
  10 -- Portability :  portable
  11 --
  12 -- Operations on lists.
  13 --
  14 -----------------------------------------------------------------------------
  15
  16 module Data.List
  17    (
  18 #ifdef __NHC__
  19      [] (..)
  20    ,
  21 #endif
  22
  23    -- * Basic functions
  24
  25      (++)              -- :: [a] -> [a] -> [a]
  26    , head              -- :: [a] -> a
  27    , last              -- :: [a] -> a
  28    , tail              -- :: [a] -> [a]
  29    , init              -- :: [a] -> [a]
  30    , null              -- :: [a] -> Bool
  31    , length            -- :: [a] -> Int
  32
  33    -- * List transformations
  34    , map               -- :: (a -> b) -> [a] -> [b]
  35    , reverse           -- :: [a] -> [a]
  36
  37    , intersperse       -- :: a -> [a] -> [a]
  38    , intercalate       -- :: [a] -> [[a]] -> [a]
  39    , transpose         -- :: [[a]] -> [[a]]
  40
  41    , subsequences      -- :: [a] -> [[a]]
  42    , permutations      -- :: [a] -> [[a]]
  43
  44    -- * Reducing lists (folds)
  45
  46    , foldl             -- :: (a -> b -> a) -> a -> [b] -> a
  47    , foldl'            -- :: (a -> b -> a) -> a -> [b] -> a
  48    , foldl1            -- :: (a -> a -> a) -> [a] -> a
  49    , foldl1'           -- :: (a -> a -> a) -> [a] -> a
  50    , foldr             -- :: (a -> b -> b) -> b -> [a] -> b
  51    , foldr1            -- :: (a -> a -> a) -> [a] -> a
  52
  53    -- ** Special folds
  54
  55    , concat            -- :: [[a]] -> [a]
  56    , concatMap         -- :: (a -> [b]) -> [a] -> [b]
  57    , and               -- :: [Bool] -> Bool
  58    , or                -- :: [Bool] -> Bool
  59    , any               -- :: (a -> Bool) -> [a] -> Bool
  60    , all               -- :: (a -> Bool) -> [a] -> Bool
  61    , sum               -- :: (Num a) => [a] -> a
  62    , product           -- :: (Num a) => [a] -> a
  63    , maximum           -- :: (Ord a) => [a] -> a
  64    , minimum           -- :: (Ord a) => [a] -> a
  65
  66    -- * Building lists
  67
  68    -- ** Scans
  69    , scanl             -- :: (a -> b -> a) -> a -> [b] -> [a]
  70    , scanl1            -- :: (a -> a -> a) -> [a] -> [a]
  71    , scanr             -- :: (a -> b -> b) -> b -> [a] -> [b]
  72    , scanr1            -- :: (a -> a -> a) -> [a] -> [a]
  73
  74    -- ** Accumulating maps
  75    , mapAccumL         -- :: (a -> b -> (a,c)) -> a -> [b] -> (a,[c])
  76    , mapAccumR         -- :: (a -> b -> (a,c)) -> a -> [b] -> (a,[c])
  77
  78    -- ** Infinite lists
  79    , iterate           -- :: (a -> a) -> a -> [a]
  80    , repeat            -- :: a -> [a]
  81    , replicate         -- :: Int -> a -> [a]
  82    , cycle             -- :: [a] -> [a]
  83
  84    -- ** Unfolding
  85    , unfoldr           -- :: (b -> Maybe (a, b)) -> b -> [a]
  86
  87    -- * Sublists
  88
  89    -- ** Extracting sublists
  90    , take              -- :: Int -> [a] -> [a]
  91    , drop              -- :: Int -> [a] -> [a]
  92    , splitAt           -- :: Int -> [a] -> ([a], [a])
  93
  94    , takeWhile         -- :: (a -> Bool) -> [a] -> [a]
  95    , dropWhile         -- :: (a -> Bool) -> [a] -> [a]
  96    , span              -- :: (a -> Bool) -> [a] -> ([a], [a])
  97    , break             -- :: (a -> Bool) -> [a] -> ([a], [a])
  98
  99    , stripPrefix       -- :: Eq a => [a] -> [a] -> Maybe [a]
 100
 101    , group             -- :: Eq a => [a] -> [[a]]
 102
 103    , inits             -- :: [a] -> [[a]]
 104    , tails             -- :: [a] -> [[a]]
 105
 106    -- ** Predicates
 107    , isPrefixOf        -- :: (Eq a) => [a] -> [a] -> Bool
 108    , isSuffixOf        -- :: (Eq a) => [a] -> [a] -> Bool
 109    , isInfixOf         -- :: (Eq a) => [a] -> [a] -> Bool
 110
 111    -- * Searching lists
 112
 113    -- ** Searching by equality
 114    , elem              -- :: a -> [a] -> Bool
 115    , notElem           -- :: a -> [a] -> Bool
 116    , lookup            -- :: (Eq a) => a -> [(a,b)] -> Maybe b
 117
 118    -- ** Searching with a predicate
 119    , find              -- :: (a -> Bool) -> [a] -> Maybe a
 120    , filter            -- :: (a -> Bool) -> [a] -> [a]
 121    , partition         -- :: (a -> Bool) -> [a] -> ([a], [a])
 122
 123    -- * Indexing lists
 124    -- | These functions treat a list @xs@ as a indexed collection,
 125    -- with indices ranging from 0 to @'length' xs - 1@.
 126
 127    , (!!)              -- :: [a] -> Int -> a
 128
 129    , elemIndex         -- :: (Eq a) => a -> [a] -> Maybe Int
 130    , elemIndices       -- :: (Eq a) => a -> [a] -> [Int]
 131
 132    , findIndex         -- :: (a -> Bool) -> [a] -> Maybe Int
 133    , findIndices       -- :: (a -> Bool) -> [a] -> [Int]
 134
 135    -- * Zipping and unzipping lists
 136
 137    , zip               -- :: [a] -> [b] -> [(a,b)]
 138    , zip3
 139    , zip4, zip5, zip6, zip7
 140
 141    , zipWith           -- :: (a -> b -> c) -> [a] -> [b] -> [c]
 142    , zipWith3
 143    , zipWith4, zipWith5, zipWith6, zipWith7
 144
 145    , unzip             -- :: [(a,b)] -> ([a],[b])
 146    , unzip3
 147    , unzip4, unzip5, unzip6, unzip7
 148
 149    -- * Special lists
 150
 151    -- ** Functions on strings
 152    , lines             -- :: String   -> [String]
 153    , words             -- :: String   -> [String]
 154    , unlines           -- :: [String] -> String
 155    , unwords           -- :: [String] -> String
 156
 157    -- ** \"Set\" operations
 158
 159    , nub               -- :: (Eq a) => [a] -> [a]
 160
 161    , delete            -- :: (Eq a) => a -> [a] -> [a]
 162    , (\\)              -- :: (Eq a) => [a] -> [a] -> [a]
 163
 164    , union             -- :: (Eq a) => [a] -> [a] -> [a]
 165    , intersect         -- :: (Eq a) => [a] -> [a] -> [a]
 166
 167    -- ** Ordered lists
 168    , sort              -- :: (Ord a) => [a] -> [a]
 169    , insert            -- :: (Ord a) => a -> [a] -> [a]
 170
 171    -- * Generalized functions
 172
 173    -- ** The \"@By@\" operations
 174    -- | By convention, overloaded functions have a non-overloaded
 175    -- counterpart whose name is suffixed with \`@By@\'.
 176    --
 177    -- It is often convenient to use these functions together with
 178    -- 'Data.Function.on', for instance @'sortBy' ('compare'
 179    -- \`on\` 'fst')@.
 180
 181    -- *** User-supplied equality (replacing an @Eq@ context)
 182    -- | The predicate is assumed to define an equivalence.
 183    , nubBy             -- :: (a -> a -> Bool) -> [a] -> [a]
 184    , deleteBy          -- :: (a -> a -> Bool) -> a -> [a] -> [a]
 185    , deleteFirstsBy    -- :: (a -> a -> Bool) -> [a] -> [a] -> [a]
 186    , unionBy           -- :: (a -> a -> Bool) -> [a] -> [a] -> [a]
 187    , intersectBy       -- :: (a -> a -> Bool) -> [a] -> [a] -> [a]
 188    , groupBy           -- :: (a -> a -> Bool) -> [a] -> [[a]]
 189
 190    -- *** User-supplied comparison (replacing an @Ord@ context)
 191    -- | The function is assumed to define a total ordering.
 192    , sortBy            -- :: (a -> a -> Ordering) -> [a] -> [a]
 193    , insertBy          -- :: (a -> a -> Ordering) -> a -> [a] -> [a]
 194    , maximumBy         -- :: (a -> a -> Ordering) -> [a] -> a
 195    , minimumBy         -- :: (a -> a -> Ordering) -> [a] -> a
 196
 197    -- ** The \"@generic@\" operations
 198    -- | The prefix \`@generic@\' indicates an overloaded function that
 199    -- is a generalized version of a "Prelude" function.
 200
 201    , genericLength     -- :: (Integral a) => [b] -> a
 202    , genericTake       -- :: (Integral a) => a -> [b] -> [b]
 203    , genericDrop       -- :: (Integral a) => a -> [b] -> [b]
 204    , genericSplitAt    -- :: (Integral a) => a -> [b] -> ([b], [b])
 205    , genericIndex      -- :: (Integral a) => [b] -> a -> b
 206    , genericReplicate  -- :: (Integral a) => a -> b -> [b]
 207
 208    ) where
 209
 210 #ifdef __NHC__
 211 import Prelude
 212 #endif
 213
 214 import Data.Maybe
 215 import Data.Char        ( isSpace )
 216
 217 #ifdef __GLASGOW_HASKELL__
 218 import GHC.Num
 219 import GHC.Real
 220 import GHC.List
 221 import GHC.Base
 222 #endif
 223
 224 infix 5 \\ -- comment to fool cpp
 225
 226 -- -----------------------------------------------------------------------------
 227 -- List functions
 228
 229 -- | The 'stripPrefix' function drops the given prefix from a list.
 230 -- It returns 'Nothing' if the list did not start with the prefix
 231 -- given, or 'Just' the list after the prefix, if it does.
 232 --
 233 -- > stripPrefix "foo" "foobar" -> Just "bar"
 234 -- > stripPrefix "foo" "foo" -> Just ""
 235 -- > stripPrefix "foo" "barfoo" -> Nothing
 236 -- > stripPrefix "foo" "barfoobaz" -> Nothing
 237 stripPrefix :: Eq a => [a] -> [a] -> Maybe [a]
 238 stripPrefix [] ys = Just ys
 239 stripPrefix (x:xs) (y:ys)
 240  | x == y = stripPrefix xs ys
 241 stripPrefix _ _ = Nothing
 242
 243 -- | The 'elemIndex' function returns the index of the first element
 244 -- in the given list which is equal (by '==') to the query element,
 245 -- or 'Nothing' if there is no such element.
 246 elemIndex       :: Eq a => a -> [a] -> Maybe Int
 247 elemIndex x     = findIndex (x==)
 248
 249 -- | The 'elemIndices' function extends 'elemIndex', by returning the
 250 -- indices of all elements equal to the query element, in ascending order.
 251 elemIndices     :: Eq a => a -> [a] -> [Int]
 252 elemIndices x   = findIndices (x==)
 253
 254 -- | The 'find' function takes a predicate and a list and returns the
 255 -- first element in the list matching the predicate, or 'Nothing' if
 256 -- there is no such element.
 257 find            :: (a -> Bool) -> [a] -> Maybe a
 258 find p          = listToMaybe . filter p
 259
 260 -- | The 'findIndex' function takes a predicate and a list and returns
 261 -- the index of the first element in the list satisfying the predicate,
 262 -- or 'Nothing' if there is no such element.
 263 findIndex       :: (a -> Bool) -> [a] -> Maybe Int
 264 findIndex p     = listToMaybe . findIndices p
 265
 266 -- | The 'findIndices' function extends 'findIndex', by returning the
 267 -- indices of all elements satisfying the predicate, in ascending order.
 268 findIndices      :: (a -> Bool) -> [a] -> [Int]
 269
 270 #if defined(USE_REPORT_PRELUDE) || !defined(__GLASGOW_HASKELL__)
 271 findIndices p xs = [ i | (x,i) <- zip xs [0..], p x]
 272 #else
 273 -- Efficient definition
 274 findIndices p ls = loop 0# ls
 275                  where
 276                    loop _ [] = []
 277                    loop n (x:xs) | p x       = I# n : loop (n +# 1#) xs
 278                                  | otherwise = loop (n +# 1#) xs
 279 #endif  /* USE_REPORT_PRELUDE */
 280
 281 -- | The 'isPrefixOf' function takes two lists and returns 'True'
 282 -- iff the first list is a prefix of the second.
 283 isPrefixOf              :: (Eq a) => [a] -> [a] -> Bool
 284 isPrefixOf [] _         =  True
 285 isPrefixOf _  []        =  False
 286 isPrefixOf (x:xs) (y:ys)=  x == y && isPrefixOf xs ys
 287
 288 -- | The 'isSuffixOf' function takes two lists and returns 'True'
 289 -- iff the first list is a suffix of the second.
 290 -- Both lists must be finite.
 291 isSuffixOf              :: (Eq a) => [a] -> [a] -> Bool
 292 isSuffixOf x y          =  reverse x `isPrefixOf` reverse y
 293
 294 -- | The 'isInfixOf' function takes two lists and returns 'True'
 295 -- iff the first list is contained, wholly and intact,
 296 -- anywhere within the second.
 297 --
 298 -- Example:
 299 --
 300 -- >isInfixOf "Haskell" "I really like Haskell." -> True
 301 -- >isInfixOf "Ial" "I really like Haskell." -> False
 302 isInfixOf               :: (Eq a) => [a] -> [a] -> Bool
 303 isInfixOf needle haystack = any (isPrefixOf needle) (tails haystack)
 304
 305 -- | The 'nub' function removes duplicate elements from a list.
 306 -- In particular, it keeps only the first occurrence of each element.
 307 -- (The name 'nub' means \`essence\'.)
 308 -- It is a special case of 'nubBy', which allows the programmer to supply
 309 -- their own equality test.
 310 nub                     :: (Eq a) => [a] -> [a]
 311 #ifdef USE_REPORT_PRELUDE
 312 nub                     =  nubBy (==)
 313 #else
 314 -- stolen from HBC
 315 nub l                   = nub' l []             -- '
 316   where
 317     nub' [] _           = []                    -- '
 318     nub' (x:xs) ls                              -- '
 319         | x `elem` ls   = nub' xs ls            -- '
 320         | otherwise     = x : nub' xs (x:ls)    -- '
 321 #endif
 322
 323 -- | The 'nubBy' function behaves just like 'nub', except it uses a
 324 -- user-supplied equality predicate instead of the overloaded '=='
 325 -- function.
 326 nubBy                   :: (a -> a -> Bool) -> [a] -> [a]
 327 #ifdef USE_REPORT_PRELUDE
 328 nubBy eq []             =  []
 329 nubBy eq (x:xs)         =  x : nubBy eq (filter (\ y -> not (eq x y)) xs)
 330 #else
 331 nubBy eq l              = nubBy' l []
 332   where
 333     nubBy' [] _         = []
 334     nubBy' (y:ys) xs
 335        | elem_by eq y xs = nubBy' ys xs
 336        | otherwise       = y : nubBy' ys (y:xs)
 337
 338 -- Not exported:
 339 -- Note that we keep the call to `eq` with arguments in the
 340 -- same order as in the reference implementation
 341 -- 'xs' is the list of things we've seen so far,
 342 -- 'y' is the potential new element
 343 elem_by :: (a -> a -> Bool) -> a -> [a] -> Bool
 344 elem_by _  _ []         =  False
 345 elem_by eq y (x:xs)     =  y `eq` x || elem_by eq y xs
 346 #endif
 347
 348
 349 -- | 'delete' @x@ removes the first occurrence of @x@ from its list argument.
 350 -- For example,
 351 --
 352 -- > delete 'a' "banana" == "bnana"
 353 --
 354 -- It is a special case of 'deleteBy', which allows the programmer to
 355 -- supply their own equality test.
 356
 357 delete                  :: (Eq a) => a -> [a] -> [a]
 358 delete                  =  deleteBy (==)
 359
 360 -- | The 'deleteBy' function behaves like 'delete', but takes a
 361 -- user-supplied equality predicate.
 362 deleteBy                :: (a -> a -> Bool) -> a -> [a] -> [a]
 363 deleteBy _  _ []        = []
 364 deleteBy eq x (y:ys)    = if x `eq` y then ys else y : deleteBy eq x ys
 365
 366 -- | The '\\' function is list difference ((non-associative).
 367 -- In the result of @xs@ '\\' @ys@, the first occurrence of each element of
 368 -- @ys@ in turn (if any) has been removed from @xs@.  Thus
 369 --
 370 -- > (xs ++ ys) \\ xs == ys.
 371 --
 372 -- It is a special case of 'deleteFirstsBy', which allows the programmer
 373 -- to supply their own equality test.
 374
 375 (\\)                    :: (Eq a) => [a] -> [a] -> [a]
 376 (\\)                    =  foldl (flip delete)
 377
 378 -- | The 'union' function returns the list union of the two lists.
 379 -- For example,
 380 --
 381 -- > "dog" `union` "cow" == "dogcw"
 382 --
 383 -- Duplicates, and elements of the first list, are removed from the
 384 -- the second list, but if the first list contains duplicates, so will
 385 -- the result.
 386 -- It is a special case of 'unionBy', which allows the programmer to supply
 387 -- their own equality test.
 388
 389 union                   :: (Eq a) => [a] -> [a] -> [a]
 390 union                   = unionBy (==)
 391
 392 -- | The 'unionBy' function is the non-overloaded version of 'union'.
 393 unionBy                 :: (a -> a -> Bool) -> [a] -> [a] -> [a]
 394 unionBy eq xs ys        =  xs ++ foldl (flip (deleteBy eq)) (nubBy eq ys) xs
 395
 396 -- | The 'intersect' function takes the list intersection of two lists.
 397 -- For example,
 398 --
 399 -- > [1,2,3,4] `intersect` [2,4,6,8] == [2,4]
 400 --
 401 -- If the first list contains duplicates, so will the result.
 402 --
 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 sortBy cmp l = mergesort cmp l
 797 sort l = mergesort compare l
 798
 799 {-
 800 Quicksort replaced by mergesort, 14/5/2002.
 801
 802 From: Ian Lynagh <igloo@earth.li>
 803
 804 I am curious as to why the List.sort implementation in GHC is a
 805 quicksort algorithm rather than an algorithm that guarantees n log n
 806 time in the worst case? I have attached a mergesort implementation along
 807 with a few scripts to time it's performance, the results of which are
 808 shown below (* means it didn't finish successfully - in all cases this
 809 was due to a stack overflow).
 810
 811 If I heap profile the random_list case with only 10000 then I see
 812 random_list peaks at using about 2.5M of memory, whereas in the same
 813 program using List.sort it uses only 100k.
 814
 815 Input style     Input length     Sort data     Sort alg    User time
 816 stdin           10000            random_list   sort        2.82
 817 stdin           10000            random_list   mergesort   2.96
 818 stdin           10000            sorted        sort        31.37
 819 stdin           10000            sorted        mergesort   1.90
 820 stdin           10000            revsorted     sort        31.21
 821 stdin           10000            revsorted     mergesort   1.88
 822 stdin           100000           random_list   sort        *
 823 stdin           100000           random_list   mergesort   *
 824 stdin           100000           sorted        sort        *
 825 stdin           100000           sorted        mergesort   *
 826 stdin           100000           revsorted     sort        *
 827 stdin           100000           revsorted     mergesort   *
 828 func            10000            random_list   sort        0.31
 829 func            10000            random_list   mergesort   0.91
 830 func            10000            sorted        sort        19.09
 831 func            10000            sorted        mergesort   0.15
 832 func            10000            revsorted     sort        19.17
 833 func            10000            revsorted     mergesort   0.16
 834 func            100000           random_list   sort        3.85
 835 func            100000           random_list   mergesort   *
 836 func            100000           sorted        sort        5831.47
 837 func            100000           sorted        mergesort   2.23
 838 func            100000           revsorted     sort        5872.34
 839 func            100000           revsorted     mergesort   2.24
 840 -}
 841
 842 mergesort :: (a -> a -> Ordering) -> [a] -> [a]
 843 mergesort cmp = mergesort' cmp . map wrap
 844
 845 mergesort' :: (a -> a -> Ordering) -> [[a]] -> [a]
 846 mergesort' _   [] = []
 847 mergesort' _   [xs] = xs
 848 mergesort' cmp xss = mergesort' cmp (merge_pairs cmp xss)
 849
 850 merge_pairs :: (a -> a -> Ordering) -> [[a]] -> [[a]]
 851 merge_pairs _   [] = []
 852 merge_pairs _   [xs] = [xs]
 853 merge_pairs cmp (xs:ys:xss) = merge cmp xs ys : merge_pairs cmp xss
 854
 855 merge :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
 856 merge _   [] ys = ys
 857 merge _   xs [] = xs
 858 merge cmp (x:xs) (y:ys)
 859  = case x `cmp` y of
 860         GT -> y : merge cmp (x:xs)   ys
 861         _  -> x : merge cmp    xs (y:ys)
 862
 863 wrap :: a -> [a]
 864 wrap x = [x]
 865
 866 {-
 867 OLD: qsort version
 868
 869 -- qsort is stable and does not concatenate.
 870 qsort :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
 871 qsort _   []     r = r
 872 qsort _   [x]    r = x:r
 873 qsort cmp (x:xs) r = qpart cmp x xs [] [] r
 874
 875 -- qpart partitions and sorts the sublists
 876 qpart :: (a -> a -> Ordering) -> a -> [a] -> [a] -> [a] -> [a] -> [a]
 877 qpart cmp x [] rlt rge r =
 878     -- rlt and rge are in reverse order and must be sorted with an
 879     -- anti-stable sorting
 880     rqsort cmp rlt (x:rqsort cmp rge r)
 881 qpart cmp x (y:ys) rlt rge r =
 882     case cmp x y of
 883         GT -> qpart cmp x ys (y:rlt) rge r
 884         _  -> qpart cmp x ys rlt (y:rge) r
 885
 886 -- rqsort is as qsort but anti-stable, i.e. reverses equal elements
 887 rqsort :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
 888 rqsort _   []     r = r
 889 rqsort _   [x]    r = x:r
 890 rqsort cmp (x:xs) r = rqpart cmp x xs [] [] r
 891
 892 rqpart :: (a -> a -> Ordering) -> a -> [a] -> [a] -> [a] -> [a] -> [a]
 893 rqpart cmp x [] rle rgt r =
 894     qsort cmp rle (x:qsort cmp rgt r)
 895 rqpart cmp x (y:ys) rle rgt r =
 896     case cmp y x of
 897         GT -> rqpart cmp x ys rle (y:rgt) r
 898         _  -> rqpart cmp x ys (y:rle) rgt r
 899 -}
 900
 901 #endif /* USE_REPORT_PRELUDE */
 902
 903 -- | The 'unfoldr' function is a \`dual\' to 'foldr': while 'foldr'
 904 -- reduces a list to a summary value, 'unfoldr' builds a list from
 905 -- a seed value.  The function takes the element and returns 'Nothing'
 906 -- if it is done producing the list or returns 'Just' @(a,b)@, in which
 907 -- case, @a@ is a prepended to the list and @b@ is used as the next
 908 -- element in a recursive call.  For example,
 909 --
 910 -- > iterate f == unfoldr (\x -> Just (x, f x))
 911 --
 912 -- In some cases, 'unfoldr' can undo a 'foldr' operation:
 913 --
 914 -- > unfoldr f' (foldr f z xs) == xs
 915 --
 916 -- if the following holds:
 917 --
 918 -- > f' (f x y) = Just (x,y)
 919 -- > f' z       = Nothing
 920 --
 921 -- A simple use of unfoldr:
 922 --
 923 -- > unfoldr (\b -> if b == 0 then Nothing else Just (b, b-1)) 10
 924 -- >  [10,9,8,7,6,5,4,3,2,1]
 925 --
 926 unfoldr      :: (b -> Maybe (a, b)) -> b -> [a]
 927 unfoldr f b  =
 928   case f b of
 929    Just (a,new_b) -> a : unfoldr f new_b
 930    Nothing        -> []
 931
 932 -- -----------------------------------------------------------------------------
 933
 934 -- | A strict version of 'foldl'.
 935 foldl'           :: (a -> b -> a) -> a -> [b] -> a
 936 #ifdef __GLASGOW_HASKELL__
 937 foldl' f z0 xs0 = lgo z0 xs0
 938     where lgo z []     = z
 939           lgo z (x:xs) = let z' = f z x in z' `seq` lgo z' xs
 940 #else
 941 foldl' f a []     = a
 942 foldl' f a (x:xs) = let a' = f a x in a' `seq` foldl' f a' xs
 943 #endif
 944
 945 #ifdef __GLASGOW_HASKELL__
 946 -- | 'foldl1' is a variant of 'foldl' that has no starting value argument,
 947 -- and thus must be applied to non-empty lists.
 948 foldl1                  :: (a -> a -> a) -> [a] -> a
 949 foldl1 f (x:xs)         =  foldl f x xs
 950 foldl1 _ []             =  errorEmptyList "foldl1"
 951 #endif /* __GLASGOW_HASKELL__ */
 952
 953 -- | A strict version of 'foldl1'
 954 foldl1'                  :: (a -> a -> a) -> [a] -> a
 955 foldl1' f (x:xs)         =  foldl' f x xs
 956 foldl1' _ []             =  errorEmptyList "foldl1'"
 957
 958 #ifdef __GLASGOW_HASKELL__
 959 -- -----------------------------------------------------------------------------
 960 -- List sum and product
 961
 962 {-# SPECIALISE sum     :: [Int] -> Int #-}
 963 {-# SPECIALISE sum     :: [Integer] -> Integer #-}
 964 {-# SPECIALISE product :: [Int] -> Int #-}
 965 {-# SPECIALISE product :: [Integer] -> Integer #-}
 966 -- | The 'sum' function computes the sum of a finite list of numbers.
 967 sum                     :: (Num a) => [a] -> a
 968 -- | The 'product' function computes the product of a finite list of numbers.
 969 product                 :: (Num a) => [a] -> a
 970 #ifdef USE_REPORT_PRELUDE
 971 sum                     =  foldl (+) 0
 972 product                 =  foldl (*) 1
 973 #else
 974 sum     l       = sum' l 0
 975   where
 976     sum' []     a = a
 977     sum' (x:xs) a = sum' xs (a+x)
 978 product l       = prod l 1
 979   where
 980     prod []     a = a
 981     prod (x:xs) a = prod xs (a*x)
 982 #endif
 983
 984 -- -----------------------------------------------------------------------------
 985 -- Functions on strings
 986
 987 -- | 'lines' breaks a string up into a list of strings at newline
 988 -- characters.  The resulting strings do not contain newlines.
 989 lines                   :: String -> [String]
 990 lines ""                =  []
 991 lines s                 =  let (l, s') = break (== '\n') s
 992                            in  l : case s' of
 993                                         []      -> []
 994                                         (_:s'') -> lines s''
 995
 996 -- | 'unlines' is an inverse operation to 'lines'.
 997 -- It joins lines, after appending a terminating newline to each.
 998 unlines                 :: [String] -> String
 999 #ifdef USE_REPORT_PRELUDE
1000 unlines                 =  concatMap (++ "\n")
1001 #else
1002 -- HBC version (stolen)
1003 -- here's a more efficient version
1004 unlines [] = []
1005 unlines (l:ls) = l ++ '\n' : unlines ls
1006 #endif
1007
1008 -- | 'words' breaks a string up into a list of words, which were delimited
1009 -- by white space.
1010 words                   :: String -> [String]
1011 words s                 =  case dropWhile {-partain:Char.-}isSpace s of
1012                                 "" -> []
1013                                 s' -> w : words s''
1014                                       where (w, s'') =
1015                                              break {-partain:Char.-}isSpace s'
1016
1017 -- | 'unwords' is an inverse operation to 'words'.
1018 -- It joins words with separating spaces.
1019 unwords                 :: [String] -> String
1020 #ifdef USE_REPORT_PRELUDE
1021 unwords []              =  ""
1022 unwords ws              =  foldr1 (\w s -> w ++ ' ':s) ws
1023 #else
1024 -- HBC version (stolen)
1025 -- here's a more efficient version
1026 unwords []              =  ""
1027 unwords [w]             = w
1028 unwords (w:ws)          = w ++ ' ' : unwords ws
1029 #endif
1030
1031 #else  /* !__GLASGOW_HASKELL__ */
1032
1033 errorEmptyList :: String -> a
1034 errorEmptyList fun =
1035   error ("Prelude." ++ fun ++ ": empty list")
1036
1037 #endif /* !__GLASGOW_HASKELL__ */