Remove Data.FiniteMap, add Control.Applicative, Data.Traversable, and

[haskell-directory.git] / Data / List.hs

diff --git a/Data/List.hs b/Data/List.hs
index 90fccbe..7c3cede 100644 (file)
--- a/Data/List.hs
+++ b/Data/List.hs
@@ -1,4 +1,4 @@
-{-# OPTIONS -fno-implicit-prelude #-}
+{-# OPTIONS_GHC -fno-implicit-prelude #-}
 -----------------------------------------------------------------------------
 -- |
 -- Module      :  Data.List
@@ -42,6 +42,7 @@ module Data.List
    , 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
 
@@ -99,6 +100,7 @@ module Data.List
    -- ** Predicates
    , isPrefixOf        -- :: (Eq a) => [a] -> [a] -> Bool
    , isSuffixOf        -- :: (Eq a) => [a] -> [a] -> Bool
+   , isInfixOf         -- :: (Eq a) => [a] -> [a] -> Bool
 
    -- * Searching lists
 
@@ -265,6 +267,17 @@ isPrefixOf (x:xs) (y:ys)=  x == y && isPrefixOf xs ys
 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\'.)
@@ -454,6 +467,47 @@ insertBy cmp x ys@(y:ys')
      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.
@@ -805,6 +859,19 @@ foldl' f a []     = a
 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
 
@@ -876,4 +943,11 @@ unwords []         =  ""
 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__ */