X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=GHC%2FList.lhs;h=ce13f467b861248080125837c79327d962b89ea3;hb=ec732e82cf3258adb72c31532df9e7f47a62ff8d;hp=689637e2ea42a52e077cc2ae8862e55b917efc0f;hpb=f5890dc1b5296b44d036df768641e2be29075d12;p=haskell-directory.git

diff --git a/GHC/List.lhs b/GHC/List.lhs
index 689637e..ce13f46 100644
--- a/GHC/List.lhs
+++ b/GHC/List.lhs
@@ -111,21 +111,12 @@ null (_:_)              =  False
 -- | '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 = lenAcc 0# l
-
-{-# RULES
-"length" [~1] forall xs. length xs = foldr incL (I# 0#) xs
-"lenAcc" [1]  forall n#. foldr incL (I# n#) = lenAcc n#
- #-}
-
-incL :: a -> Int -> Int		-- Internal
-{-# NOINLINE [0] incL #-}
-incL x n = n `plusInt` oneInt
-
-lenAcc :: Int# -> [a] -> Int	-- Internal
-lenAcc a# []     = I# a#
-lenAcc a# (_:xs) = lenAcc (a# +# 1#) xs
+length                  :: [a] -> Int
+length l                =  len l 0#
+  where
+    len :: [a] -> Int# -> Int
+    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.,
@@ -276,7 +267,12 @@ 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@.
+-- 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 _ []          =  []
@@ -284,7 +280,12 @@ takeWhile p (x:xs)
             | p x       =  x : takeWhile p xs
             | otherwise =  []
 
--- | 'dropWhile' @p xs@ returns the suffix remaining after 'takeWhile' @p xs@.
+-- | '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 _ []          =  []
@@ -293,19 +294,46 @@ dropWhile p xs@(x: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@.
+-- 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]
 
 -- | 'drop' @n xs@ returns the suffix of @xs@
--- after the first @n@ elements, or @[]@ if @n > 'length' 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]
 
--- | 'splitAt' @n xs@ is equivalent to @('take' n xs, 'drop' n xs)@.
--- It is an instance of the more general 'Data.List.genericSplitAt',
+-- | '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])
 
@@ -322,10 +350,16 @@ splitAt n xs           =  (take n xs, drop n xs)
 
 #else /* hack away */
 {-# RULES
-"take"	   [~1] forall n xs . take n xs = case n of I# n# -> build (\c nil -> foldr (takeFB c nil) (takeConst nil) xs n#)
+"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#.
@@ -333,8 +367,8 @@ takeConst :: a -> Int# -> a
 takeConst x _ = x
 
 {-# NOINLINE [0] takeFB #-}
-takeFB :: (a -> b -> c) -> c -> a -> (Int# -> b) -> Int# -> c
-takeFB c n x xs m | m <=# 0#  = n
+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 #-}
@@ -390,7 +424,15 @@ splitAt (I# n#) ls
 
 #endif /* USE_REPORT_PRELUDE */
 
--- | 'span' @p xs@ is equivalent to @('takeWhile' p xs, 'dropWhile' p xs)@
+-- | '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)
@@ -398,7 +440,15 @@ span p xs@(x:xs')
          | p x          =  let (ys,zs) = span p xs' in (x:ys,zs)
          | otherwise    =  ([],xs)
 
--- | 'break' @p@ is equivalent to @'span' ('not' . p)@.
+-- | '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