-{-# OPTIONS -fno-implicit-prelude #-}
+{-# OPTIONS_GHC -fno-implicit-prelude #-}
-----------------------------------------------------------------------------
-- |
-- Module : Data.List
-- License : BSD-style (see the file libraries/base/LICENSE)
--
-- Maintainer : libraries@haskell.org
--- Stability : provisional
+-- Stability : stable
-- Portability : portable
--
-- Operations on lists.
, reverse -- :: [a] -> [a]
, intersperse -- :: a -> [a] -> [a]
+ , intercalate -- :: [a] -> [[a]] -> [a]
, transpose -- :: [[a]] -> [[a]]
-- * Reducing lists (folds)
, foldl -- :: (a -> b -> a) -> a -> [b] -> a
, foldl' -- :: (a -> b -> a) -> a -> [b] -> a
, foldl1 -- :: (a -> a -> a) -> [a] -> a
+ , foldl1' -- :: (a -> a -> a) -> [a] -> a
, foldr -- :: (a -> b -> b) -> b -> [a] -> b
, foldr1 -- :: (a -> a -> a) -> [a] -> a
-- ** Predicates
, isPrefixOf -- :: (Eq a) => [a] -> [a] -> Bool
, isSuffixOf -- :: (Eq a) => [a] -> [a] -> Bool
+ , isInfixOf -- :: (Eq a) => [a] -> [a] -> Bool
-- * Searching lists
import GHC.Base
#endif
-infix 5 \\
+infix 5 \\ -- comment to fool cpp
-- -----------------------------------------------------------------------------
-- List functions
isSuffixOf :: (Eq a) => [a] -> [a] -> Bool
isSuffixOf x y = reverse x `isPrefixOf` reverse y
+-- | The 'isInfixOf' function takes two lists and returns 'True'
+-- iff the first list is contained, wholly and intact,
+-- anywhere within the second.
+--
+-- Example:
+--
+-- >isInfixOf "Haskell" "I really like Haskell." -> True
+-- >isInfixOf "Ial" "I really like Haskell." -> False
+isInfixOf :: (Eq a) => [a] -> [a] -> Bool
+isInfixOf needle haystack = any (isPrefixOf needle) (tails haystack)
+
-- | The 'nub' function removes duplicate elements from a list.
-- In particular, it keeps only the first occurrence of each element.
-- (The name 'nub' means \`essence\'.)
intersperse _ [x] = [x]
intersperse sep (x:xs) = x : sep : intersperse sep xs
+-- | 'intercalate' @xs xss@ is equivalent to @('concat' ('intersperse' xs xss))@.
+-- It inserts the list @xs@ in between the lists in @xss@ and concatenates the
+-- result.
+intercalate :: [a] -> [[a]] -> [a]
+intercalate xs xss = concat (intersperse xs xss)
+
-- | The 'transpose' function transposes the rows and columns of its argument.
-- For example,
--
{-# INLINE partition #-}
partition p xs = foldr (select p) ([],[]) xs
-select p x (ts,fs) | p x = (x:ts,fs)
- | otherwise = (ts, x:fs)
+select p x ~(ts,fs) | p x = (x:ts,fs)
+ | otherwise = (ts, x:fs)
-- | The 'mapAccumL' function behaves like a combination of 'map' and
-- 'foldl'; it applies a function to each element of a list, passing
GT -> y : insertBy cmp x ys'
_ -> x : ys
+#ifdef __GLASGOW_HASKELL__
+
+-- | '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
+
+{-# RULES
+ "maximumInt" maximum = (strictMaximum :: [Int] -> Int);
+ "maximumInteger" maximum = (strictMaximum :: [Integer] -> Integer)
+ #-}
+
+-- We can't make the overloaded version of maximum strict without
+-- changing its semantics (max might not be strict), but we can for
+-- the version specialised to 'Int'.
+strictMaximum :: (Ord a) => [a] -> a
+strictMaximum [] = errorEmptyList "maximum"
+strictMaximum 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
+
+{-# RULES
+ "minimumInt" minimum = (strictMinimum :: [Int] -> Int);
+ "minimumInteger" minimum = (strictMinimum :: [Integer] -> Integer)
+ #-}
+
+strictMinimum :: (Ord a) => [a] -> a
+strictMinimum [] = errorEmptyList "minimum"
+strictMinimum xs = foldl1' min xs
+
+#endif /* __GLASGOW_HASKELL__ */
+
-- | The 'maximumBy' function takes a comparison function and a list
-- and returns the greatest element of the list by the comparison function.
-- The list must be finite and non-empty.
foldl' f a (x:xs) = let a' = f a x in a' `seq` foldl' f a' xs
#ifdef __GLASGOW_HASKELL__
+-- | '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"
+#endif /* __GLASGOW_HASKELL__ */
+
+-- | A strict version of 'foldl1'
+foldl1' :: (a -> a -> a) -> [a] -> a
+foldl1' f (x:xs) = foldl' f x xs
+foldl1' _ [] = errorEmptyList "foldl1'"
+
+#ifdef __GLASGOW_HASKELL__
-- -----------------------------------------------------------------------------
-- List sum and product
unwords [w] = w
unwords (w:ws) = w ++ ' ' : unwords ws
#endif
-#endif /* __GLASGOW_HASKELL__ */
+
+#else /* !__GLASGOW_HASKELL__ */
+
+errorEmptyList :: String -> a
+errorEmptyList fun =
+ error ("Prelude." ++ fun ++ ": empty list")
+
+#endif /* !__GLASGOW_HASKELL__ */