\begin{code}
-{-# OPTIONS -fno-implicit-prelude #-}
+{-# OPTIONS_GHC -fno-implicit-prelude #-}
-----------------------------------------------------------------------------
-- |
-- Module : GHC.List
--
-----------------------------------------------------------------------------
+-- #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
-- 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)
lgo z [] = z
lgo z (x:xs) = lgo (f z x) xs
--- | 'foldl1' is a variant of 'foldl' that has no starting value argument,
--- and thus must be applied to non-empty lists.
-
-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:
--
-- 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 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 _ [] = []
| 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 _ [] = []
| 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])
splitAt n xs = (take n xs, drop n xs)
#else /* hack away */
+{-# 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
(x:xs) -> x : take_unsafe_UInt_append (m -# 1#) xs rs
drop (I# n#) ls
- | n# <# 0# = []
+ | n# <# 0# = ls
| otherwise = drop# n# ls
where
drop# :: Int# -> [a] -> [a]
#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)
| 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
| key == x = Just y
| otherwise = lookup key xys
-{-# SPECIALISE maximum :: [Int] -> Int #-}
-{-# SPECIALISE minimum :: [Int] -> Int #-}
-
--- | 'maximum' returns the maximum value from a list,
--- which must be non-empty, finite, and of an ordered type.
--- It is a special case of 'Data.List.maximumBy', which allows the
--- programmer to supply their own comparison function.
-maximum :: (Ord a) => [a] -> a
-maximum [] = errorEmptyList "maximum"
-maximum xs = foldl1 max xs
-
--- | 'minimum' returns the minimum value from a list,
--- which must be non-empty, finite, and of an ordered type.
--- It is a special case of 'Data.List.minimumBy', which allows the
--- programmer to supply their own comparison function.
-minimum :: (Ord a) => [a] -> a
-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) []
projects / haskell-directory.git / blobdiff