X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=Data%2FList.hs;h=b6a847b3e01eb7c03827014fea252c7b50f7e5cd;hb=4b26136ab82fb1ff12e49477c4833a9586d368c5;hp=7d4cf51d2f877e1be1d00336cd64e1edc6d084bd;hpb=7ae1d0ce9df2c5d7fd5edc8d613061c8c5c14c02;p=haskell-directory.git diff --git a/Data/List.hs b/Data/List.hs index 7d4cf51..b6a847b 100644 --- a/Data/List.hs +++ b/Data/List.hs @@ -1,4 +1,4 @@ -{-# OPTIONS -fno-implicit-prelude #-} +{-# OPTIONS_GHC -fno-implicit-prelude #-} ----------------------------------------------------------------------------- -- | -- Module : Data.List @@ -35,6 +35,7 @@ module Data.List , reverse -- :: [a] -> [a] , intersperse -- :: a -> [a] -> [a] + , intercalate -- :: [a] -> [[a]] -> [a] , transpose -- :: [[a]] -> [[a]] -- * Reducing lists (folds) @@ -42,6 +43,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 +101,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 @@ -165,6 +168,10 @@ module Data.List -- ** The \"@By@\" operations -- | By convention, overloaded functions have a non-overloaded -- counterpart whose name is suffixed with \`@By@\'. + -- + -- It is often convenient to use these functions together with + -- 'Data.Function.on', for instance @'sortBy' ('compare' + -- \`on\` 'fst')@. -- *** User-supplied equality (replacing an @Eq@ context) -- | The predicate is assumed to define an equivalence. @@ -265,6 +272,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\'.) @@ -383,6 +401,12 @@ intersperse _ [] = [] 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, -- @@ -454,6 +478,8 @@ 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 @@ -462,14 +488,17 @@ maximum :: (Ord a) => [a] -> a maximum [] = errorEmptyList "maximum" maximum xs = foldl1 max xs -{-# RULES "maximumInt" maximum = maximumInt #-} +{-# 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'. -maximumInt :: [Int] -> Int -maximumInt [] = errorEmptyList "maximum" -maximumInt xs = foldl1' max xs +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. @@ -479,11 +508,16 @@ minimum :: (Ord a) => [a] -> a minimum [] = errorEmptyList "minimum" minimum xs = foldl1 min xs -{-# RULES "minimumInt" minimum = minimumInt #-} +{-# RULES + "minimumInt" minimum = (strictMinimum :: [Int] -> Int); + "minimumInteger" minimum = (strictMinimum :: [Integer] -> Integer) + #-} -minimumInt :: [Int] -> Int -minimumInt [] = errorEmptyList "minimum" -minimumInt xs = foldl1' min xs +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. @@ -821,7 +855,12 @@ rqpart cmp x (y:ys) rle rgt r = -- -- > f' (f x y) = Just (x,y) -- > f' z = Nothing - +-- +-- A simple use of unfoldr: +-- +-- > unfoldr (\b -> if b == 0 then Nothing else Just (b, b-1)) 10 +-- > [10,9,8,7,6,5,4,3,2,1] +-- unfoldr :: (b -> Maybe (a, b)) -> b -> [a] unfoldr f b = case f b of @@ -835,11 +874,13 @@ foldl' :: (a -> b -> a) -> a -> [b] -> a 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 @@ -918,4 +959,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__ */