\begin{code}
-{-# OPTIONS -fno-implicit-prelude #-}
+{-# OPTIONS_GHC -fno-implicit-prelude #-}
-----------------------------------------------------------------------------
-- |
-- Module : GHC.List
--
-----------------------------------------------------------------------------
+-- #hide
module GHC.List (
-- [] (..), -- Not Haskell 98; built in syntax
) where
import {-# SOURCE #-} GHC.Err ( error )
-import Data.Tuple
+import Data.Tuple() -- Instances
import Data.Maybe
import GHC.Base
-- 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)
-- | '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
- len :: [a] -> Int# -> Int
- len [] a# = I# a#
- len (_:xs) a# = len xs (a# +# 1#)
+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
-- | 'filter', applied to a predicate and a list, returns the list of
-- those elements that satisfy the predicate; i.e.,
-- 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)
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#)
+"takeList" [1] forall n xs . foldr (takeFB (:) []) (takeConst []) xs n = takeUInt n xs
+ #-}
+
+{-# 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 -> c) -> c -> a -> (Int# -> b) -> Int# -> c
+takeFB c n x xs m | m <=# 0# = 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