7  List Utilities

module List (      elemIndex, elemIndices,     find, findIndex, findIndices,     nub, nubBy, delete, deleteBy, (\\), deleteFirstsBy,     union, unionBy, intersect, intersectBy,     intersperse, transpose, partition, group, groupBy,     inits, tails, isPrefixOf, isSuffixOf,     mapAccumL, mapAccumR,     sort, sortBy, insert, insertBy, maximumBy, minimumBy,     genericLength, genericTake, genericDrop,     genericSplitAt, genericIndex, genericReplicate,     zip4, zip5, zip6, zip7,     zipWith4, zipWith5, zipWith6, zipWith7,     unzip4, unzip5, unzip6, unzip7, unfoldr,     -- ...and what the Prelude exports     []((:), []),     map, (++), concat, filter,     head, last, tail, init, null, length, (!!),     foldl, foldl1, scanl, scanl1, foldr, foldr1, scanr, scanr1,     iterate, repeat, replicate, cycle,     take, drop, splitAt, takeWhile, dropWhile, span, break,     lines, words, unlines, unwords, reverse, and, or,     any, all, elem, notElem, lookup,     sum, product, maximum, minimum, concatMap,      zip, zip3, zipWith, zipWith3, unzip, unzip3     ) where infix 5 \\ 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]) unfoldr     :: (b -> Maybe (a,b)) -> b -> [a] 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] zip4                :: [a] -> [b] -> [c] -> [d] -> [(a,b,c,d)] zip5                :: [a] -> [b] -> [c] -> [d] -> [e] -> [(a,b,c,d,e)] zip6                :: [a] -> [b] -> [c] -> [d] -> [e] -> [f]                            -> [(a,b,c,d,e,f)] zip7                :: [a] -> [b] -> [c] -> [d] -> [e] -> [f] -> [g]                           -> [(a,b,c,d,e,f,g)] zipWith4            :: (a->b->c->d->e) -> [a]->[b]->[c]->[d]->[e] zipWith5            :: (a->b->c->d->e->f) ->                         [a]->[b]->[c]->[d]->[e]->[f] zipWith6            :: (a->b->c->d->e->f->g) ->                        [a]->[b]->[c]->[d]->[e]->[f]->[g] zipWith7            :: (a->b->c->d->e->f->g->h) ->                        [a]->[b]->[c]->[d]->[e]->[f]->[g]->[h] unzip4              :: [(a,b,c,d)] -> ([a],[b],[c],[d]) unzip5              :: [(a,b,c,d,e)] -> ([a],[b],[c],[d],[e]) unzip6              :: [(a,b,c,d,e,f)] -> ([a],[b],[c],[d],[e],[f]) unzip7              :: [(a,b,c,d,e,f,g)] -> ([a],[b],[c],[d],[e],[f],[g])

This library defines some lesser-used operations over lists.

7.1  Indexing lists

Function elemIndex val list returns the index of the first occurrence, if any, of val in list as Just index. Nothing is returned if not (val `elem` list).

Function elemIndices val list returns an in-order list of indices, giving the occurrences of val in list.

Function find returns the first element of a list that satisfies a predicate, or Nothing, if there is no such element. findIndex returns the corresponding index. findIndices returns a list of all such indices.

7.2  "Set" operations

There are a number of "set" operations defined over the List type. nub (meaning "essence") removes duplicates elements from a list. delete, (\\), union and intersect preserve the invariant that lists don't contain duplicates, provided that their first argument contains no duplicates.

• delete x removes the first occurrence of x from its list argument, e.g.,
  
    delete 'a' "banana" == "bnana"
  
  

• (\\) 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. union is list union, e.g.,
  
    "dog" `union` "cow" == "dogcw"
  
  

• intersect is list intersection, e.g.,
  
    intersect [1,2,3,4] `intersect` [2,4,6,8] == [2,4]
  
  

7.3  List transformations

• intersperse sep inserts sep between the elements of its list argument, e.g.,
  
    intersperse ',' "abcde" == "a,b,c,d,e"
  
  

• transpose transposes the rows and columns of its argument, e.g.,
  
    transpose [[1,2,3],[4,5,6]] == [[1,4],[2,5],[3,6]]
  
  

• 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)
  
  

• sort/sortBy implement a stable sorting algorithm, here specified in terms of the insertBy function, which inserts objects into a list according to the specified ordering relation.

• group splits its list argument into a list of lists of equal, adjacent elements. For exmaple
  
    group "Mississippi" == ["M","i","ss","i","ss","i","pp","i"]
  
  

• inits returns the list of initial segments of its argument list, shortest first.
  
    inits "abc" == ["","a","ab","abc"]
  
  

• tails returns the list of all final segments of its argument list, longest first.
  
    tails "abc" == ["abc", "bc", "c",""]
  

  
  

• mapAccumL f s l applies f to an accumulating "state" parameter s and to each element of l in turn.

• mapAccumR is similar to mapAccumL except that the list is processed from right-to-left rather than left-to-right.

7.4  unfoldr

The unfoldr function undoes a foldr operation. Note that, in general, only invertible functions can be unfolded.

  unfoldr f' (foldr f z xs) == xs

if the following holds:

  f' (f x y) = Just (x,y)
  f' z       = Nothing

7.5  Predicates

isPrefixOf and isSuffixOf check whether the first argument is a prefix (resp. suffix) of the second argument.

7.6  The "By" operations

By convention, overloaded functions have a non-overloaded counterpart whose name is suffixed with "By". For example, the function nub could be defined as follows:

  nub                     :: (Eq a) => [a] -> [a]
  nub []                  =  []
  nub (x:xs)              =  x : nub (filter (\y -> x /= y) xs)

However, the equality method may not be appropriate in all situations. The function:

  nubBy                   :: (a -> a -> Bool) -> [a] -> [a]
  nubBy eq []             =  []
  nubBy eq (x:xs)         =  x : nubBy eq (filter (\y -> not (eq x y)) xs)

allows the programmer to supply their own equality test. When the "By" function replaces an Eq context by a binary predicate, the predicate is assumed to define an equivalence; when the "By" function replaces an Ord context by a binary predicate, the predicate is assumed to define a total ordering.

The "By" variants are as follows: nubBy, deleteBy, unionBy, intersectBy, groupBy, sortBy, insertBy, maximumBy, minimumBy. The library does not provide elemBy, because any (eq x) does the same job as elemBy eq x would. A handful of overloaded functions (elemIndex, elemIndices, isPrefixOf, isSuffixOf) were not considered important enough to have "By" variants.

7.7  The "generic" operations

The prefix "generic" indicates an overloaded function that is a generalised version of a Prelude function. For example,

  genericLength       :: Integral a => [b] -> a

is a generalised verion of length.

The "generic" operations are as follows: genericLength, genericTake, genericDrop, genericSplitAt, genericIndex, genericReplicate.

7.8  Library List