fix strictness of foldr/build rule for take, see #1219
[packages/old-time.git] / GHC / List.lhs
index 07f6d3f..ce13f46 100644 (file)
@@ -1,42 +1,44 @@
-% ------------------------------------------------------------------------------
-% $Id: List.lhs,v 1.3 2001/07/03 14:13:32 simonmar Exp $
-%
-% (c) The University of Glasgow, 1994-2000
-%
-
-\section[GHC.List]{Module @GHC.List@}
-
-The List data type and its operations
-
 \begin{code}
-{-# OPTIONS -fno-implicit-prelude #-}
+{-# OPTIONS_GHC -fno-implicit-prelude #-}
+-----------------------------------------------------------------------------
+-- |
+-- Module      :  GHC.List
+-- Copyright   :  (c) The University of Glasgow 1994-2002
+-- License     :  see libraries/base/LICENSE
+-- 
+-- Maintainer  :  cvs-ghc@haskell.org
+-- Stability   :  internal
+-- Portability :  non-portable (GHC Extensions)
+--
+-- The List data type and its operations
+--
+-----------------------------------------------------------------------------
 
+-- #hide
 module GHC.List (
-   [] (..),
+   -- [] (..),         -- Not Haskell 98; built in syntax
 
    map, (++), filter, concat,
    head, last, tail, init, null, length, (!!), 
-   foldl, foldl1, scanl, scanl1, foldr, foldr1, scanr, scanr1,
+   foldl, scanl, scanl1, foldr, foldr1, scanr, scanr1,
    iterate, repeat, replicate, cycle,
    take, drop, splitAt, takeWhile, dropWhile, span, break,
    reverse, and, or,
    any, all, elem, notElem, lookup,
-   maximum, minimum, concatMap,
+   concatMap,
    zip, zip3, zipWith, zipWith3, unzip, unzip3,
-#ifdef USE_REPORT_PRELUDE
-
-#else
+   errorEmptyList,
 
+#ifndef USE_REPORT_PRELUDE
    -- non-standard, but hidden when creating the Prelude
    -- export list.
    takeUInt_append
-
 #endif
 
  ) where
 
 import {-# SOURCE #-} GHC.Err ( error )
-import Data.Tuple
+import Data.Tuple()    -- Instances
 import Data.Maybe
 import GHC.Base
 
@@ -51,11 +53,7 @@ infix  4 `elem`, `notElem`
 %*********************************************************
 
 \begin{code}
--- head and tail extract the first element and remaining elements,
--- respectively, of a list, which must be non-empty.  last and init
--- are the dual functions working from the end of a finite list,
--- rather than the beginning.
-
+-- | Extract the first element of a list, which must be non-empty.
 head                    :: [a] -> a
 head (x:_)              =  x
 head []                 =  badHead
@@ -65,16 +63,18 @@ badHead = errorEmptyList "head"
 -- This rule is useful in cases like 
 --     head [y | (x,y) <- ps, x==t]
 {-# RULES
-"head/build"   forall (g::forall b.(Bool->b->b)->b->b) . 
+"head/build"   forall (g::forall b.(a->b->b)->b->b) .
                head (build g) = g (\x _ -> x) badHead
 "head/augment" forall xs (g::forall b. (a->b->b) -> b -> b) . 
                head (augment g xs) = g (\x _ -> x) (head xs)
  #-}
 
+-- | Extract the elements after the head of a list, which must be non-empty.
 tail                    :: [a] -> [a]
 tail (_:xs)             =  xs
 tail []                 =  errorEmptyList "tail"
 
+-- | Extract the last element of a list, which must be finite and non-empty.
 last                    :: [a] -> a
 #ifdef USE_REPORT_PRELUDE
 last [x]                =  x
@@ -88,6 +88,8 @@ last (x:xs)           =  last' x xs
        last' _ (y:ys) = last' y ys
 #endif
 
+-- | Return all the elements of a list except the last one.
+-- The list must be finite and non-empty.
 init                    :: [a] -> [a]
 #ifdef USE_REPORT_PRELUDE
 init [x]                =  []
@@ -101,13 +103,14 @@ init (x:xs)             =  init' x xs
        init' y (z:zs) = y : init' z zs
 #endif
 
+-- | Test whether a list is empty.
 null                    :: [a] -> Bool
 null []                 =  True
 null (_:_)              =  False
 
--- length returns the length of a finite list as an Int; it is an instance
--- of the more general genericLength, the result type of which may be
--- any kind of number.
+-- | 'length' returns the length of a finite list as an 'Int'.
+-- It is an instance of the more general 'Data.List.genericLength',
+-- the result type of which may be any kind of number.
 length                  :: [a] -> Int
 length l                =  len l 0#
   where
@@ -115,19 +118,25 @@ length l                =  len l 0#
     len []     a# = I# a#
     len (_:xs) a# = len xs (a# +# 1#)
 
--- filter, applied to a predicate and a list, returns the list of those
--- elements that satisfy the predicate; i.e.,
--- filter p xs = [ x | x <- xs, p x]
+-- | 'filter', applied to a predicate and a list, returns the list of
+-- those elements that satisfy the predicate; i.e.,
+--
+-- > filter p xs = [ x | x <- xs, p x]
+
 filter :: (a -> Bool) -> [a] -> [a]
-filter = filterList
+filter _pred []    = []
+filter pred (x:xs)
+  | pred x         = x : filter pred xs
+  | otherwise     = filter pred xs
 
+{-# NOINLINE [0] filterFB #-}
 filterFB c p x r | p x       = x `c` r
                 | otherwise = r
 
 {-# RULES
-"filter"       forall p xs.    filter p xs = build (\c n -> foldr (filterFB c p) n xs)
-"filterFB"     forall c p q.   filterFB (filterFB c p) q = filterFB c (\x -> q x && p x)
-"filterList"   forall p.       foldr (filterFB (:) p) [] = filterList p
+"filter"     [~1] forall p xs.  filter p xs = build (\c n -> foldr (filterFB c p) n xs)
+"filterList" [1]  forall p.    foldr (filterFB (:) p) [] = filter p
+"filterFB"       forall c p q. filterFB (filterFB c p) q = filterFB c (\x -> q x && p x)
  #-}
 
 -- Note the filterFB rule, which has p and q the "wrong way round" in the RHS.
@@ -139,23 +148,14 @@ filterFB c p x r | p x       = x `c` r
 -- I originally wrote (\x -> p x && q x), which is wrong, and actually
 -- gave rise to a live bug report.  SLPJ.
 
-filterList :: (a -> Bool) -> [a] -> [a]
-filterList _pred []    = []
-filterList pred (x:xs)
-  | pred x         = x : filterList pred xs
-  | otherwise     = filterList pred xs
-
--- foldl, applied to a binary operator, a starting value (typically the
--- left-identity of the operator), and a list, reduces the list using
--- the binary operator, from left to right:
---  foldl f z [x1, x2, ..., xn] == (...((z `f` x1) `f` x2) `f`...) `f` xn
--- foldl1 is a variant that has no starting value argument, and  thus must
--- be applied to non-empty lists.  scanl is similar to foldl, but returns
--- a list of successive reduced values from the left:
---      scanl f z [x1, x2, ...] == [z, z `f` x1, (z `f` x1) `f` x2, ...]
--- Note that  last (scanl f z xs) == foldl f z xs.
--- scanl1 is similar, again without the starting element:
---      scanl1 f [x1, x2, ...] == [x1, x1 `f` x2, ...]
+
+-- | 'foldl', applied to a binary operator, a starting value (typically
+-- the left-identity of the operator), and a list, reduces the list
+-- using the binary operator, from left to right:
+--
+-- > foldl f z [x1, x2, ..., xn] == (...((z `f` x1) `f` x2) `f`...) `f` xn
+--
+-- The list must be finite.
 
 -- We write foldl as a non-recursive thing, so that it
 -- can be inlined, and then (often) strictness-analysed,
@@ -167,70 +167,98 @@ foldl f z xs = lgo z xs
                lgo z []     =  z
                lgo z (x:xs) = lgo (f z x) xs
 
-foldl1                  :: (a -> a -> a) -> [a] -> a
-foldl1 f (x:xs)         =  foldl f x xs
-foldl1 _ []             =  errorEmptyList "foldl1"
+-- | 'scanl' is similar to 'foldl', but returns a list of successive
+-- reduced values from the left:
+--
+-- > scanl f z [x1, x2, ...] == [z, z `f` x1, (z `f` x1) `f` x2, ...]
+--
+-- Note that
+--
+-- > last (scanl f z xs) == foldl f z xs.
 
 scanl                   :: (a -> b -> a) -> a -> [b] -> [a]
 scanl f q ls            =  q : (case ls of
                                 []   -> []
                                 x:xs -> scanl f (f q x) xs)
 
-scanl1                  :: (a -> a -> a) -> [a] -> [a]
-scanl1 f (x:xs)         =  scanl f x xs
-scanl1 _ []             =  errorEmptyList "scanl1"
+-- | 'scanl1' is a variant of 'scanl' that has no starting value argument:
+--
+-- > scanl1 f [x1, x2, ...] == [x1, x1 `f` x2, ...]
+
+scanl1                 :: (a -> a -> a) -> [a] -> [a]
+scanl1 f (x:xs)                =  scanl f x xs
+scanl1 _ []            =  []
 
 -- foldr, foldr1, scanr, and scanr1 are the right-to-left duals of the
 -- above functions.
 
+-- | 'foldr1' is a variant of 'foldr' that has no starting value argument,
+-- and thus must be applied to non-empty lists.
+
 foldr1                  :: (a -> a -> a) -> [a] -> a
 foldr1 _ [x]            =  x
 foldr1 f (x:xs)         =  f x (foldr1 f xs)
 foldr1 _ []             =  errorEmptyList "foldr1"
 
+-- | 'scanr' is the right-to-left dual of 'scanl'.
+-- Note that
+--
+-- > head (scanr f z xs) == foldr f z xs.
+
 scanr                   :: (a -> b -> b) -> b -> [a] -> [b]
 scanr _ q0 []           =  [q0]
 scanr f q0 (x:xs)       =  f x q : qs
                            where qs@(q:_) = scanr f q0 xs 
 
+-- | 'scanr1' is a variant of 'scanr' that has no starting value argument.
+
 scanr1                  :: (a -> a -> a) -> [a] -> [a]
-scanr1 _  [x]           =  [x]
-scanr1 f  (x:xs)        =  f x q : qs
+scanr1 f []            =  []
+scanr1 f [x]           =  [x]
+scanr1 f (x:xs)                =  f x q : qs
                            where qs@(q:_) = scanr1 f xs 
-scanr1 _ []             =  errorEmptyList "scanr1"
 
--- iterate f x returns an infinite list of repeated applications of f to x:
--- iterate f x == [x, f x, f (f x), ...]
+-- | 'iterate' @f x@ returns an infinite list of repeated applications
+-- of @f@ to @x@:
+--
+-- > iterate f x == [x, f x, f (f x), ...]
+
 iterate :: (a -> a) -> a -> [a]
-iterate = iterateList
+iterate f x =  x : iterate f (f x)
 
 iterateFB c f x = x `c` iterateFB c f (f x)
 
-iterateList f x =  x : iterateList f (f x)
 
 {-# RULES
-"iterate"      forall f x.     iterate f x = build (\c _n -> iterateFB c f x)
-"iterateFB"                    iterateFB (:) = iterateList
+"iterate"    [~1] forall f x.  iterate f x = build (\c _n -> iterateFB c f x)
+"iterateFB"  [1]               iterateFB (:) = iterate
  #-}
 
 
--- repeat x is an infinite list, with x the value of every element.
+-- | 'repeat' @x@ is an infinite list, with @x@ the value of every element.
 repeat :: a -> [a]
-repeat = repeatList
+{-# INLINE [0] repeat #-}
+-- The pragma just gives the rules more chance to fire
+repeat x = xs where xs = x : xs
 
+{-# INLINE [0] repeatFB #-}    -- ditto
 repeatFB c x = xs where xs = x `c` xs
-repeatList x = xs where xs = x :   xs
+
 
 {-# RULES
-"repeat"       forall x. repeat x      = build (\c _n -> repeatFB c x)
-"repeatFB"               repeatFB (:)  = repeatList
+"repeat"    [~1] forall x. repeat x = build (\c _n -> repeatFB c x)
+"repeatFB"  [1]  repeatFB (:)      = repeat
  #-}
 
--- replicate n x is a list of length n with x the value of every element
+-- | 'replicate' @n x@ is a list of length @n@ with @x@ the value of
+-- every element.
+-- It is an instance of the more general 'Data.List.genericReplicate',
+-- in which @n@ may be of any integral type.
+{-# INLINE replicate #-}
 replicate               :: Int -> a -> [a]
 replicate n x           =  take n (repeat x)
 
--- cycle ties a finite list into a circular one, or equivalently,
+-- | 'cycle' ties a finite list into a circular one, or equivalently,
 -- the infinite repetition of the original list.  It is the identity
 -- on infinite lists.
 
@@ -238,10 +266,13 @@ cycle                   :: [a] -> [a]
 cycle []               = error "Prelude.cycle: empty list"
 cycle xs               = xs' where xs' = xs ++ xs'
 
--- takeWhile, applied to a predicate p and a list xs, returns the longest
--- prefix (possibly empty) of xs of elements that satisfy p.  dropWhile p xs
--- returns the remaining suffix.  Span p xs is equivalent to 
--- (takeWhile p xs, dropWhile p xs), while break p uses the negation of p.
+-- | 'takeWhile', applied to a predicate @p@ and a list @xs@, returns the
+-- longest prefix (possibly empty) of @xs@ of elements that satisfy @p@:
+--
+-- > takeWhile (< 3) [1,2,3,4,1,2,3,4] == [1,2]
+-- > takeWhile (< 9) [1,2,3] == [1,2,3]
+-- > takeWhile (< 0) [1,2,3] == []
+--
 
 takeWhile               :: (a -> Bool) -> [a] -> [a]
 takeWhile _ []          =  []
@@ -249,38 +280,98 @@ takeWhile p (x:xs)
             | p x       =  x : takeWhile p xs
             | otherwise =  []
 
+-- | 'dropWhile' @p xs@ returns the suffix remaining after 'takeWhile' @p xs@:
+--
+-- > dropWhile (< 3) [1,2,3,4,5,1,2,3] == [3,4,5,1,2,3]
+-- > dropWhile (< 9) [1,2,3] == []
+-- > dropWhile (< 0) [1,2,3] == [1,2,3]
+--
+
 dropWhile               :: (a -> Bool) -> [a] -> [a]
 dropWhile _ []          =  []
 dropWhile p xs@(x:xs')
             | p x       =  dropWhile p xs'
             | otherwise =  xs
 
--- take n, applied to a list xs, returns the prefix of xs of length n,
--- or xs itself if n > length xs.  drop n xs returns the suffix of xs
--- after the first n elements, or [] if n > length xs.  splitAt n xs
--- is equivalent to (take n xs, drop n xs).
-#ifdef USE_REPORT_PRELUDE
+-- | 'take' @n@, applied to a list @xs@, returns the prefix of @xs@
+-- of length @n@, or @xs@ itself if @n > 'length' xs@:
+--
+-- > take 5 "Hello World!" == "Hello"
+-- > take 3 [1,2,3,4,5] == [1,2,3]
+-- > take 3 [1,2] == [1,2]
+-- > take 3 [] == []
+-- > take (-1) [1,2] == []
+-- > take 0 [1,2] == []
+--
+-- It is an instance of the more general 'Data.List.genericTake',
+-- in which @n@ may be of any integral type.
 take                   :: Int -> [a] -> [a]
-take 0 _               =  []
-take _ []              =  []
-take n (x:xs) | n > 0  =  x : take (minusInt n 1) xs
-take _     _           =  errorNegativeIdx "take"
 
+-- | 'drop' @n xs@ returns the suffix of @xs@
+-- after the first @n@ elements, or @[]@ if @n > 'length' xs@:
+--
+-- > drop 6 "Hello World!" == "World!"
+-- > drop 3 [1,2,3,4,5] == [4,5]
+-- > drop 3 [1,2] == []
+-- > drop 3 [] == []
+-- > drop (-1) [1,2] == [1,2]
+-- > drop 0 [1,2] == [1,2]
+--
+-- It is an instance of the more general 'Data.List.genericDrop',
+-- in which @n@ may be of any integral type.
 drop                   :: Int -> [a] -> [a]
-drop 0 xs              =  xs
-drop _ []              =  []
-drop n (_:xs) | n > 0  =  drop (minusInt n 1) xs
-drop _     _           =  errorNegativeIdx "drop"
 
+-- | 'splitAt' @n xs@ returns a tuple where first element is @xs@ prefix of
+-- length @n@ and second element is the remainder of the list:
+--
+-- > splitAt 6 "Hello World!" == ("Hello ","World!")
+-- > splitAt 3 [1,2,3,4,5] == ([1,2,3],[4,5])
+-- > splitAt 1 [1,2,3] == ([1],[2,3])
+-- > splitAt 3 [1,2,3] == ([1,2,3],[])
+-- > splitAt 4 [1,2,3] == ([1,2,3],[])
+-- > splitAt 0 [1,2,3] == ([],[1,2,3])
+-- > splitAt (-1) [1,2,3] == ([],[1,2,3])
+--
+-- It is equivalent to @('take' n xs, 'drop' n xs)@.
+-- 'splitAt' is an instance of the more general 'Data.List.genericSplitAt',
+-- in which @n@ may be of any integral type.
+splitAt                :: Int -> [a] -> ([a],[a])
 
-splitAt                   :: Int -> [a] -> ([a],[a])
-splitAt 0 xs              =  ([],xs)
-splitAt _ []              =  ([],[])
-splitAt n (x:xs) | n > 0  =  (x:xs',xs'') where (xs',xs'') = splitAt (minusInt n 1) xs
-splitAt _     _           =  errorNegativeIdx "splitAt"
+#ifdef USE_REPORT_PRELUDE
+take n _      | n <= 0 =  []
+take _ []              =  []
+take n (x:xs)          =  x : take (n-1) xs
+
+drop n xs     | n <= 0 =  xs
+drop _ []              =  []
+drop n (_:xs)          =  drop (n-1) xs
+
+splitAt n xs           =  (take n xs, drop n xs)
 
 #else /* hack away */
-take   :: Int -> [b] -> [b]
+{-# RULES
+"take"    [~1] forall n xs . take n xs = takeFoldr n xs 
+"takeList"  [1] forall n xs . foldr (takeFB (:) []) (takeConst []) xs n = takeUInt n xs
+ #-}
+
+{-# INLINE takeFoldr #-}
+takeFoldr :: Int -> [a] -> [a]
+takeFoldr (I# n#) xs
+  = build (\c nil -> if n# <=# 0# then nil else
+                     foldr (takeFB c nil) (takeConst nil) xs n#)
+
+{-# NOINLINE [0] takeConst #-}
+-- just a version of const that doesn't get inlined too early, so we
+-- can spot it in rules.  Also we need a type sig due to the unboxed Int#.
+takeConst :: a -> Int# -> a
+takeConst x _ = x
+
+{-# NOINLINE [0] takeFB #-}
+takeFB :: (a -> b -> b) -> b -> a -> (Int# -> b) -> Int# -> b
+takeFB c n x xs m | m <=# 1#  = x `c` n
+                 | otherwise = x `c` xs (m -# 1#)
+
+{-# INLINE [0] take #-}
 take (I# n#) xs = takeUInt n# xs
 
 -- The general code for take, below, checks n <= maxInt
@@ -290,7 +381,7 @@ take (I# n#) xs = takeUInt n# xs
 takeUInt :: Int# -> [b] -> [b]
 takeUInt n xs
   | n >=# 0#  =  take_unsafe_UInt n xs
-  | otherwise =  errorNegativeIdx "take"
+  | otherwise =  []
 
 take_unsafe_UInt :: Int# -> [b] -> [b]
 take_unsafe_UInt 0#  _  = []
@@ -302,7 +393,7 @@ take_unsafe_UInt m   ls =
 takeUInt_append :: Int# -> [b] -> [b] -> [b]
 takeUInt_append n xs rs
   | n >=# 0#  =  take_unsafe_UInt_append n xs rs
-  | otherwise =  errorNegativeIdx "take"
+  | otherwise =  []
 
 take_unsafe_UInt_append        :: Int# -> [b] -> [b] -> [b]
 take_unsafe_UInt_append        0#  _ rs  = rs
@@ -311,9 +402,8 @@ take_unsafe_UInt_append     m  ls rs  =
     []     -> rs
     (x:xs) -> x : take_unsafe_UInt_append (m -# 1#) xs rs
 
-drop           :: Int -> [b] -> [b]
 drop (I# n#) ls
-  | n# <# 0#   = errorNegativeIdx "drop"
+  | n# <# 0#   = ls
   | otherwise  = drop# n# ls
     where
        drop# :: Int# -> [a] -> [a]
@@ -321,9 +411,8 @@ drop (I# n#) ls
        drop# _  xs@[]   = xs
        drop# m# (_:xs)  = drop# (m# -# 1#) xs
 
-splitAt        :: Int -> [b] -> ([b], [b])
 splitAt (I# n#) ls
-  | n# <# 0#   = errorNegativeIdx "splitAt"
+  | n# <# 0#   = ([], ls)
   | otherwise  = splitAt# n# ls
     where
        splitAt# :: Int# -> [a] -> ([a], [a])
@@ -335,12 +424,33 @@ splitAt (I# n#) ls
 
 #endif /* USE_REPORT_PRELUDE */
 
-span, break             :: (a -> Bool) -> [a] -> ([a],[a])
+-- | 'span', applied to a predicate @p@ and a list @xs@, returns a tuple where
+-- first element is longest prefix (possibly empty) of @xs@ of elements that
+-- satisfy @p@ and second element is the remainder of the list:
+-- 
+-- > span (< 3) [1,2,3,4,1,2,3,4] == ([1,2],[3,4,1,2,3,4])
+-- > span (< 9) [1,2,3] == ([1,2,3],[])
+-- > span (< 0) [1,2,3] == ([],[1,2,3])
+-- 
+-- 'span' @p xs@ is equivalent to @('takeWhile' p xs, 'dropWhile' p xs)@
+
+span                    :: (a -> Bool) -> [a] -> ([a],[a])
 span _ xs@[]            =  (xs, xs)
 span p xs@(x:xs')
          | p x          =  let (ys,zs) = span p xs' in (x:ys,zs)
          | otherwise    =  ([],xs)
 
+-- | 'break', applied to a predicate @p@ and a list @xs@, returns a tuple where
+-- first element is longest prefix (possibly empty) of @xs@ of elements that
+-- /do not satisfy/ @p@ and second element is the remainder of the list:
+-- 
+-- > break (> 3) [1,2,3,4,1,2,3,4] == ([1,2,3],[4,1,2,3,4])
+-- > break (< 9) [1,2,3] == ([],[1,2,3])
+-- > break (> 9) [1,2,3] == ([1,2,3],[])
+--
+-- 'break' @p@ is equivalent to @'span' ('not' . p)@.
+
+break                   :: (a -> Bool) -> [a] -> ([a],[a])
 #ifdef USE_REPORT_PRELUDE
 break p                 =  span (not . p)
 #else
@@ -351,7 +461,8 @@ break p xs@(x:xs')
           | otherwise  =  let (ys,zs) = break p xs' in (x:ys,zs)
 #endif
 
--- reverse xs returns the elements of xs in reverse order.  xs must be finite.
+-- | 'reverse' @xs@ returns the elements of @xs@ in reverse order.
+-- @xs@ must be finite.
 reverse                 :: [a] -> [a]
 #ifdef USE_REPORT_PRELUDE
 reverse                 =  foldl (flip (:)) []
@@ -362,11 +473,15 @@ reverse l =  rev l []
     rev (x:xs) a = rev xs (x:a)
 #endif
 
--- and returns the conjunction of a Boolean list.  For the result to be
--- True, the list must be finite; False, however, results from a False
--- value at a finite index of a finite or infinite list.  or is the
--- disjunctive dual of and.
-and, or                 :: [Bool] -> Bool
+-- | 'and' returns the conjunction of a Boolean list.  For the result to be
+-- 'True', the list must be finite; 'False', however, results from a 'False'
+-- value at a finite index of a finite or infinite list.
+and                     :: [Bool] -> Bool
+
+-- | 'or' returns the disjunction of a Boolean list.  For the result to be
+-- 'False', the list must be finite; 'True', however, results from a 'True'
+-- value at a finite index of a finite or infinite list.
+or                      :: [Bool] -> Bool
 #ifdef USE_REPORT_PRELUDE
 and                     =  foldr (&&) True
 or                      =  foldr (||) False
@@ -384,9 +499,13 @@ or (x:xs)  =  x || or xs
  #-}
 #endif
 
--- Applied to a predicate and a list, any determines if any element
--- of the list satisfies the predicate.  Similarly, for all.
-any, all                :: (a -> Bool) -> [a] -> Bool
+-- | Applied to a predicate and a list, 'any' determines if any element
+-- of the list satisfies the predicate.
+any                     :: (a -> Bool) -> [a] -> Bool
+
+-- | Applied to a predicate and a list, 'all' determines if all elements
+-- of the list satisfy the predicate.
+all                     :: (a -> Bool) -> [a] -> Bool
 #ifdef USE_REPORT_PRELUDE
 any p                   =  or . map p
 all p                   =  and . map p
@@ -404,9 +523,12 @@ all p (x:xs)       =  p x && all p xs
  #-}
 #endif
 
--- elem is the list membership predicate, usually written in infix form,
--- e.g., x `elem` xs.  notElem is the negation.
-elem, notElem           :: (Eq a) => a -> [a] -> Bool
+-- | 'elem' is the list membership predicate, usually written in infix form,
+-- e.g., @x `elem` xs@.
+elem                    :: (Eq a) => a -> [a] -> Bool
+
+-- | 'notElem' is the negation of 'elem'.
+notElem                 :: (Eq a) => a -> [a] -> Bool
 #ifdef USE_REPORT_PRELUDE
 elem x                  =  any (== x)
 notElem x               =  all (/= x)
@@ -418,45 +540,39 @@ notElem   _ []    =  True
 notElem x (y:ys)=  x /= y && notElem x ys
 #endif
 
--- lookup key assocs looks up a key in an association list.
+-- | 'lookup' @key assocs@ looks up a key in an association list.
 lookup                  :: (Eq a) => a -> [(a,b)] -> Maybe b
 lookup _key []          =  Nothing
 lookup  key ((x,y):xys)
     | key == x          =  Just y
     | otherwise         =  lookup key xys
 
-
--- maximum and minimum return the maximum or minimum value from a list,
--- which must be non-empty, finite, and of an ordered type.
-{-# SPECIALISE maximum :: [Int] -> Int #-}
-{-# SPECIALISE minimum :: [Int] -> Int #-}
-maximum, minimum        :: (Ord a) => [a] -> a
-maximum []              =  errorEmptyList "maximum"
-maximum xs              =  foldl1 max xs
-
-minimum []              =  errorEmptyList "minimum"
-minimum xs              =  foldl1 min xs
-
+-- | Map a function over a list and concatenate the results.
 concatMap               :: (a -> [b]) -> [a] -> [b]
 concatMap f             =  foldr ((++) . f) []
 
+-- | Concatenate a list of lists.
 concat :: [[a]] -> [a]
 concat = foldr (++) []
 
 {-# RULES
   "concat" forall xs. concat xs = build (\c n -> foldr (\x y -> foldr c y x) n xs)
+-- We don't bother to turn non-fusible applications of concat back into concat
  #-}
+
 \end{code}
 
 
 \begin{code}
--- List index (subscript) operator, 0-origin
+-- | List index (subscript) operator, starting from 0.
+-- It is an instance of the more general 'Data.List.genericIndex',
+-- which takes an index of any integral type.
 (!!)                    :: [a] -> Int -> a
 #ifdef USE_REPORT_PRELUDE
-(x:_)  !! 0             =  x
-(_:xs) !! n | n > 0     =  xs !! (minusInt n 1)
-(_:_)  !! _             =  error "Prelude.(!!): negative index"
-[]     !! _             =  error "Prelude.(!!): index too large"
+xs     !! n | n < 0 =  error "Prelude.!!: negative index"
+[]     !! _         =  error "Prelude.!!: index too large"
+(x:_)  !! 0         =  x
+(_:xs) !! n         =  xs !! (n-1)
 #else
 -- HBC version (stolen), then unboxified
 -- The semantics is not quite the same for error conditions
@@ -512,31 +628,30 @@ E.g. main = print (null (zip nonobviousNil (build undefined)))
 I'm going to leave it though.
 
 
-zip takes two lists and returns a list of corresponding pairs.  If one
-input list is short, excess elements of the longer list are discarded.
-zip3 takes three lists and returns a list of triples.  Zips for larger
-tuples are in the List module.
+Zips for larger tuples are in the List module.
 
 \begin{code}
 ----------------------------------------------
+-- | 'zip' takes two lists and returns a list of corresponding pairs.
+-- If one input list is short, excess elements of the longer list are
+-- discarded.
 zip :: [a] -> [b] -> [(a,b)]
-zip = zipList
+zip (a:as) (b:bs) = (a,b) : zip as bs
+zip _      _      = []
 
+{-# INLINE [0] zipFB #-}
 zipFB c x y r = (x,y) `c` r
 
-
-zipList               :: [a] -> [b] -> [(a,b)]
-zipList (a:as) (b:bs) = (a,b) : zipList as bs
-zipList _      _      = []
-
 {-# RULES
-"zip"          forall xs ys. zip xs ys = build (\c n -> foldr2 (zipFB c) n xs ys)
-"zipList"      foldr2 (zipFB (:)) []   = zipList
+"zip"     [~1] forall xs ys. zip xs ys = build (\c n -> foldr2 (zipFB c) n xs ys)
+"zipList"  [1] foldr2 (zipFB (:)) []   = zip
  #-}
 \end{code}
 
 \begin{code}
 ----------------------------------------------
+-- | 'zip3' takes three lists and returns a list of triples, analogous to
+-- 'zip'.
 zip3 :: [a] -> [b] -> [c] -> [(a,b,c)]
 -- Specification
 -- zip3 =  zipWith3 (,,)
@@ -547,39 +662,43 @@ zip3 _      _      _      = []
 
 -- The zipWith family generalises the zip family by zipping with the
 -- function given as the first argument, instead of a tupling function.
--- For example, zipWith (+) is applied to two lists to produce the list
--- of corresponding sums.
-
 
 \begin{code}
 ----------------------------------------------
+-- | 'zipWith' generalises 'zip' by zipping with the function given
+-- as the first argument, instead of a tupling function.
+-- For example, @'zipWith' (+)@ is applied to two lists to produce the
+-- list of corresponding sums.
 zipWith :: (a->b->c) -> [a]->[b]->[c]
-zipWith = zipWithList
-
+zipWith f (a:as) (b:bs) = f a b : zipWith f as bs
+zipWith _ _      _      = []
 
+{-# INLINE [0] zipWithFB #-}
 zipWithFB c f x y r = (x `f` y) `c` r
 
-zipWithList                 :: (a->b->c) -> [a] -> [b] -> [c]
-zipWithList f (a:as) (b:bs) = f a b : zipWithList f as bs
-zipWithList _ _      _      = []
-
 {-# RULES
-"zipWith"      forall f xs ys. zipWith f xs ys = build (\c n -> foldr2 (zipWithFB c f) n xs ys)
-"zipWithList"  forall f.       foldr2 (zipWithFB (:) f) [] = zipWithList f
+"zipWith"      [~1] forall f xs ys.    zipWith f xs ys = build (\c n -> foldr2 (zipWithFB c f) n xs ys)
+"zipWithList"  [1]  forall f.  foldr2 (zipWithFB (:) f) [] = zipWith f
   #-}
 \end{code}
 
 \begin{code}
+-- | The 'zipWith3' function takes a function which combines three
+-- elements, as well as three lists and returns a list of their point-wise
+-- combination, analogous to 'zipWith'.
 zipWith3                :: (a->b->c->d) -> [a]->[b]->[c]->[d]
 zipWith3 z (a:as) (b:bs) (c:cs)
                         =  z a b c : zipWith3 z as bs cs
 zipWith3 _ _ _ _        =  []
 
--- unzip transforms a list of pairs into a pair of lists.  
+-- | 'unzip' transforms a list of pairs into a list of first components
+-- and a list of second components.
 unzip    :: [(a,b)] -> ([a],[b])
 {-# INLINE unzip #-}
 unzip    =  foldr (\(a,b) ~(as,bs) -> (a:as,b:bs)) ([],[])
 
+-- | The 'unzip3' function takes a list of triples and returns three
+-- lists, analogous to 'unzip'.
 unzip3   :: [(a,b,c)] -> ([a],[b],[c])
 {-# INLINE unzip3 #-}
 unzip3   =  foldr (\(a,b,c) ~(as,bs,cs) -> (a:as,b:bs,c:cs))
@@ -601,10 +720,6 @@ errorEmptyList :: String -> a
 errorEmptyList fun =
   error (prel_list_str ++ fun ++ ": empty list")
 
-errorNegativeIdx :: String -> a
-errorNegativeIdx fun =
- error (prel_list_str ++ fun ++ ": negative index")
-
 prel_list_str :: String
 prel_list_str = "Prelude."
 \end{code}