ghc/lib/std/List.lhs

   1 % -----------------------------------------------------------------------------
   2 % $Id: List.lhs,v 1.12 2001/06/25 13:13:58 simonpj Exp $
   3 %
   4 % (c) The University of Glasgow, 1994-2000
   5 %
   6
   7 \section[List]{Module @List@}
   8
   9 \begin{code}
  10 module List
  11    (
  12 #ifndef __HUGS__
  13      []((:), [])
  14    ,
  15 #endif
  16
  17       elemIndex        -- :: (Eq a) => a -> [a] -> Maybe Int
  18    , elemIndices       -- :: (Eq a) => a -> [a] -> [Int]
  19
  20    , find              -- :: (a -> Bool) -> [a] -> Maybe a
  21    , findIndex         -- :: (a -> Bool) -> [a] -> Maybe Int
  22    , findIndices       -- :: (a -> Bool) -> [a] -> [Int]
  23
  24    , nub               -- :: (Eq a) => [a] -> [a]
  25    , nubBy             -- :: (a -> a -> Bool) -> [a] -> [a]
  26
  27    , delete            -- :: (Eq a) => a -> [a] -> [a]
  28    , deleteBy          -- :: (a -> a -> Bool) -> a -> [a] -> [a]
  29    , (\\)              -- :: (Eq a) => [a] -> [a] -> [a]
  30    , deleteFirstsBy    -- :: (a -> a -> Bool) -> [a] -> [a] -> [a]
  31
  32    , union             -- :: (Eq a) => [a] -> [a] -> [a]
  33    , unionBy           -- :: (a -> a -> Bool) -> [a] -> [a] -> [a]
  34
  35    , intersect         -- :: (Eq a) => [a] -> [a] -> [a]
  36    , intersectBy       -- :: (a -> a -> Bool) -> [a] -> [a] -> [a]
  37
  38    , intersperse       -- :: a -> [a] -> [a]
  39    , transpose         -- :: [[a]] -> [[a]]
  40    , partition         -- :: (a -> Bool) -> [a] -> ([a], [a])
  41
  42    , group             -- :: Eq a => [a] -> [[a]]
  43    , groupBy           -- :: (a -> a -> Bool) -> [a] -> [[a]]
  44
  45    , inits             -- :: [a] -> [[a]]
  46    , tails             -- :: [a] -> [[a]]
  47
  48    , isPrefixOf        -- :: (Eq a) => [a] -> [a] -> Bool
  49    , isSuffixOf        -- :: (Eq a) => [a] -> [a] -> Bool
  50
  51    , mapAccumL         -- :: (a -> b -> (a,c)) -> a -> [b] -> (a,[c])
  52    , mapAccumR         -- :: (a -> b -> (a,c)) -> a -> [b] -> (a,[c])
  53
  54    , sort              -- :: (Ord a) => [a] -> [a]
  55    , sortBy            -- :: (a -> a -> Ordering) -> [a] -> [a]
  56
  57    , insert            -- :: (Ord a) => a -> [a] -> [a]
  58    , insertBy          -- :: (a -> a -> Ordering) -> a -> [a] -> [a]
  59
  60    , maximumBy         -- :: (a -> a -> Ordering) -> [a] -> a
  61    , minimumBy         -- :: (a -> a -> Ordering) -> [a] -> a
  62
  63    , genericLength     -- :: (Integral a) => [b] -> a
  64    , genericTake       -- :: (Integral a) => a -> [b] -> [b]
  65    , genericDrop       -- :: (Integral a) => a -> [b] -> [b]
  66    , genericSplitAt    -- :: (Integral a) => a -> [b] -> ([b], [b])
  67    , genericIndex      -- :: (Integral a) => [b] -> a -> b
  68    , genericReplicate  -- :: (Integral a) => a -> b -> [b]
  69
  70    , unfoldr            -- :: (b -> Maybe (a, b)) -> b -> [a]
  71
  72    , zip4, zip5, zip6, zip7
  73    , zipWith4, zipWith5, zipWith6, zipWith7
  74    , unzip4, unzip5, unzip6, unzip7
  75
  76    , map               -- :: ( a -> b ) -> [a] -> [b]
  77    , (++)              -- :: [a] -> [a] -> [a]
  78    , concat            -- :: [[a]] -> [a]
  79    , filter            -- :: (a -> Bool) -> [a] -> [a]
  80    , head              -- :: [a] -> a
  81    , last              -- :: [a] -> a
  82    , tail              -- :: [a] -> [a]
  83    , init              -- :: [a] -> [a]
  84    , null              -- :: [a] -> Bool
  85    , length            -- :: [a] -> Int
  86    , (!!)              -- :: [a] -> Int -> a
  87    , foldl             -- :: (a -> b -> a) -> a -> [b] -> a
  88    , foldl1            -- :: (a -> a -> a) -> [a] -> a
  89    , scanl             -- :: (a -> b -> a) -> a -> [b] -> [a]
  90    , scanl1            -- :: (a -> a -> a) -> [a] -> [a]
  91    , foldr             -- :: (a -> b -> b) -> b -> [a] -> b
  92    , foldr1            -- :: (a -> a -> a) -> [a] -> a
  93    , scanr             -- :: (a -> b -> b) -> b -> [a] -> [b]
  94    , scanr1            -- :: (a -> a -> a) -> [a] -> [a]
  95    , iterate           -- :: (a -> a) -> a -> [a]
  96    , repeat            -- :: a -> [a]
  97    , replicate         -- :: Int -> a -> [a]
  98    , cycle             -- :: [a] -> [a]
  99    , take              -- :: Int -> [a] -> [a]
 100    , drop              -- :: Int -> [a] -> [a]
 101    , splitAt           -- :: Int -> [a] -> ([a], [a])
 102    , takeWhile         -- :: (a -> Bool) -> [a] -> [a]
 103    , dropWhile         -- :: (a -> Bool) -> [a] -> [a]
 104    , span              -- :: (a -> Bool) -> [a] -> ([a], [a])
 105    , break             -- :: (a -> Bool) -> [a] -> ([a], [a])
 106
 107    , lines             -- :: String   -> [String]
 108    , words             -- :: String   -> [String]
 109    , unlines           -- :: [String] -> String
 110    , unwords           -- :: [String] -> String
 111    , reverse           -- :: [a] -> [a]
 112    , and               -- :: [Bool] -> Bool
 113    , or                -- :: [Bool] -> Bool
 114    , any               -- :: (a -> Bool) -> [a] -> Bool
 115    , all               -- :: (a -> Bool) -> [a] -> Bool
 116    , elem              -- :: a -> [a] -> Bool
 117    , notElem           -- :: a -> [a] -> Bool
 118    , lookup            -- :: (Eq a) => a -> [(a,b)] -> Maybe b
 119    , sum               -- :: (Num a) => [a] -> a
 120    , product           -- :: (Num a) => [a] -> a
 121    , maximum           -- :: (Ord a) => [a] -> a
 122    , minimum           -- :: (Ord a) => [a] -> a
 123    , concatMap         -- :: (a -> [b]) -> [a] -> [b]
 124    , zip               -- :: [a] -> [b] -> [(a,b)]
 125    , zip3
 126    , zipWith           -- :: (a -> b -> c) -> [a] -> [b] -> [c]
 127    , zipWith3
 128    , unzip             -- :: [(a,b)] -> ([a],[b])
 129    , unzip3
 130
 131      -- Implementation checked wrt. Haskell 98 lib report, 1/99.
 132    ) where
 133
 134 import Prelude
 135 import Maybe    ( listToMaybe )
 136
 137 #ifndef __HUGS__
 138 import PrelShow ( lines, words, unlines, unwords )
 139 import PrelBase ( Int(..), map, (++) )
 140 import PrelGHC  ( (+#) )
 141 #endif
 142
 143 infix 5 \\
 144 \end{code}
 145
 146 %*********************************************************
 147 %*                                                      *
 148 \subsection{List functions}
 149 %*                                                      *
 150 %*********************************************************
 151
 152 \begin{code}
 153 elemIndex       :: Eq a => a -> [a] -> Maybe Int
 154 elemIndex x     = findIndex (x==)
 155
 156 elemIndices     :: Eq a => a -> [a] -> [Int]
 157 elemIndices x   = findIndices (x==)
 158
 159 find            :: (a -> Bool) -> [a] -> Maybe a
 160 find p          = listToMaybe . filter p
 161
 162 findIndex       :: (a -> Bool) -> [a] -> Maybe Int
 163 findIndex p     = listToMaybe . findIndices p
 164
 165 findIndices      :: (a -> Bool) -> [a] -> [Int]
 166
 167 #ifdef USE_REPORT_PRELUDE
 168 findIndices p xs = [ i | (x,i) <- zip xs [0..], p x]
 169 #else
 170 #ifdef __HUGS__
 171 findIndices p xs = [ i | (x,i) <- zip xs [0..], p x]
 172 #else
 173 -- Efficient definition
 174 findIndices p ls = loop 0# ls
 175                  where
 176                    loop _ [] = []
 177                    loop n (x:xs) | p x       = I# n : loop (n +# 1#) xs
 178                                  | otherwise = loop (n +# 1#) xs
 179 #endif  /* __HUGS__ */
 180 #endif  /* USE_REPORT_PRELUDE */
 181
 182 isPrefixOf              :: (Eq a) => [a] -> [a] -> Bool
 183 isPrefixOf [] _         =  True
 184 isPrefixOf _  []        =  False
 185 isPrefixOf (x:xs) (y:ys)=  x == y && isPrefixOf xs ys
 186
 187 isSuffixOf              :: (Eq a) => [a] -> [a] -> Bool
 188 isSuffixOf x y          =  reverse x `isPrefixOf` reverse y
 189
 190 -- nub (meaning "essence") remove duplicate elements from its list argument.
 191 nub                     :: (Eq a) => [a] -> [a]
 192 #ifdef USE_REPORT_PRELUDE
 193 nub                     =  nubBy (==)
 194 #else
 195 -- stolen from HBC
 196 nub l                   = nub' l []             -- '
 197   where
 198     nub' [] _           = []                    -- '
 199     nub' (x:xs) ls                              -- '
 200         | x `elem` ls   = nub' xs ls            -- '
 201         | otherwise     = x : nub' xs (x:ls)    -- '
 202 #endif
 203
 204 nubBy                   :: (a -> a -> Bool) -> [a] -> [a]
 205 #ifdef USE_REPORT_PRELUDE
 206 nubBy eq []             =  []
 207 nubBy eq (x:xs)         =  x : nubBy eq (filter (\ y -> not (eq x y)) xs)
 208 #else
 209 nubBy eq l              = nubBy' l []
 210   where
 211     nubBy' [] _         = []
 212     nubBy' (y:ys) xs
 213        | elem_by eq y xs = nubBy' ys xs
 214        | otherwise       = y : nubBy' ys (y:xs)
 215
 216 -- Not exported:
 217 -- Note that we keep the call to `eq` with arguments in the
 218 -- same order as in the reference implementation
 219 -- 'xs' is the list of things we've seen so far,
 220 -- 'y' is the potential new element
 221 elem_by :: (a -> a -> Bool) -> a -> [a] -> Bool
 222 elem_by _  _ []         =  False
 223 elem_by eq y (x:xs)     =  x `eq` y || elem_by eq y xs
 224 #endif
 225
 226
 227 -- delete x removes the first occurrence of x from its list argument.
 228 delete                  :: (Eq a) => a -> [a] -> [a]
 229 delete                  =  deleteBy (==)
 230
 231 deleteBy                :: (a -> a -> Bool) -> a -> [a] -> [a]
 232 deleteBy _  _ []        = []
 233 deleteBy eq x (y:ys)    = if x `eq` y then ys else y : deleteBy eq x ys
 234
 235 -- list difference (non-associative).  In the result of xs \\ ys,
 236 -- the first occurrence of each element of ys in turn (if any)
 237 -- has been removed from xs.  Thus, (xs ++ ys) \\ xs == ys.
 238 (\\)                    :: (Eq a) => [a] -> [a] -> [a]
 239 (\\)                    =  foldl (flip delete)
 240
 241 -- List union, remove the elements of first list from second.
 242 union                   :: (Eq a) => [a] -> [a] -> [a]
 243 union                   = unionBy (==)
 244
 245 unionBy                 :: (a -> a -> Bool) -> [a] -> [a] -> [a]
 246 unionBy eq xs ys        =  xs ++ foldl (flip (deleteBy eq)) (nubBy eq ys) xs
 247
 248 intersect               :: (Eq a) => [a] -> [a] -> [a]
 249 intersect               =  intersectBy (==)
 250
 251 intersectBy             :: (a -> a -> Bool) -> [a] -> [a] -> [a]
 252 intersectBy eq xs ys    =  [x | x <- xs, any (eq x) ys]
 253
 254 -- intersperse sep inserts sep between the elements of its list argument.
 255 -- e.g. intersperse ',' "abcde" == "a,b,c,d,e"
 256 intersperse             :: a -> [a] -> [a]
 257 intersperse _   []      = []
 258 intersperse _   [x]     = [x]
 259 intersperse sep (x:xs)  = x : sep : intersperse sep xs
 260
 261 transpose               :: [[a]] -> [[a]]
 262 transpose []             = []
 263 transpose ([]   : xss)   = transpose xss
 264 transpose ((x:xs) : xss) = (x : [h | (h:t) <- xss]) : transpose (xs : [ t | (h:t) <- xss])
 265
 266
 267 -- partition takes a predicate and a list and returns a pair of lists:
 268 -- those elements of the argument list that do and do not satisfy the
 269 -- predicate, respectively; i,e,,
 270 -- partition p xs == (filter p xs, filter (not . p) xs).
 271 partition               :: (a -> Bool) -> [a] -> ([a],[a])
 272 {-# INLINE partition #-}
 273 partition p xs = foldr (select p) ([],[]) xs
 274
 275 select p x (ts,fs) | p x       = (x:ts,fs)
 276                    | otherwise = (ts, x:fs)
 277 \end{code}
 278
 279 @mapAccumL@ behaves like a combination
 280 of  @map@ and @foldl@;
 281 it applies a function to each element of a list, passing an accumulating
 282 parameter from left to right, and returning a final value of this
 283 accumulator together with the new list.
 284
 285 \begin{code}
 286
 287 mapAccumL :: (acc -> x -> (acc, y)) -- Function of elt of input list
 288                                     -- and accumulator, returning new
 289                                     -- accumulator and elt of result list
 290           -> acc            -- Initial accumulator
 291           -> [x]            -- Input list
 292           -> (acc, [y])     -- Final accumulator and result list
 293 mapAccumL _ s []        =  (s, [])
 294 mapAccumL f s (x:xs)    =  (s'',y:ys)
 295                            where (s', y ) = f s x
 296                                  (s'',ys) = mapAccumL f s' xs
 297 \end{code}
 298
 299 @mapAccumR@ does the same, but working from right to left instead.  Its type is
 300 the same as @mapAccumL@, though.
 301
 302 \begin{code}
 303 mapAccumR :: (acc -> x -> (acc, y))     -- Function of elt of input list
 304                                         -- and accumulator, returning new
 305                                         -- accumulator and elt of result list
 306             -> acc              -- Initial accumulator
 307             -> [x]              -- Input list
 308             -> (acc, [y])               -- Final accumulator and result list
 309 mapAccumR _ s []        =  (s, [])
 310 mapAccumR f s (x:xs)    =  (s'', y:ys)
 311                            where (s'',y ) = f s' x
 312                                  (s', ys) = mapAccumR f s xs
 313 \end{code}
 314
 315 \begin{code}
 316 insert :: Ord a => a -> [a] -> [a]
 317 insert e ls = insertBy (compare) e ls
 318
 319 insertBy :: (a -> a -> Ordering) -> a -> [a] -> [a]
 320 insertBy _   x [] = [x]
 321 insertBy cmp x ys@(y:ys')
 322  = case cmp x y of
 323      GT -> y : insertBy cmp x ys'
 324      _  -> x : ys
 325
 326 maximumBy               :: (a -> a -> a) -> [a] -> a
 327 maximumBy _   []        =  error "List.maximumBy: empty list"
 328 maximumBy max xs        =  foldl1 max xs
 329
 330 minimumBy               :: (a -> a -> a) -> [a] -> a
 331 minimumBy _   []        =  error "List.minimumBy: empty list"
 332 minimumBy min xs        =  foldl1 min xs
 333
 334 genericLength           :: (Num i) => [b] -> i
 335 genericLength []        =  0
 336 genericLength (_:l)     =  1 + genericLength l
 337
 338 genericTake             :: (Integral i) => i -> [a] -> [a]
 339 genericTake 0 _         =  []
 340 genericTake _ []        =  []
 341 genericTake n (x:xs) | n > 0  =  x : genericTake (n-1) xs
 342 genericTake _  _        =  error "List.genericTake: negative argument"
 343
 344 genericDrop             :: (Integral i) => i -> [a] -> [a]
 345 genericDrop 0 xs        =  xs
 346 genericDrop _ []        =  []
 347 genericDrop n (_:xs) | n > 0  =  genericDrop (n-1) xs
 348 genericDrop _ _         =  error "List.genericDrop: negative argument"
 349
 350 genericSplitAt          :: (Integral i) => i -> [b] -> ([b],[b])
 351 genericSplitAt 0 xs     =  ([],xs)
 352 genericSplitAt _ []     =  ([],[])
 353 genericSplitAt n (x:xs) | n > 0  =  (x:xs',xs'') where
 354                                (xs',xs'') = genericSplitAt (n-1) xs
 355 genericSplitAt _ _      =  error "List.genericSplitAt: negative argument"
 356
 357
 358 genericIndex :: (Integral a) => [b] -> a -> b
 359 genericIndex (x:_)  0 = x
 360 genericIndex (_:xs) n
 361  | n > 0     = genericIndex xs (n-1)
 362  | otherwise = error "List.genericIndex: negative argument."
 363 genericIndex _ _      = error "List.genericIndex: index too large."
 364
 365 genericReplicate        :: (Integral i) => i -> a -> [a]
 366 genericReplicate n x    =  genericTake n (repeat x)
 367
 368
 369 zip4                    :: [a] -> [b] -> [c] -> [d] -> [(a,b,c,d)]
 370 zip4                    =  zipWith4 (,,,)
 371
 372 zip5                    :: [a] -> [b] -> [c] -> [d] -> [e] -> [(a,b,c,d,e)]
 373 zip5                    =  zipWith5 (,,,,)
 374
 375 zip6                    :: [a] -> [b] -> [c] -> [d] -> [e] -> [f] ->
 376                               [(a,b,c,d,e,f)]
 377 zip6                    =  zipWith6 (,,,,,)
 378
 379 zip7                    :: [a] -> [b] -> [c] -> [d] -> [e] -> [f] ->
 380                               [g] -> [(a,b,c,d,e,f,g)]
 381 zip7                    =  zipWith7 (,,,,,,)
 382
 383 zipWith4                :: (a->b->c->d->e) -> [a]->[b]->[c]->[d]->[e]
 384 zipWith4 z (a:as) (b:bs) (c:cs) (d:ds)
 385                         =  z a b c d : zipWith4 z as bs cs ds
 386 zipWith4 _ _ _ _ _      =  []
 387
 388 zipWith5                :: (a->b->c->d->e->f) ->
 389                            [a]->[b]->[c]->[d]->[e]->[f]
 390 zipWith5 z (a:as) (b:bs) (c:cs) (d:ds) (e:es)
 391                         =  z a b c d e : zipWith5 z as bs cs ds es
 392 zipWith5 _ _ _ _ _ _    = []
 393
 394 zipWith6                :: (a->b->c->d->e->f->g) ->
 395                            [a]->[b]->[c]->[d]->[e]->[f]->[g]
 396 zipWith6 z (a:as) (b:bs) (c:cs) (d:ds) (e:es) (f:fs)
 397                         =  z a b c d e f : zipWith6 z as bs cs ds es fs
 398 zipWith6 _ _ _ _ _ _ _  = []
 399
 400 zipWith7                :: (a->b->c->d->e->f->g->h) ->
 401                            [a]->[b]->[c]->[d]->[e]->[f]->[g]->[h]
 402 zipWith7 z (a:as) (b:bs) (c:cs) (d:ds) (e:es) (f:fs) (g:gs)
 403                    =  z a b c d e f g : zipWith7 z as bs cs ds es fs gs
 404 zipWith7 _ _ _ _ _ _ _ _ = []
 405
 406 unzip4                  :: [(a,b,c,d)] -> ([a],[b],[c],[d])
 407 unzip4                  =  foldr (\(a,b,c,d) ~(as,bs,cs,ds) ->
 408                                         (a:as,b:bs,c:cs,d:ds))
 409                                  ([],[],[],[])
 410
 411 unzip5                  :: [(a,b,c,d,e)] -> ([a],[b],[c],[d],[e])
 412 unzip5                  =  foldr (\(a,b,c,d,e) ~(as,bs,cs,ds,es) ->
 413                                         (a:as,b:bs,c:cs,d:ds,e:es))
 414                                  ([],[],[],[],[])
 415
 416 unzip6                  :: [(a,b,c,d,e,f)] -> ([a],[b],[c],[d],[e],[f])
 417 unzip6                  =  foldr (\(a,b,c,d,e,f) ~(as,bs,cs,ds,es,fs) ->
 418                                         (a:as,b:bs,c:cs,d:ds,e:es,f:fs))
 419                                  ([],[],[],[],[],[])
 420
 421 unzip7          :: [(a,b,c,d,e,f,g)] -> ([a],[b],[c],[d],[e],[f],[g])
 422 unzip7          =  foldr (\(a,b,c,d,e,f,g) ~(as,bs,cs,ds,es,fs,gs) ->
 423                                 (a:as,b:bs,c:cs,d:ds,e:es,f:fs,g:gs))
 424                          ([],[],[],[],[],[],[])
 425
 426
 427
 428 deleteFirstsBy          :: (a -> a -> Bool) -> [a] -> [a] -> [a]
 429 deleteFirstsBy eq       =  foldl (flip (deleteBy eq))
 430
 431
 432 -- group splits its list argument into a list of lists of equal, adjacent
 433 -- elements.  e.g.,
 434 -- group "Mississippi" == ["M","i","ss","i","ss","i","pp","i"]
 435 group                   :: (Eq a) => [a] -> [[a]]
 436 group                   =  groupBy (==)
 437
 438 groupBy                 :: (a -> a -> Bool) -> [a] -> [[a]]
 439 groupBy _  []           =  []
 440 groupBy eq (x:xs)       =  (x:ys) : groupBy eq zs
 441                            where (ys,zs) = span (eq x) xs
 442
 443 -- inits xs returns the list of initial segments of xs, shortest first.
 444 -- e.g., inits "abc" == ["","a","ab","abc"]
 445 inits                   :: [a] -> [[a]]
 446 inits []                =  [[]]
 447 inits (x:xs)            =  [[]] ++ map (x:) (inits xs)
 448
 449 -- tails xs returns the list of all final segments of xs, longest first.
 450 -- e.g., tails "abc" == ["abc", "bc", "c",""]
 451 tails                   :: [a] -> [[a]]
 452 tails []                =  [[]]
 453 tails xxs@(_:xs)        =  xxs : tails xs
 454
 455 \end{code}
 456
 457 %-----------------------------------------------------------------------------
 458 Quick Sort algorithm taken from HBC's QSort library.
 459
 460 \begin{code}
 461 sort :: (Ord a) => [a] -> [a]
 462 sortBy :: (a -> a -> Ordering) -> [a] -> [a]
 463
 464 #ifdef USE_REPORT_PRELUDE
 465 sort = sortBy compare
 466 sortBy cmp = foldr (insertBy cmp) []
 467 #else
 468
 469 sortBy cmp l = qsort cmp l []
 470 sort l = qsort compare l []
 471
 472 -- rest is not exported:
 473
 474 -- qsort is stable and does not concatenate.
 475 qsort :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
 476 qsort _   []     r = r
 477 qsort _   [x]    r = x:r
 478 qsort cmp (x:xs) r = qpart cmp x xs [] [] r
 479
 480 -- qpart partitions and sorts the sublists
 481 qpart :: (a -> a -> Ordering) -> a -> [a] -> [a] -> [a] -> [a] -> [a]
 482 qpart cmp x [] rlt rge r =
 483     -- rlt and rge are in reverse order and must be sorted with an
 484     -- anti-stable sorting
 485     rqsort cmp rlt (x:rqsort cmp rge r)
 486 qpart cmp x (y:ys) rlt rge r =
 487     case cmp x y of
 488         GT -> qpart cmp x ys (y:rlt) rge r
 489         _  -> qpart cmp x ys rlt (y:rge) r
 490
 491 -- rqsort is as qsort but anti-stable, i.e. reverses equal elements
 492 rqsort :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
 493 rqsort _   []     r = r
 494 rqsort _   [x]    r = x:r
 495 rqsort cmp (x:xs) r = rqpart cmp x xs [] [] r
 496
 497 rqpart :: (a -> a -> Ordering) -> a -> [a] -> [a] -> [a] -> [a] -> [a]
 498 rqpart cmp x [] rle rgt r =
 499     qsort cmp rle (x:qsort cmp rgt r)
 500 rqpart cmp x (y:ys) rle rgt r =
 501     case cmp y x of
 502         GT -> rqpart cmp x ys rle (y:rgt) r
 503         _  -> rqpart cmp x ys (y:rle) rgt r
 504
 505 #endif /* USE_REPORT_PRELUDE */
 506 \end{code}
 507
 508 \begin{verbatim}
 509   unfoldr f' (foldr f z xs) == (z,xs)
 510
 511  if the following holds:
 512
 513    f' (f x y) = Just (x,y)
 514    f' z       = Nothing
 515 \end{verbatim}
 516
 517 \begin{code}
 518 unfoldr      :: (b -> Maybe (a, b)) -> b -> [a]
 519 unfoldr f b  =
 520   case f b of
 521    Just (a,new_b) -> a : unfoldr f new_b
 522    Nothing        -> []
 523 \end{code}