From 69daab60bb6f89433a0394182481d721dc2f42fd Mon Sep 17 00:00:00 2001 From: ross Date: Mon, 1 Sep 2003 09:12:07 +0000 Subject: [PATCH] [project @ 2003-09-01 09:12:02 by ross] H98 docs for Data.List --- Data/List.hs | 506 +++++++++++++++++++++++++++++++++++----------------------- GHC/Base.lhs | 19 +++ GHC/List.lhs | 213 ++++++++++++++++-------- Prelude.hs | 84 ++++++---- 4 files changed, 526 insertions(+), 296 deletions(-) diff --git a/Data/List.hs b/Data/List.hs index fb1606d..c3b5df6 100644 --- a/Data/List.hs +++ b/Data/List.hs @@ -19,120 +19,179 @@ module Data.List [] (..) , #endif - elemIndex -- :: (Eq a) => a -> [a] -> Maybe Int - , elemIndices -- :: (Eq a) => a -> [a] -> [Int] - - , find -- :: (a -> Bool) -> [a] -> Maybe a - , findIndex -- :: (a -> Bool) -> [a] -> Maybe Int - , findIndices -- :: (a -> Bool) -> [a] -> [Int] - - , nub -- :: (Eq a) => [a] -> [a] - , nubBy -- :: (a -> a -> Bool) -> [a] -> [a] - - , delete -- :: (Eq a) => a -> [a] -> [a] - , deleteBy -- :: (a -> a -> Bool) -> a -> [a] -> [a] - , (\\) -- :: (Eq a) => [a] -> [a] -> [a] - , deleteFirstsBy -- :: (a -> a -> Bool) -> [a] -> [a] -> [a] - - , union -- :: (Eq a) => [a] -> [a] -> [a] - , unionBy -- :: (a -> a -> Bool) -> [a] -> [a] -> [a] - - , intersect -- :: (Eq a) => [a] -> [a] -> [a] - , intersectBy -- :: (a -> a -> Bool) -> [a] -> [a] -> [a] - - , intersperse -- :: a -> [a] -> [a] - , transpose -- :: [[a]] -> [[a]] - , partition -- :: (a -> Bool) -> [a] -> ([a], [a]) - - , group -- :: Eq a => [a] -> [[a]] - , groupBy -- :: (a -> a -> Bool) -> [a] -> [[a]] - - , inits -- :: [a] -> [[a]] - , tails -- :: [a] -> [[a]] - , isPrefixOf -- :: (Eq a) => [a] -> [a] -> Bool - , isSuffixOf -- :: (Eq a) => [a] -> [a] -> Bool - - , mapAccumL -- :: (a -> b -> (a,c)) -> a -> [b] -> (a,[c]) - , mapAccumR -- :: (a -> b -> (a,c)) -> a -> [b] -> (a,[c]) - - , sort -- :: (Ord a) => [a] -> [a] - , sortBy -- :: (a -> a -> Ordering) -> [a] -> [a] - - , insert -- :: (Ord a) => a -> [a] -> [a] - , insertBy -- :: (a -> a -> Ordering) -> a -> [a] -> [a] - - , maximumBy -- :: (a -> a -> Ordering) -> [a] -> a - , minimumBy -- :: (a -> a -> Ordering) -> [a] -> a - - , genericLength -- :: (Integral a) => [b] -> a - , genericTake -- :: (Integral a) => a -> [b] -> [b] - , genericDrop -- :: (Integral a) => a -> [b] -> [b] - , genericSplitAt -- :: (Integral a) => a -> [b] -> ([b], [b]) - , genericIndex -- :: (Integral a) => [b] -> a -> b - , genericReplicate -- :: (Integral a) => a -> b -> [b] - - , unfoldr -- :: (b -> Maybe (a, b)) -> b -> [a] + -- * Basic functions - , zip4, zip5, zip6, zip7 - , zipWith4, zipWith5, zipWith6, zipWith7 - , unzip4, unzip5, unzip6, unzip7 - - , map -- :: ( a -> b ) -> [a] -> [b] - , (++) -- :: [a] -> [a] -> [a] - , concat -- :: [[a]] -> [a] - , filter -- :: (a -> Bool) -> [a] -> [a] + (++) -- :: [a] -> [a] -> [a] , head -- :: [a] -> a , last -- :: [a] -> a , tail -- :: [a] -> [a] , init -- :: [a] -> [a] , null -- :: [a] -> Bool , length -- :: [a] -> Int - , (!!) -- :: [a] -> Int -> a + + -- * List transformations + , map -- :: (a -> b) -> [a] -> [b] + , reverse -- :: [a] -> [a] + + , intersperse -- :: 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 - , scanl -- :: (a -> b -> a) -> a -> [b] -> [a] - , scanl1 -- :: (a -> a -> a) -> [a] -> [a] , foldr -- :: (a -> b -> b) -> b -> [a] -> b , foldr1 -- :: (a -> a -> a) -> [a] -> a + + -- ** Special folds + + , concat -- :: [[a]] -> [a] + , concatMap -- :: (a -> [b]) -> [a] -> [b] + , and -- :: [Bool] -> Bool + , or -- :: [Bool] -> Bool + , any -- :: (a -> Bool) -> [a] -> Bool + , all -- :: (a -> Bool) -> [a] -> Bool + , sum -- :: (Num a) => [a] -> a + , product -- :: (Num a) => [a] -> a + , maximum -- :: (Ord a) => [a] -> a + , minimum -- :: (Ord a) => [a] -> a + + -- * Building lists + + -- ** Scans + , scanl -- :: (a -> b -> a) -> a -> [b] -> [a] + , scanl1 -- :: (a -> a -> a) -> [a] -> [a] , scanr -- :: (a -> b -> b) -> b -> [a] -> [b] , scanr1 -- :: (a -> a -> a) -> [a] -> [a] + + -- ** Accumulating maps + , mapAccumL -- :: (a -> b -> (a,c)) -> a -> [b] -> (a,[c]) + , mapAccumR -- :: (a -> b -> (a,c)) -> a -> [b] -> (a,[c]) + + -- ** Infinite lists , iterate -- :: (a -> a) -> a -> [a] , repeat -- :: a -> [a] , replicate -- :: Int -> a -> [a] , cycle -- :: [a] -> [a] + + -- ** Unfolding + , unfoldr -- :: (b -> Maybe (a, b)) -> b -> [a] + + -- * Sublists + + -- ** Extracting sublists , take -- :: Int -> [a] -> [a] , drop -- :: Int -> [a] -> [a] , splitAt -- :: Int -> [a] -> ([a], [a]) + , takeWhile -- :: (a -> Bool) -> [a] -> [a] , dropWhile -- :: (a -> Bool) -> [a] -> [a] , span -- :: (a -> Bool) -> [a] -> ([a], [a]) , break -- :: (a -> Bool) -> [a] -> ([a], [a]) - , lines -- :: String -> [String] - , words -- :: String -> [String] - , unlines -- :: [String] -> String - , unwords -- :: [String] -> String - , reverse -- :: [a] -> [a] - , and -- :: [Bool] -> Bool - , or -- :: [Bool] -> Bool - , any -- :: (a -> Bool) -> [a] -> Bool - , all -- :: (a -> Bool) -> [a] -> Bool + , group -- :: Eq a => [a] -> [[a]] + + , inits -- :: [a] -> [[a]] + , tails -- :: [a] -> [[a]] + + -- ** Predicates + , isPrefixOf -- :: (Eq a) => [a] -> [a] -> Bool + , isSuffixOf -- :: (Eq a) => [a] -> [a] -> Bool + + -- * Searching lists + + -- ** Searching by equality , elem -- :: a -> [a] -> Bool , notElem -- :: a -> [a] -> Bool , lookup -- :: (Eq a) => a -> [(a,b)] -> Maybe b - , sum -- :: (Num a) => [a] -> a - , product -- :: (Num a) => [a] -> a - , maximum -- :: (Ord a) => [a] -> a - , minimum -- :: (Ord a) => [a] -> a - , concatMap -- :: (a -> [b]) -> [a] -> [b] + + -- ** Searching with a predicate + , find -- :: (a -> Bool) -> [a] -> Maybe a + , filter -- :: (a -> Bool) -> [a] -> [a] + , partition -- :: (a -> Bool) -> [a] -> ([a], [a]) + + -- * Indexing lists + -- | These functions treat a list @xs@ as a indexed collection, + -- with indices ranging from 0 to @'length' xs - 1@. + + , (!!) -- :: [a] -> Int -> a + + , elemIndex -- :: (Eq a) => a -> [a] -> Maybe Int + , elemIndices -- :: (Eq a) => a -> [a] -> [Int] + + , findIndex -- :: (a -> Bool) -> [a] -> Maybe Int + , findIndices -- :: (a -> Bool) -> [a] -> [Int] + + -- * Zipping and unzipping lists + , zip -- :: [a] -> [b] -> [(a,b)] , zip3 + , zip4, zip5, zip6, zip7 + , zipWith -- :: (a -> b -> c) -> [a] -> [b] -> [c] , zipWith3 + , zipWith4, zipWith5, zipWith6, zipWith7 + , unzip -- :: [(a,b)] -> ([a],[b]) , unzip3 + , unzip4, unzip5, unzip6, unzip7 + + -- * Special lists + + -- ** Functions on strings + , lines -- :: String -> [String] + , words -- :: String -> [String] + , unlines -- :: [String] -> String + , unwords -- :: [String] -> String + + -- ** \"Set\" operations + + , nub -- :: (Eq a) => [a] -> [a] + + , delete -- :: (Eq a) => a -> [a] -> [a] + , (\\) -- :: (Eq a) => [a] -> [a] -> [a] + + , union -- :: (Eq a) => [a] -> [a] -> [a] + , intersect -- :: (Eq a) => [a] -> [a] -> [a] + + -- ** Ordered lists + , sort -- :: (Ord a) => [a] -> [a] + , insert -- :: (Ord a) => a -> [a] -> [a] + + -- * Generalized functions + + -- ** The \"@By@\" operations + -- | By convention, overloaded functions have a non-overloaded + -- counterpart whose name is suffixed with \`@By@\'. + + -- *** User-supplied equality (replacing an @Eq@ context) + -- | The predicate is assumed to define an equivalence. + , nubBy -- :: (a -> a -> Bool) -> [a] -> [a] + , deleteBy -- :: (a -> a -> Bool) -> a -> [a] -> [a] + , deleteFirstsBy -- :: (a -> a -> Bool) -> [a] -> [a] -> [a] + , unionBy -- :: (a -> a -> Bool) -> [a] -> [a] -> [a] + , intersectBy -- :: (a -> a -> Bool) -> [a] -> [a] -> [a] + , groupBy -- :: (a -> a -> Bool) -> [a] -> [[a]] + + -- *** User-supplied comparison (replacing an @Ord@ context) + -- | The function is assumed to define a total ordering. + , sortBy -- :: (a -> a -> Ordering) -> [a] -> [a] + , insertBy -- :: (a -> a -> Ordering) -> a -> [a] -> [a] + , maximumBy -- :: (a -> a -> Ordering) -> [a] -> a + , minimumBy -- :: (a -> a -> Ordering) -> [a] -> a + + -- ** The \"@generic@\" operations + -- | The prefix \`@generic@\' indicates an overloaded function that + -- is a generalized version of a "Prelude" function. + + , genericLength -- :: (Integral a) => [b] -> a + , genericTake -- :: (Integral a) => a -> [b] -> [b] + , genericDrop -- :: (Integral a) => a -> [b] -> [b] + , genericSplitAt -- :: (Integral a) => a -> [b] -> ([b], [b]) + , genericIndex -- :: (Integral a) => [b] -> a -> b + , genericReplicate -- :: (Integral a) => a -> b -> [b] ) where @@ -155,32 +214,31 @@ infix 5 \\ -- ----------------------------------------------------------------------------- -- List functions --- | The 'elemIndex' function finds the first element in the given list --- which is equal (by '(==)') to the query element. It returns the 0-based --- index of that element. The function returns 'Nothing' if the element --- is not found in the list. +-- | The 'elemIndex' function returns the index of the first element +-- in the given list which is equal (by '==') to the query element, +-- or 'Nothing' if there is no such element. elemIndex :: Eq a => a -> [a] -> Maybe Int elemIndex x = findIndex (x==) --- | The 'elemIndices' function behaves similarly to 'elemIndex', except --- it returns the indices of all matching elements, not just the first. +-- | The 'elemIndices' function extends 'elemIndex', by returning the +-- indices of all elements equal to the query element, in ascending order. elemIndices :: Eq a => a -> [a] -> [Int] elemIndices x = findIndices (x==) -- | The 'find' function takes a predicate and a list and returns the --- first element in the list matching the predicate, or Nothing if no --- such element exists. +-- first element in the list matching the predicate, or 'Nothing' if +-- there is no such element. find :: (a -> Bool) -> [a] -> Maybe a find p = listToMaybe . filter p -- | The 'findIndex' function takes a predicate and a list and returns --- the index of the first elemen in the list matching the predicate, or --- Nothing if no such element exists. +-- the index of the first element in the list satisfying the predicate, +-- or 'Nothing' if there is no such element. findIndex :: (a -> Bool) -> [a] -> Maybe Int findIndex p = listToMaybe . findIndices p --- | The 'findIndices' function behaves like 'findIndex', but returns --- all matching indices. +-- | The 'findIndices' function extends 'findIndex', by returning the +-- indices of all elements satisfying the predicate, in ascending order. findIndices :: (a -> Bool) -> [a] -> [Int] #if defined(USE_REPORT_PRELUDE) || !defined(__GLASGOW_HASKELL__) @@ -194,19 +252,24 @@ findIndices p ls = loop 0# ls | otherwise = loop (n +# 1#) xs #endif /* USE_REPORT_PRELUDE */ --- | The 'isPrefixOf' function takes two lists and returns True +-- | The 'isPrefixOf' function takes two lists and returns 'True' -- iff the first list is a prefix of the second. isPrefixOf :: (Eq a) => [a] -> [a] -> Bool isPrefixOf [] _ = True isPrefixOf _ [] = False isPrefixOf (x:xs) (y:ys)= x == y && isPrefixOf xs ys +-- | The 'isSuffixOf' function takes two lists and returns 'True' +-- iff the first list is a suffix of the second. +-- Both lists must be finite. isSuffixOf :: (Eq a) => [a] -> [a] -> Bool isSuffixOf x y = reverse x `isPrefixOf` reverse y --- nub (meaning "essence") remove duplicate elements from its list argument. --- | The 'nub' function removes duplicate elements from a list. In particular, --- it keeps only the first occurance of each element. (The name `nub' means `essence'.) +-- | 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\'.) +-- It is a special case of 'nubBy', which allows the programmer to supply +-- their own equality test. nub :: (Eq a) => [a] -> [a] #ifdef USE_REPORT_PRELUDE nub = nubBy (==) @@ -221,7 +284,7 @@ nub l = nub' l [] -- ' #endif -- | The 'nubBy' function behaves just like 'nub', except it uses a --- user-supplied equality predicate instead of the overloaded '(==)' +-- user-supplied equality predicate instead of the overloaded '==' -- function. nubBy :: (a -> a -> Bool) -> [a] -> [a] #ifdef USE_REPORT_PRELUDE @@ -246,9 +309,14 @@ elem_by eq y (x:xs) = x `eq` y || elem_by eq y xs #endif --- delete x removes the first occurrence of x from its list argument. --- | The 'delete' function takes an element and a list and removes the --- first occurance of the elemtn from the list. +-- | 'delete' @x@ removes the first occurrence of @x@ from its list argument. +-- For example, +-- +-- > delete 'a' "banana" == "bnana" +-- +-- It is a special case of 'deleteBy', which allows the programmer to +-- supply their own equality test. + delete :: (Eq a) => a -> [a] -> [a] delete = deleteBy (==) @@ -258,18 +326,29 @@ deleteBy :: (a -> a -> Bool) -> a -> [a] -> [a] deleteBy _ _ [] = [] deleteBy eq x (y:ys) = if x `eq` y then ys else y : deleteBy eq x ys --- list difference (non-associative). In the result of xs \\ ys, --- the first occurrence of each element of ys in turn (if any) --- has been removed from xs. Thus, (xs ++ ys) \\ xs == ys. --- | The '(\\)' function is list difference. In particular, the --- first occurance of each element of the second argument is --- removed from the first argument (once). +-- | The '\\' function is list difference ((non-associative). +-- In the result of @xs@ '\\' @ys@, the first occurrence of each element of +-- @ys@ in turn (if any) has been removed from @xs@. Thus +-- +-- > (xs ++ ys) \\ xs == ys. +-- +-- It is a special case of 'deleteFirstsBy', which allows the programmer +-- to supply their own equality test. + (\\) :: (Eq a) => [a] -> [a] -> [a] (\\) = foldl (flip delete) --- List union, remove the elements of first list from second. -- | The 'union' function returns the list union of the two lists. --- If the first list contains duplicates, so will the result. +-- For example, +-- +-- > "dog" `union` "cow" == "dogcw" +-- +-- Duplicates, and elements of the first list, are removed from the +-- the second list, but if the first list contains duplicates, so will +-- the result. +-- It is a special case of 'unionBy', which allows the programmer to supply +-- their own equality test. + union :: (Eq a) => [a] -> [a] -> [a] union = unionBy (==) @@ -278,7 +357,14 @@ unionBy :: (a -> a -> Bool) -> [a] -> [a] -> [a] unionBy eq xs ys = xs ++ foldl (flip (deleteBy eq)) (nubBy eq ys) xs -- | The 'intersect' function takes the list intersection of two lists. +-- For example, +-- +-- > [1,2,3,4] `intersect` [2,4,6,8] == [2,4] +-- -- If the first list contains duplicates, so will the result. +-- It is a special case of 'intersectBy', which allows the programmer to +-- supply their own equality test. + intersect :: (Eq a) => [a] -> [a] -> [a] intersect = intersectBy (==) @@ -286,29 +372,34 @@ intersect = intersectBy (==) intersectBy :: (a -> a -> Bool) -> [a] -> [a] -> [a] intersectBy eq xs ys = [x | x <- xs, any (eq x) ys] --- intersperse sep inserts sep between the elements of its list argument. --- e.g. intersperse ',' "abcde" == "a,b,c,d,e" --- | The 'intersperse' function takes an element and a list and `intersperses' --- that element between the elements of the list. +-- | The 'intersperse' function takes an element and a list and +-- \`intersperses\' that element between the elements of the list. +-- For example, +-- +-- > intersperse ',' "abcde" == "a,b,c,d,e" + intersperse :: a -> [a] -> [a] intersperse _ [] = [] intersperse _ [x] = [x] intersperse sep (x:xs) = x : sep : intersperse sep xs --- | The 'transpose' function performs matrix transposition on its argument. +-- | The 'transpose' function transposes the rows and columns of its argument. +-- For example, +-- +-- > transpose [[1,2,3],[4,5,6]] == [[1,4],[2,5],[3,6]] + transpose :: [[a]] -> [[a]] transpose [] = [] transpose ([] : xss) = transpose xss transpose ((x:xs) : xss) = (x : [h | (h:t) <- xss]) : transpose (xs : [ t | (h:t) <- xss]) --- partition takes a predicate and a list and returns a pair of lists: --- those elements of the argument list that do and do not satisfy the --- predicate, respectively; i,e,, --- partition p xs == (filter p xs, filter (not . p) xs). -- | The 'partition' function takes a predicate a list and returns -- the pair of lists of elements which do and do not satisfy the --- predicate. +-- predicate, respectively; i.e., +-- +-- > partition p xs == (filter p xs, filter (not . p) xs) + partition :: (a -> Bool) -> [a] -> ([a],[a]) {-# INLINE partition #-} partition p xs = foldr (select p) ([],[]) xs @@ -316,16 +407,10 @@ partition p xs = foldr (select p) ([],[]) xs select p x (ts,fs) | p x = (x:ts,fs) | otherwise = (ts, x:fs) --- @mapAccumL@ behaves like a combination --- of @map@ and @foldl@; --- it applies a function to each element of a list, passing an accumulating --- parameter from left to right, and returning a final value of this --- accumulator together with the new list. - -- | The 'mapAccumL' function behaves like a combination of 'map' and --- 'foldl'. In particular, it applies a function to each element of alist, --- passing an accumulating parameter from left to right, and returning a --- final value of this accumulator together with the new list. +-- 'foldl'; it applies a function to each element of a list, passing +-- an accumulating parameter from left to right, and returning a final +-- value of this accumulator together with the new list. mapAccumL :: (acc -> x -> (acc, y)) -- Function of elt of input list -- and accumulator, returning new -- accumulator and elt of result list @@ -337,13 +422,10 @@ mapAccumL f s (x:xs) = (s'',y:ys) where (s', y ) = f s x (s'',ys) = mapAccumL f s' xs --- @mapAccumR@ does the same, but working from right to left instead. --- Its type is the same as @mapAccumL@, though. - -- | The 'mapAccumR' function behaves like a combination of 'map' and --- 'foldr'. In particular, it applies a function to each element of alist, --- passing an accumulating parameter from right to left, and returning a --- final value of this accumulator together with the new list. +-- 'foldr'; it applies a function to each element of a list, passing +-- an accumulating parameter from right to left, and returning a final +-- value of this accumulator together with the new list. mapAccumR :: (acc -> x -> (acc, y)) -- Function of elt of input list -- and accumulator, returning new -- accumulator and elt of result list @@ -359,6 +441,8 @@ mapAccumR f s (x:xs) = (s'', y:ys) -- element into the list at the last position where it is still less -- than or equal to the next element. In particular, if the list -- is sorted before the call, the result will also be sorted. +-- It is a special case of 'insertBy', which allows the programmer to +-- supply their own comparison function. insert :: Ord a => a -> [a] -> [a] insert e ls = insertBy (compare) e ls @@ -372,7 +456,7 @@ insertBy cmp x ys@(y:ys') -- | The 'maximumBy' function takes a comparison function and a list -- and returns the greatest element of the list by the comparison function. --- It is an error on an empty list. +-- The list must be finite and non-empty. maximumBy :: (a -> a -> Ordering) -> [a] -> a maximumBy _ [] = error "List.maximumBy: empty list" maximumBy cmp xs = foldl1 max xs @@ -383,7 +467,7 @@ maximumBy cmp xs = foldl1 max xs -- | The 'minimumBy' function takes a comparison function and a list -- and returns the least element of the list by the comparison function. --- It is an error on an empty list. +-- The list must be finite and non-empty. minimumBy :: (a -> a -> Ordering) -> [a] -> a minimumBy _ [] = error "List.minimumBy: empty list" minimumBy cmp xs = foldl1 min xs @@ -393,14 +477,14 @@ minimumBy cmp xs = foldl1 min xs _ -> x -- | The 'genericLength' function is an overloaded version of 'length'. In --- particular, instead of returning an Int, it returns any type which is --- an instance of Num. It is, however, less efficient than 'length'. +-- particular, instead of returning an 'Int', it returns any type which is +-- an instance of 'Num'. It is, however, less efficient than 'length'. genericLength :: (Num i) => [b] -> i genericLength [] = 0 genericLength (_:l) = 1 + genericLength l -- | The 'genericTake' function is an overloaded version of 'take', which --- accepts any Integral value as the number of elements to take. +-- accepts any 'Integral' value as the number of elements to take. genericTake :: (Integral i) => i -> [a] -> [a] genericTake 0 _ = [] genericTake _ [] = [] @@ -408,7 +492,7 @@ genericTake n (x:xs) | n > 0 = x : genericTake (n-1) xs genericTake _ _ = error "List.genericTake: negative argument" -- | The 'genericDrop' function is an overloaded version of 'drop', which --- accepts any Integral value as the number of elements to drop. +-- accepts any 'Integral' value as the number of elements to drop. genericDrop :: (Integral i) => i -> [a] -> [a] genericDrop 0 xs = xs genericDrop _ [] = [] @@ -416,7 +500,7 @@ genericDrop n (_:xs) | n > 0 = genericDrop (n-1) xs genericDrop _ _ = error "List.genericDrop: negative argument" -- | The 'genericSplitAt' function is an overloaded version of 'splitAt', which --- accepts any Integral value as the position at which to split. +-- accepts any 'Integral' value as the position at which to split. genericSplitAt :: (Integral i) => i -> [b] -> ([b],[b]) genericSplitAt 0 xs = ([],xs) genericSplitAt _ [] = ([],[]) @@ -424,8 +508,8 @@ genericSplitAt n (x:xs) | n > 0 = (x:xs',xs'') where (xs',xs'') = genericSplitAt (n-1) xs genericSplitAt _ _ = error "List.genericSplitAt: negative argument" --- | The 'genericIndex' function is an overloaded version of 'index', which --- accepts any Integral value as the index to return. +-- | The 'genericIndex' function is an overloaded version of '!!', which +-- accepts any 'Integral' value as the index. genericIndex :: (Integral a) => [b] -> a -> b genericIndex (x:_) 0 = x genericIndex (_:xs) n @@ -433,95 +517,112 @@ genericIndex (_:xs) n | otherwise = error "List.genericIndex: negative argument." genericIndex _ _ = error "List.genericIndex: index too large." --- | The 'genericReplicate' function is an overloaded version of 'replicate', which --- accepts any Integral value as the number of repetitions to make. +-- | The 'genericReplicate' function is an overloaded version of 'replicate', +-- which accepts any 'Integral' value as the number of repetitions to make. genericReplicate :: (Integral i) => i -> a -> [a] genericReplicate n x = genericTake n (repeat x) --- | The 'zip4' function takes four lists and returns a list of quadruples, analogous to 'zip'. +-- | The 'zip4' function takes four lists and returns a list of +-- quadruples, analogous to 'zip'. zip4 :: [a] -> [b] -> [c] -> [d] -> [(a,b,c,d)] zip4 = zipWith4 (,,,) --- | The 'zip5' function takes five lists and returns a list of five-tuples, analogous to 'zip'. +-- | The 'zip5' function takes five lists and returns a list of +-- five-tuples, analogous to 'zip'. zip5 :: [a] -> [b] -> [c] -> [d] -> [e] -> [(a,b,c,d,e)] zip5 = zipWith5 (,,,,) --- | The 'zip6' function takes six lists and returns a list of six-tuples, analogous to 'zip'. +-- | The 'zip6' function takes six lists and returns a list of six-tuples, +-- analogous to 'zip'. zip6 :: [a] -> [b] -> [c] -> [d] -> [e] -> [f] -> [(a,b,c,d,e,f)] zip6 = zipWith6 (,,,,,) --- | The 'zip7' function takes seven lists and returns a list of seven-tuples, analogous to 'zip'. +-- | The 'zip7' function takes seven lists and returns a list of +-- seven-tuples, analogous to 'zip'. zip7 :: [a] -> [b] -> [c] -> [d] -> [e] -> [f] -> [g] -> [(a,b,c,d,e,f,g)] zip7 = zipWith7 (,,,,,,) --- | The 'zipWith4' function takes a function which combines four elements, as well as four lists and returns a list of their point-wise combination, analogous to 'zipWith'. +-- | The 'zipWith4' function takes a function which combines four +-- elements, as well as four lists and returns a list of their point-wise +-- combination, analogous to 'zipWith'. zipWith4 :: (a->b->c->d->e) -> [a]->[b]->[c]->[d]->[e] zipWith4 z (a:as) (b:bs) (c:cs) (d:ds) = z a b c d : zipWith4 z as bs cs ds zipWith4 _ _ _ _ _ = [] --- | The 'zipWith5' function takes a function which combines five elements, as well as five lists and returns a list of their point-wise combination, analogous to 'zipWith'. +-- | The 'zipWith5' function takes a function which combines five +-- elements, as well as five lists and returns a list of their point-wise +-- combination, analogous to 'zipWith'. zipWith5 :: (a->b->c->d->e->f) -> [a]->[b]->[c]->[d]->[e]->[f] zipWith5 z (a:as) (b:bs) (c:cs) (d:ds) (e:es) = z a b c d e : zipWith5 z as bs cs ds es zipWith5 _ _ _ _ _ _ = [] --- | The 'zipWith6' function takes a function which combines six elements, as well as six lists and returns a list of their point-wise combination, analogous to 'zipWith'. +-- | The 'zipWith6' function takes a function which combines six +-- elements, as well as six lists and returns a list of their point-wise +-- combination, analogous to 'zipWith'. zipWith6 :: (a->b->c->d->e->f->g) -> [a]->[b]->[c]->[d]->[e]->[f]->[g] zipWith6 z (a:as) (b:bs) (c:cs) (d:ds) (e:es) (f:fs) = z a b c d e f : zipWith6 z as bs cs ds es fs zipWith6 _ _ _ _ _ _ _ = [] --- | The 'zipWith7' function takes a function which combines seven elements, as well as seven lists and returns a list of their point-wise combination, analogous to 'zipWith'. +-- | The 'zipWith7' function takes a function which combines seven +-- elements, as well as seven lists and returns a list of their point-wise +-- combination, analogous to 'zipWith'. zipWith7 :: (a->b->c->d->e->f->g->h) -> [a]->[b]->[c]->[d]->[e]->[f]->[g]->[h] zipWith7 z (a:as) (b:bs) (c:cs) (d:ds) (e:es) (f:fs) (g:gs) = z a b c d e f g : zipWith7 z as bs cs ds es fs gs zipWith7 _ _ _ _ _ _ _ _ = [] --- | The 'unzip4' function takes a list of quadruples and returns four lists, analogous to 'unzip'. +-- | The 'unzip4' function takes a list of quadruples and returns four +-- lists, analogous to 'unzip'. unzip4 :: [(a,b,c,d)] -> ([a],[b],[c],[d]) unzip4 = foldr (\(a,b,c,d) ~(as,bs,cs,ds) -> (a:as,b:bs,c:cs,d:ds)) ([],[],[],[]) --- | The 'unzip5' function takes a list of five-tuples and returns five lists, analogous to 'unzip'. +-- | The 'unzip5' function takes a list of five-tuples and returns five +-- lists, analogous to 'unzip'. unzip5 :: [(a,b,c,d,e)] -> ([a],[b],[c],[d],[e]) unzip5 = foldr (\(a,b,c,d,e) ~(as,bs,cs,ds,es) -> (a:as,b:bs,c:cs,d:ds,e:es)) ([],[],[],[],[]) --- | The 'unzip6' function takes a list of six-tuples and returns six lists, analogous to 'unzip'. +-- | The 'unzip6' function takes a list of six-tuples and returns six +-- lists, analogous to 'unzip'. unzip6 :: [(a,b,c,d,e,f)] -> ([a],[b],[c],[d],[e],[f]) unzip6 = foldr (\(a,b,c,d,e,f) ~(as,bs,cs,ds,es,fs) -> (a:as,b:bs,c:cs,d:ds,e:es,f:fs)) ([],[],[],[],[],[]) --- | The 'unzip7' function takes a list of seven-tuples and returns seven lists, analogous to 'unzip'. +-- | The 'unzip7' function takes a list of seven-tuples and returns +-- seven lists, analogous to 'unzip'. unzip7 :: [(a,b,c,d,e,f,g)] -> ([a],[b],[c],[d],[e],[f],[g]) unzip7 = foldr (\(a,b,c,d,e,f,g) ~(as,bs,cs,ds,es,fs,gs) -> (a:as,b:bs,c:cs,d:ds,e:es,f:fs,g:gs)) ([],[],[],[],[],[],[]) --- | The 'deleteFirstsBy' function takes a predicate and two lists and returns the first --- list with the first occurance of each element of the second list removed. +-- | The 'deleteFirstsBy' function takes a predicate and two lists and +-- returns the first list with the first occurrence of each element of +-- the second list removed. deleteFirstsBy :: (a -> a -> Bool) -> [a] -> [a] -> [a] deleteFirstsBy eq = foldl (flip (deleteBy eq)) - --- group splits its list argument into a list of lists of equal, adjacent --- elements. e.g., --- group "Mississippi" == ["M","i","ss","i","ss","i","pp","i"] -- | The 'group' function takes a list and returns a list of lists such -- that the concatenation of the result is equal to the argument. Moreover, -- each sublist in the result contains only equal elements. For example, --- when applied to the string \"Mississippi\", the result is @[\"M\",\"i\",\"ss\",\"i\",\"ss\",\"i\",\"pp\",\"i\"]@. -group :: (Eq a) => [a] -> [[a]] +-- +-- > group "Mississippi" = ["M","i","ss","i","ss","i","pp","i"] +-- +-- It is a special case of 'groupBy', which allows the programmer to supply +-- their own equality test. +group :: Eq a => [a] -> [[a]] group = groupBy (==) -- | The 'groupBy' function is the non-overloaded version of 'group'. @@ -530,16 +631,20 @@ groupBy _ [] = [] groupBy eq (x:xs) = (x:ys) : groupBy eq zs where (ys,zs) = span (eq x) xs --- inits xs returns the list of initial segments of xs, shortest first. --- e.g., inits "abc" == ["","a","ab","abc"] --- | The 'inits' function returns all initial segements of the argument, short to long. +-- | The 'inits' function returns all initial segments of the argument, +-- shortest first. For example, +-- +-- > inits "abc" == ["","a","ab","abc"] +-- inits :: [a] -> [[a]] inits [] = [[]] inits (x:xs) = [[]] ++ map (x:) (inits xs) --- tails xs returns the list of all final segments of xs, longest first. --- e.g., tails "abc" == ["abc", "bc", "c",""] --- | The 'tails' function returns all final segements of the argument, long to short. +-- | The 'tails' function returns all final segments of the argument, +-- longest first. For example, +-- +-- > tails "abc" == ["abc", "bc", "c",""] +-- tails :: [a] -> [[a]] tails [] = [[]] tails xxs@(_:xs) = xxs : tails xs @@ -548,8 +653,11 @@ tails xxs@(_:xs) = xxs : tails xs ------------------------------------------------------------------------------ -- Quick Sort algorithm taken from HBC's QSort library. --- | The 'sort' function sorts a list with the overloaded 'compare' function. +-- | The 'sort' function implements a stable sorting algorithm. +-- It is a special case of 'sortBy', which allows the programmer to supply +-- their own comparison function. sort :: (Ord a) => [a] -> [a] + -- | The 'sortBy' function is the non-overloaded version of 'sort'. sortBy :: (a -> a -> Ordering) -> [a] -> [a] @@ -665,32 +773,33 @@ rqpart cmp x (y:ys) rle rgt r = #endif /* USE_REPORT_PRELUDE */ -{- -\begin{verbatim} - unfoldr f' (foldr f z xs) == (z,xs) - - if the following holds: - - f' (f x y) = Just (x,y) - f' z = Nothing -\end{verbatim} --} +-- | The 'unfoldr' function is a \`dual\' to 'foldr': while 'foldr' +-- reduces a list to a summary value, 'unfoldr' builds a list from +-- a seed value. The function takes the element and returns 'Nothing' +-- if it is done producing the list or returns 'Just' @(a,b)@, in which +-- case, @a@ is a prepended to the list and @b@ is used as the next +-- element in a recursive call. For example, +-- +-- > iterate f == unfoldr (\x -> Just (x, f x)) +-- +-- In some cases, 'unfoldr' can undo a 'foldr' operation: +-- +-- > unfoldr f' (foldr f z xs) == xs +-- +-- if the following holds: +-- +-- > f' (f x y) = Just (x,y) +-- > f' z = Nothing --- | The 'unfoldr' function produces a list from an element. The function --- takes the element and returns 'Nothing' if it is done producing the list --- or returns @Just (a,b)@, in which case, @a@ is a prepended to the list --- and @b@ is used as the next element in a recursive call. unfoldr :: (b -> Maybe (a, b)) -> b -> [a] unfoldr f b = case f b of Just (a,new_b) -> a : unfoldr f new_b Nothing -> [] - -- ----------------------------------------------------------------------------- --- strict version of foldl --- | A strict version of 'foldl' +-- | A strict version of 'foldl'. 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 @@ -699,24 +808,22 @@ foldl' f a (x:xs) = let a' = f a x in a' `seq` foldl' f a' xs -- ----------------------------------------------------------------------------- -- List sum and product --- sum and product compute the sum or product of a finite list of numbers. {-# SPECIALISE sum :: [Int] -> Int #-} {-# SPECIALISE sum :: [Integer] -> Integer #-} {-# SPECIALISE product :: [Int] -> Int #-} {-# SPECIALISE product :: [Integer] -> Integer #-} -sum, product :: (Num a) => [a] -> a +-- | The 'sum' function computes the sum of a finite list of numbers. +sum :: (Num a) => [a] -> a +-- | The 'product' function computes the product of a finite list of numbers. +product :: (Num a) => [a] -> a #ifdef USE_REPORT_PRELUDE --- | The 'sum' function sums the elements of a list. sum = foldl (+) 0 --- | The 'product' function computes the product of the elements of a list. product = foldl (*) 1 #else --- | The 'sum' function sums the elements of a list. sum l = sum' l 0 where sum' [] a = a sum' (x:xs) a = sum' xs (a+x) --- | The 'product' function computes the product of the elements of a list. product l = prod l 1 where prod [] a = a @@ -726,13 +833,8 @@ product l = prod l 1 -- ----------------------------------------------------------------------------- -- Functions on strings --- lines breaks a string up into a list of strings at newline characters. --- The resulting strings do not contain newlines. Similary, words --- breaks a string up into a list of words, which were delimited by --- white space. unlines and unwords are the inverse operations. --- unlines joins lines with terminating newlines, and unwords joins --- words with separating spaces. - +-- | 'lines' breaks a string up into a list of strings at newline +-- characters. The resulting strings do not contain newlines. lines :: String -> [String] lines "" = [] lines s = let (l, s') = break (== '\n') s @@ -740,6 +842,8 @@ lines s = let (l, s') = break (== '\n') s [] -> [] (_:s'') -> lines s'' +-- | 'unlines' is an inverse operation to 'lines'. +-- It joins lines, after appending a terminating newline to each. unlines :: [String] -> String #ifdef USE_REPORT_PRELUDE unlines = concatMap (++ "\n") @@ -750,6 +854,8 @@ unlines [] = [] unlines (l:ls) = l ++ '\n' : unlines ls #endif +-- | 'words' breaks a string up into a list of words, which were delimited +-- by white space. words :: String -> [String] words s = case dropWhile {-partain:Char.-}isSpace s of "" -> [] @@ -757,6 +863,8 @@ words s = case dropWhile {-partain:Char.-}isSpace s of where (w, s'') = break {-partain:Char.-}isSpace s' +-- | 'unwords' is an inverse operation to 'words'. +-- It joins words with separating spaces. unwords :: [String] -> String #ifdef USE_REPORT_PRELUDE unwords [] = "" diff --git a/GHC/Base.lhs b/GHC/Base.lhs index 5f47ebb..f957a6d 100644 --- a/GHC/Base.lhs +++ b/GHC/Base.lhs @@ -279,6 +279,12 @@ The rest of the prelude list functions are in GHC.List. ---------------------------------------------- \begin{code} +-- | 'foldr', applied to a binary operator, a starting value (typically +-- the right-identity of the operator), and a list, reduces the list +-- using the binary operator, from right to left: +-- +-- > foldr f z [x1, x2, ..., xn] == x1 `f` (x2 `f` ... (xn `f` z)...) + foldr :: (a -> b -> b) -> b -> [a] -> b -- foldr _ z [] = z -- foldr f z (x:xs) = f x (foldr f z xs) @@ -344,6 +350,12 @@ augment g xs = g (:) xs ---------------------------------------------- \begin{code} +-- | 'map' @f xs@ is the list obtained by applying @f@ to each element +-- of @xs@, i.e., +-- +-- > map f [x1, x2, ..., xn] == [f x1, f x2, ..., f xn] +-- > map f [x1, x2, ...] == [f x1, f x2, ...] + map :: (a -> b) -> [a] -> [b] map _ [] = [] map f (x:xs) = f x : map f xs @@ -383,6 +395,13 @@ mapFB c f x ys = c (f x) ys -- append ---------------------------------------------- \begin{code} +-- | Append two lists, i.e., +-- +-- > [x1, ..., xm] ++ [y1, ..., yn] == [x1, ..., xm, y1, ..., yn] +-- > [x1, ..., xm] ++ [y1, ...] == [x1, ..., xm, y1, ...] +-- +-- If the first list is not finite, the result is the first list. + (++) :: [a] -> [a] -> [a] (++) [] ys = ys (++) (x:xs) ys = x : xs ++ ys diff --git a/GHC/List.lhs b/GHC/List.lhs index 99c1b5b..d431070 100644 --- a/GHC/List.lhs +++ b/GHC/List.lhs @@ -54,11 +54,7 @@ infix 4 `elem`, `notElem` %********************************************************* \begin{code} --- head and tail extract the first element and remaining elements, --- respectively, of a list, which must be non-empty. last and init --- are the dual functions working from the end of a finite list, --- rather than the beginning. - +-- | Extract the first element of a list, which must be non-empty. head :: [a] -> a head (x:_) = x head [] = badHead @@ -74,10 +70,12 @@ badHead = errorEmptyList "head" head (augment g xs) = g (\x _ -> x) (head xs) #-} +-- | Extract the elements after the head of a list, which must be non-empty. tail :: [a] -> [a] tail (_:xs) = xs tail [] = errorEmptyList "tail" +-- | Extract the last element of a list, which must be finite and non-empty. last :: [a] -> a #ifdef USE_REPORT_PRELUDE last [x] = x @@ -91,6 +89,8 @@ last (x:xs) = last' x xs last' _ (y:ys) = last' y ys #endif +-- | Return all the elements of a list except the last one. +-- The list must be finite and non-empty. init :: [a] -> [a] #ifdef USE_REPORT_PRELUDE init [x] = [] @@ -104,13 +104,14 @@ init (x:xs) = init' x xs init' y (z:zs) = y : init' z zs #endif +-- | Test whether a list is empty. null :: [a] -> Bool null [] = True null (_:_) = False --- length returns the length of a finite list as an Int; it is an instance --- of the more general genericLength, the result type of which may be --- any kind of number. +-- | '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 @@ -118,9 +119,11 @@ length l = len l 0# len [] a# = I# a# len (_:xs) a# = len xs (a# +# 1#) --- filter, applied to a predicate and a list, returns the list of those --- elements that satisfy the predicate; i.e., --- filter p xs = [ x | x <- xs, p x] +-- | 'filter', applied to a predicate and a list, returns the list of +-- those elements that satisfy the predicate; i.e., +-- +-- > filter p xs = [ x | x <- xs, p x] + filter :: (a -> Bool) -> [a] -> [a] filter _pred [] = [] filter pred (x:xs) @@ -147,17 +150,13 @@ filterFB c p x r | p x = x `c` r -- gave rise to a live bug report. SLPJ. --- foldl, applied to a binary operator, a starting value (typically the --- left-identity of the operator), and a list, reduces the list using --- the binary operator, from left to right: --- foldl f z [x1, x2, ..., xn] == (...((z `f` x1) `f` x2) `f`...) `f` xn --- foldl1 is a variant that has no starting value argument, and thus must --- be applied to non-empty lists. scanl is similar to foldl, but returns --- a list of successive reduced values from the left: --- scanl f z [x1, x2, ...] == [z, z `f` x1, (z `f` x1) `f` x2, ...] --- Note that last (scanl f z xs) == foldl f z xs. --- scanl1 is similar, again without the starting element: --- scanl1 f [x1, x2, ...] == [x1, x1 `f` x2, ...] +-- | 'foldl', applied to a binary operator, a starting value (typically +-- the left-identity of the operator), and a list, reduces the list +-- using the binary operator, from left to right: +-- +-- > foldl f z [x1, x2, ..., xn] == (...((z `f` x1) `f` x2) `f`...) `f` xn +-- +-- The list must be finite. -- We write foldl as a non-recursive thing, so that it -- can be inlined, and then (often) strictness-analysed, @@ -169,15 +168,31 @@ foldl f z xs = lgo z 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: +-- +-- > scanl f z [x1, x2, ...] == [z, z `f` x1, (z `f` x1) `f` x2, ...] +-- +-- Note that +-- +-- > last (scanl f z xs) == foldl f z xs. + scanl :: (a -> b -> a) -> a -> [b] -> [a] scanl f q ls = q : (case ls of [] -> [] x:xs -> scanl f (f q x) xs) +-- | 'scanl1' is a variant of 'scanl' that has no starting value argument: +-- +-- > scanl1 f [x1, x2, ...] == [x1, x1 `f` x2, ...] + scanl1 :: (a -> a -> a) -> [a] -> [a] scanl1 f (x:xs) = scanl f x xs scanl1 _ [] = [] @@ -185,24 +200,37 @@ scanl1 _ [] = [] -- foldr, foldr1, scanr, and scanr1 are the right-to-left duals of the -- above functions. +-- | 'foldr1' is a variant of 'foldr' that has no starting value argument, +-- and thus must be applied to non-empty lists. + foldr1 :: (a -> a -> a) -> [a] -> a foldr1 _ [x] = x foldr1 f (x:xs) = f x (foldr1 f xs) foldr1 _ [] = errorEmptyList "foldr1" +-- | 'scanr' is the right-to-left dual of 'scanl'. +-- Note that +-- +-- > head (scanr f z xs) == foldr f z xs. + scanr :: (a -> b -> b) -> b -> [a] -> [b] scanr _ q0 [] = [q0] scanr f q0 (x:xs) = f x q : qs where qs@(q:_) = scanr f q0 xs +-- | 'scanr1' is a variant of 'scanr' that has no starting value argument. + scanr1 :: (a -> a -> a) -> [a] -> [a] scanr1 f [] = [] scanr1 f [x] = [x] scanr1 f (x:xs) = f x q : qs where qs@(q:_) = scanr1 f xs --- iterate f x returns an infinite list of repeated applications of f to x: --- iterate f x == [x, f x, f (f x), ...] +-- | 'iterate' @f x@ returns an infinite list of repeated applications +-- of @f@ to @x@: +-- +-- > iterate f x == [x, f x, f (f x), ...] + iterate :: (a -> a) -> a -> [a] iterate f x = x : iterate f (f x) @@ -215,7 +243,7 @@ iterateFB c f x = x `c` iterateFB c f (f x) #-} --- repeat x is an infinite list, with x the value of every element. +-- | 'repeat' @x@ is an infinite list, with @x@ the value of every element. repeat :: a -> [a] {-# INLINE [0] repeat #-} -- The pragma just gives the rules more chance to fire @@ -230,11 +258,14 @@ repeatFB c x = xs where xs = x `c` xs "repeatFB" [1] repeatFB (:) = repeat #-} --- replicate n x is a list of length n with x the value of every element +-- | 'replicate' @n x@ is a list of length @n@ with @x@ the value of +-- every element. +-- It is an instance of the more general 'Data.List.genericReplicate', +-- in which @n@ may be of any integral type. replicate :: Int -> a -> [a] replicate n x = take n (repeat x) --- cycle ties a finite list into a circular one, or equivalently, +-- | 'cycle' ties a finite list into a circular one, or equivalently, -- the infinite repetition of the original list. It is the identity -- on infinite lists. @@ -242,10 +273,8 @@ cycle :: [a] -> [a] cycle [] = error "Prelude.cycle: empty list" 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. dropWhile p xs --- returns the remaining suffix. Span p xs is equivalent to --- (takeWhile p xs, dropWhile p xs), while break p uses the negation of p. +-- | 'takeWhile', applied to a predicate @p@ and a list @xs@, returns the +-- longest prefix (possibly empty) of @xs@ of elements that satisfy @p@. takeWhile :: (a -> Bool) -> [a] -> [a] takeWhile _ [] = [] @@ -253,32 +282,43 @@ takeWhile p (x:xs) | p x = x : takeWhile p xs | otherwise = [] +-- | 'dropWhile' @p xs@ returns the suffix remaining after 'takeWhile' @p xs@. + dropWhile :: (a -> Bool) -> [a] -> [a] dropWhile _ [] = [] dropWhile p xs@(x:xs') | p x = dropWhile p xs' | otherwise = xs --- take n, applied to a list xs, returns the prefix of xs of length n, --- or xs itself if n > length xs. drop n xs returns the suffix of xs --- after the first n elements, or [] if n > length xs. splitAt n xs --- is equivalent to (take n xs, drop n xs). -#ifdef USE_REPORT_PRELUDE +-- | 'take' @n@, applied to a list @xs@, returns the prefix of @xs@ +-- of length @n@, or @xs@ itself if @n > 'length' xs@. +-- 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@. +-- 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', +-- in which @n@ may be of any integral type. +splitAt :: Int -> [a] -> ([a],[a]) + +#ifdef USE_REPORT_PRELUDE take n _ | n <= 0 = [] take _ [] = [] take n (x:xs) = x : take (n-1) xs -drop :: Int -> [a] -> [a] drop n xs | n <= 0 = xs drop _ [] = [] drop n (_:xs) = drop (n-1) xs -splitAt :: Int -> [a] -> ([a],[a]) -splitAt n xs = (take n xs, drop n xs) +splitAt n xs = (take n xs, drop n xs) #else /* hack away */ -take :: Int -> [b] -> [b] take (I# n#) xs = takeUInt n# xs -- The general code for take, below, checks n <= maxInt @@ -309,7 +349,6 @@ take_unsafe_UInt_append m ls rs = [] -> rs (x:xs) -> x : take_unsafe_UInt_append (m -# 1#) xs rs -drop :: Int -> [b] -> [b] drop (I# n#) ls | n# <# 0# = [] | otherwise = drop# n# ls @@ -319,7 +358,6 @@ drop (I# n#) ls drop# _ xs@[] = xs drop# m# (_:xs) = drop# (m# -# 1#) xs -splitAt :: Int -> [b] -> ([b], [b]) splitAt (I# n#) ls | n# <# 0# = ([], ls) | otherwise = splitAt# n# ls @@ -333,12 +371,17 @@ splitAt (I# n#) ls #endif /* USE_REPORT_PRELUDE */ -span, break :: (a -> Bool) -> [a] -> ([a],[a]) +-- | 'span' @p xs@ is equivalent to @('takeWhile' p xs, 'dropWhile' p xs)@ + +span :: (a -> Bool) -> [a] -> ([a],[a]) span _ xs@[] = (xs, xs) span p xs@(x:xs') | p x = let (ys,zs) = span p xs' in (x:ys,zs) | otherwise = ([],xs) +-- | 'break' @p@ is equivalent to @'span' ('not' . p)@. + +break :: (a -> Bool) -> [a] -> ([a],[a]) #ifdef USE_REPORT_PRELUDE break p = span (not . p) #else @@ -349,7 +392,8 @@ break p xs@(x:xs') | otherwise = let (ys,zs) = break p xs' in (x:ys,zs) #endif --- reverse xs returns the elements of xs in reverse order. xs must be finite. +-- | 'reverse' @xs@ returns the elements of @xs@ in reverse order. +-- @xs@ must be finite. reverse :: [a] -> [a] #ifdef USE_REPORT_PRELUDE reverse = foldl (flip (:)) [] @@ -360,11 +404,15 @@ reverse l = rev l [] rev (x:xs) a = rev xs (x:a) #endif --- and returns the conjunction of a Boolean list. For the result to be --- True, the list must be finite; False, however, results from a False --- value at a finite index of a finite or infinite list. or is the --- disjunctive dual of and. -and, or :: [Bool] -> Bool +-- | 'and' returns the conjunction of a Boolean list. For the result to be +-- 'True', the list must be finite; 'False', however, results from a 'False' +-- value at a finite index of a finite or infinite list. +and :: [Bool] -> Bool + +-- | 'or' returns the disjunction of a Boolean list. For the result to be +-- 'False', the list must be finite; 'True', however, results from a 'True' +-- value at a finite index of a finite or infinite list. +or :: [Bool] -> Bool #ifdef USE_REPORT_PRELUDE and = foldr (&&) True or = foldr (||) False @@ -382,9 +430,13 @@ or (x:xs) = x || or xs #-} #endif --- Applied to a predicate and a list, any determines if any element --- of the list satisfies the predicate. Similarly, for all. -any, all :: (a -> Bool) -> [a] -> Bool +-- | Applied to a predicate and a list, 'any' determines if any element +-- of the list satisfies the predicate. +any :: (a -> Bool) -> [a] -> Bool + +-- | Applied to a predicate and a list, 'all' determines if all elements +-- of the list satisfy the predicate. +all :: (a -> Bool) -> [a] -> Bool #ifdef USE_REPORT_PRELUDE any p = or . map p all p = and . map p @@ -402,9 +454,12 @@ all p (x:xs) = p x && all p xs #-} #endif --- elem is the list membership predicate, usually written in infix form, --- e.g., x `elem` xs. notElem is the negation. -elem, notElem :: (Eq a) => a -> [a] -> Bool +-- | 'elem' is the list membership predicate, usually written in infix form, +-- e.g., @x `elem` xs@. +elem :: (Eq a) => a -> [a] -> Bool + +-- | 'notElem' is the negation of 'elem'. +notElem :: (Eq a) => a -> [a] -> Bool #ifdef USE_REPORT_PRELUDE elem x = any (== x) notElem x = all (/= x) @@ -416,28 +471,37 @@ notElem _ [] = True notElem x (y:ys)= x /= y && notElem x ys #endif --- lookup key assocs looks up a key in an association list. +-- | 'lookup' @key assocs@ looks up a key in an association list. lookup :: (Eq a) => a -> [(a,b)] -> Maybe b lookup _key [] = Nothing lookup key ((x,y):xys) | key == x = Just y | otherwise = lookup key xys - --- maximum and minimum return the maximum or minimum value from a list, --- which must be non-empty, finite, and of an ordered type. {-# SPECIALISE maximum :: [Int] -> Int #-} {-# SPECIALISE minimum :: [Int] -> Int #-} -maximum, minimum :: (Ord a) => [a] -> a + +-- | '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) [] +-- | Concatenate a list of lists. concat :: [[a]] -> [a] concat = foldr (++) [] @@ -450,7 +514,9 @@ concat = foldr (++) [] \begin{code} --- List index (subscript) operator, 0-origin +-- | List index (subscript) operator, starting from 0. +-- It is an instance of the more general 'Data.List.genericIndex', +-- which takes an index of any integral type. (!!) :: [a] -> Int -> a #ifdef USE_REPORT_PRELUDE xs !! n | n < 0 = error "Prelude.!!: negative index" @@ -512,13 +578,13 @@ E.g. main = print (null (zip nonobviousNil (build undefined))) I'm going to leave it though. -zip takes two lists and returns a list of corresponding pairs. If one -input list is short, excess elements of the longer list are discarded. -zip3 takes three lists and returns a list of triples. Zips for larger -tuples are in the List module. +Zips for larger tuples are in the List module. \begin{code} ---------------------------------------------- +-- | 'zip' takes two lists and returns a list of corresponding pairs. +-- If one input list is short, excess elements of the longer list are +-- discarded. zip :: [a] -> [b] -> [(a,b)] zip (a:as) (b:bs) = (a,b) : zip as bs zip _ _ = [] @@ -534,6 +600,8 @@ zipFB c x y r = (x,y) `c` r \begin{code} ---------------------------------------------- +-- | 'zip3' takes three lists and returns a list of triples, analogous to +-- 'zip'. zip3 :: [a] -> [b] -> [c] -> [(a,b,c)] -- Specification -- zip3 = zipWith3 (,,) @@ -544,12 +612,13 @@ zip3 _ _ _ = [] -- The zipWith family generalises the zip family by zipping with the -- function given as the first argument, instead of a tupling function. --- For example, zipWith (+) is applied to two lists to produce the list --- of corresponding sums. - \begin{code} ---------------------------------------------- +-- | 'zipWith' generalises 'zip' by zipping with the function given +-- as the first argument, instead of a tupling function. +-- For example, @'zipWith' (+)@ is applied to two lists to produce the +-- list of corresponding sums. zipWith :: (a->b->c) -> [a]->[b]->[c] zipWith f (a:as) (b:bs) = f a b : zipWith f as bs zipWith _ _ _ = [] @@ -564,16 +633,22 @@ zipWithFB c f x y r = (x `f` y) `c` r \end{code} \begin{code} +-- | The 'zipWith3' function takes a function which combines three +-- elements, as well as three lists and returns a list of their point-wise +-- combination, analogous to 'zipWith'. zipWith3 :: (a->b->c->d) -> [a]->[b]->[c]->[d] zipWith3 z (a:as) (b:bs) (c:cs) = z a b c : zipWith3 z as bs cs zipWith3 _ _ _ _ = [] --- unzip transforms a list of pairs into a pair of lists. +-- | 'unzip' transforms a list of pairs into a list of first components +-- and a list of second components. unzip :: [(a,b)] -> ([a],[b]) {-# INLINE unzip #-} unzip = foldr (\(a,b) ~(as,bs) -> (a:as,b:bs)) ([],[]) +-- | The 'unzip3' function takes a list of triples and returns three +-- lists, analogous to 'unzip'. unzip3 :: [(a,b,c)] -> ([a],[b],[c]) {-# INLINE unzip3 #-} unzip3 = foldr (\(a,b,c) ~(as,bs,cs) -> (a:as,b:bs,c:cs)) diff --git a/Prelude.hs b/Prelude.hs index 7ad6355..08fe811 100644 --- a/Prelude.hs +++ b/Prelude.hs @@ -17,13 +17,25 @@ module Prelude ( - -- * Basic data types + -- * Standard types, classes and related functions + + -- ** Basic data types Bool(False, True), + (&&), (||), not, otherwise, + Maybe(Nothing, Just), + maybe, + Either(Left, Right), + either, + Ordering(LT, EQ, GT), - Char, String, Int, Integer, Float, Double, IO, - Rational, + Char, String, + IO, + + -- *** Tuples + fst, snd, curry, uncurry, + #if defined(__NHC__) []((:), []), -- Not legal Haskell 98; -- ... available through built-in syntax @@ -35,14 +47,20 @@ module Prelude ( (:), -- Not legal Haskell 98 #endif - -- * Basic type classes + -- ** Basic type classes Eq((==), (/=)), Ord(compare, (<), (<=), (>=), (>), max, min), Enum(succ, pred, toEnum, fromEnum, enumFrom, enumFromThen, enumFromTo, enumFromThenTo), Bounded(minBound, maxBound), - -- * Numeric type classes + -- ** Numbers + + -- *** Numeric types + Int, Integer, Float, Double, + Rational, + + -- *** Numeric type classes Num((+), (-), (*), negate, abs, signum, fromInteger), Real(toRational), Integral(quot, rem, div, mod, quotRem, divMod, toInteger), @@ -54,19 +72,44 @@ module Prelude ( encodeFloat, exponent, significand, scaleFloat, isNaN, isInfinite, isDenormalized, isIEEE, isNegativeZero, atan2), + -- *** Numeric functions + subtract, even, odd, gcd, lcm, (^), (^^), + fromIntegral, realToFrac, + + -- ** Monads and functors + Monad((>>=), (>>), return, fail), + Functor(fmap), + mapM, mapM_, sequence, sequence_, (=<<), + + -- ** Miscellaneous functions + id, const, (.), flip, ($), until, + asTypeOf, error, undefined, + seq, ($!), + -- * List operations - map, (++), filter, concat, + map, (++), filter, head, last, tail, init, null, length, (!!), - foldl, foldl1, scanl, scanl1, foldr, foldr1, scanr, scanr1, + reverse, + -- ** Reducing lists (folds) + foldl, foldl1, foldr, foldr1, + -- *** Special folds + and, or, any, all, + sum, product, + concat, concatMap, + maximum, minimum, + -- ** Building lists + -- *** Scans + scanl, scanl1, scanr, scanr1, + -- *** Infinite lists iterate, repeat, replicate, cycle, + -- ** Sublists take, drop, splitAt, takeWhile, dropWhile, span, break, - reverse, and, or, - any, all, elem, notElem, lookup, - maximum, minimum, concatMap, + -- ** Searching lists + elem, notElem, lookup, + -- ** Zipping and unzipping lists zip, zip3, zipWith, zipWith3, unzip, unzip3, - + -- ** Functions on strings lines, words, unlines, unwords, - sum, product, -- * Converting to and from @String@ ReadS, ShowS, @@ -92,22 +135,7 @@ module Prelude ( FilePath, readFile, writeFile, appendFile, readIO, readLn, -- ** Exception handling in the I\/O monad - IOError, ioError, userError, catch, - - -- * Monads - Monad((>>=), (>>), return, fail), - Functor(fmap), - mapM, mapM_, sequence, sequence_, (=<<), - - -- * Miscellaneous functions - maybe, either, - (&&), (||), not, otherwise, - subtract, even, odd, gcd, lcm, (^), (^^), - fromIntegral, realToFrac, - fst, snd, curry, uncurry, - id, const, (.), flip, ($), until, - asTypeOf, error, undefined, - seq, ($!) + IOError, ioError, userError, catch ) where -- 1.7.10.4