Описание библиотеки Haskell 98: Утилиты работы со списками Описание Haskell 98
наверх | назад | вперед | содержание | предметный указатель функций

17  Утилиты работы со списками


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,

    -- ...и то, что экспортирует Prelude
    -- []((:), []), -- Это встроенный синтаксис
    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])

В этой библиотеке определены некоторые редко используемые операции над списками.

17.1  Индексирование списков

17.2  Операции над "множествами"

Имеется ряд операций над "множествами", определенные над типом List. nub (означает "сущность") удаляет дублирующие элементы из списка. delete, (\\), union и intersect (и их By-варианты) сохраняют инвариант: их результат не содержит дубликаты, при условии, что их первый аргумент не содержит дубликаты.

17.3  Преобразования списков

17.4  unfoldr

Функция unfoldr является "двойственной" к foldr: тогда как foldr приводит список к суммарному значению, unfoldr строит список из случайного значения. Например:

  iterate f == unfoldr (\x -> Just (x, f x))

В некоторых случаях unfoldr может аннулировать операцию foldr:

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

если выполняется следующее:

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

17.5  Предикаты

isPrefixOf и isSuffixOf проверяют, является ли первый аргумент соответственно приставкой или суффиксом второго аргумента.

17.6  "By"-операции

В соответствии с соглашением, перегруженные функции имеют неперегруженные копии, чьи имена имеют суффикс "By". Например, функция nub могла быть определена следующим образом:

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

Тем не менее, метод сравнения на равенство не может подходить под все ситуации. Функция:

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

позволяет программисту добавлять свою собственную проверку равенства. Когда "By"-функция заменяет контекст Eq бинарным предикатом, предполагается, что предикат определяет эквивалентность; когда "By"-функция заменяет контекст Ord бинарным предикатом, предполагается, что предикат определяет нестрогий порядок.

"By"-вариантами являются следующие: nubBy, deleteBy, deleteFirstsBy (By-вариант \\), unionBy, intersectBy, groupBy, sortBy, insertBy, maximumBy, minimumBy.

Библиотека не обеспечивает elemBy, потому что any (eq x) выполняет ту же работу, что выполняла бы elemBy eq x. Небольшое количество перегруженных функций (elemIndex, elemIndices, isPrefixOf, isSuffixOf) посчитали недостаточно важными для того, чтобы они имели "By"-варианты.

17.7  "generic"-операции

Приставка "generic" указывает на перегруженную функцию, которая является обобщенной версией функции Prelude . Например,

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

является обобщенной версией length.

"generic"-операциями являются следующие: genericLength, genericTake, genericDrop, genericSplitAt, genericIndex (обобщенная версия !!), genericReplicate.

17.8  Дополнительные "zip"-операции

Prelude обеспечивает zip, zip3, unzip, unzip3, zipWith и zipWith3. Библиотека List обеспечивает те же три операции для 4, 5, 6 и 7 аргументов.

17.9  Библиотека List


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,

    -- ...и то, что экспортирует Prelude
    -- []((:), []), -- Это встроенный синтаксис
    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

import Maybe( listToMaybe )

infix 5 \\

elemIndex               :: Eq a => a -> [a] -> Maybe Int
elemIndex x             =  findIndex (x ==)
        
elemIndices             :: Eq a => a -> [a] -> [Int]
elemIndices x           =  findIndices (x ==)
                        
find                    :: (a -> Bool) -> [a] -> Maybe a
find p                  =  listToMaybe . filter p

findIndex               :: (a -> Bool) -> [a] -> Maybe Int
findIndex p             =  listToMaybe . findIndices p

findIndices             :: (a -> Bool) -> [a] -> [Int]
findIndices p xs        =  [ i | (x,i) <- zip xs [0..], p x ]

nub                     :: Eq a => [a] -> [a]
nub                     =  nubBy (==)

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

delete                  :: Eq a => a -> [a] -> [a]
delete                  =  deleteBy (==)

deleteBy                :: (a -> a -> Bool) -> a -> [a] -> [a]
deleteBy eq x []        = []
deleteBy eq x (y:ys)    = if x `eq` y then ys else y : deleteBy eq x ys

(\\)                    :: Eq a => [a] -> [a] -> [a]
(\\)                    =  foldl (flip delete)

deleteFirstsBy          :: (a -> a -> Bool) -> [a] -> [a] -> [a]
deleteFirstsBy eq       =  foldl (flip (deleteBy eq))

union                   :: Eq a => [a] -> [a] -> [a]
union                   =  unionBy (==)    

unionBy                 :: (a -> a -> Bool) -> [a] -> [a] -> [a]
unionBy eq xs ys        =  xs ++ deleteFirstsBy eq (nubBy eq ys) xs

intersect               :: Eq a => [a] -> [a] -> [a]
intersect               =  intersectBy (==)

intersectBy             :: (a -> a -> Bool) -> [a] -> [a] -> [a]
intersectBy eq xs ys    =  [x | x <- xs, any (eq x) ys]

intersperse             :: a -> [a] -> [a]
intersperse sep []      =  []
intersperse sep [x]     =  [x]
intersperse sep (x:xs)  =  x : sep : intersperse sep xs

-- transpose является ленивой и в отношении строк, и в отношении столбцов,
--       и работает для непрямоугольных 'матриц'
-- Например, transpose [[1,2],[3,4,5],[]]  =  [[1,3],[2,4],[5]]
-- Обратите внимание, что [h | (h:t) <- xss] --- не то же самое, что (map head xss)
--      потому что первый отбрасывает пустые подсписки внутри xss
transpose                :: [[a]] -> [[a]]
transpose []             = []
transpose ([]     : xss) = transpose xss
transpose ((x:xs) : xss) = (x : [h | (h:t) <- xss]) : 
                           transpose (xs : [t | (h:t) <- xss])

partition               :: (a -> Bool) -> [a] -> ([a],[a])
partition p xs          =  (filter p xs, filter (not . p) xs)

-- group делит указанный в аргументе список на список списков одинаковых, соседних
-- элементов.  Например,
-- group "Mississippi" == ["M","i","ss","i","ss","i","pp","i"]
group                   :: Eq a => [a] -> [[a]]
group                   =  groupBy (==)

groupBy                 :: (a -> a -> Bool) -> [a] -> [[a]]
groupBy eq []           =  []
groupBy eq (x:xs)       =  (x:ys) : groupBy eq zs
                           where (ys,zs) = span (eq x) xs

-- inits xs возвращает список начальных сегментов xs, наиболее короткий --- в начале списка.
-- Например, inits "abc" == ["","a","ab","abc"]
inits                   :: [a] -> [[a]]
inits []                =  [[]]
inits (x:xs)            =  [[]] ++ map (x:) (inits xs)

-- tails xs возвращает список всех конечных сегментов xs, наиболее длинный --- в начале списка.
-- Например, tails "abc" == ["abc", "bc", "c",""]
tails                   :: [a] -> [[a]]
tails []                =  [[]]
tails xxs@(_:xs)        =  xxs : tails xs

isPrefixOf               :: Eq a => [a] -> [a] -> Bool
isPrefixOf []     _      =  True
isPrefixOf _      []     =  False
isPrefixOf (x:xs) (y:ys) =  x == y && isPrefixOf xs ys

isSuffixOf              :: Eq a => [a] -> [a] -> Bool
isSuffixOf x y          =  reverse x `isPrefixOf` reverse y

mapAccumL               :: (a -> b -> (a, c)) -> a -> [b] -> (a, [c])
mapAccumL f s []        =  (s, [])
mapAccumL f s (x:xs)    =  (s'',y:ys)
                           where (s', y ) = f s x
                                 (s'',ys) = mapAccumL f s' xs

mapAccumR               :: (a -> b -> (a, c)) -> a -> [b] -> (a, [c])
mapAccumR f s []        =  (s, [])
mapAccumR f s (x:xs)    =  (s'', y:ys)
                           where (s'',y ) = f s' x
                                 (s', ys) = mapAccumR f s xs

unfoldr                 :: (b -> Maybe (a,b)) -> b -> [a]
unfoldr f b             = case f b of
                                Nothing    -> []
                                Just (a,b) -> a : unfoldr f b

sort                    :: (Ord a) => [a] -> [a]
sort                    =  sortBy compare

sortBy                  :: (a -> a -> Ordering) -> [a] -> [a]
sortBy cmp              =  foldr (insertBy cmp) []

insert                  :: (Ord a) => a -> [a] -> [a]
insert                  = insertBy compare

insertBy                :: (a -> a -> Ordering) -> a -> [a] -> [a]
insertBy cmp x []       =  [x]
insertBy cmp x ys@(y:ys')
                        =  case cmp x y of
                                GT -> y : insertBy cmp x ys'
                                _  -> x : ys

maximumBy               :: (a -> a -> Ordering) -> [a] -> a
maximumBy cmp []        =  error "List.maximumBy: пустой список"
maximumBy cmp xs        =  foldl1 max xs
                        where
                           max x y = case cmp x y of
                                        GT -> x
                                        _  -> y

minimumBy               :: (a -> a -> Ordering) -> [a] -> a
minimumBy cmp []        =  error "List.minimumBy: пустой список"
minimumBy cmp xs        =  foldl1 min xs
                        where
                           min x y = case cmp x y of
                                        GT -> y
                                        _  -> x

genericLength           :: (Integral a) => [b] -> a
genericLength []        =  0
genericLength (x:xs)    =  1 + genericLength xs

genericTake             :: (Integral a) => a -> [b] -> [b]
genericTake _ []        =  []
genericTake 0 _         =  []
genericTake n (x:xs) 
   | n > 0              =  x : genericTake (n-1) xs
   | otherwise          =  error "List.genericTake: отрицательный аргумент"

genericDrop             :: (Integral a) => a -> [b] -> [b]
genericDrop 0 xs        =  xs
genericDrop _ []        =  []
genericDrop n (_:xs) 
   | n > 0              =  genericDrop (n-1) xs
   | otherwise          =  error "List.genericDrop: отрицательный аргумент"

genericSplitAt          :: (Integral a) => a -> [b] -> ([b],[b])
genericSplitAt 0 xs     =  ([],xs)
genericSplitAt _ []     =  ([],[])
genericSplitAt n (x:xs) 
   | n > 0              =  (x:xs',xs'')
   | otherwise          =  error "List.genericSplitAt: отрицательный аргумент"
       where (xs',xs'') =  genericSplitAt (n-1) xs

genericIndex            :: (Integral a) => [b] -> a -> b
genericIndex (x:_)  0   =  x
genericIndex (_:xs) n 
        | n > 0         =  genericIndex xs (n-1)
        | otherwise     =  error "List.genericIndex: отрицательный аргумент"
genericIndex _ _        =  error "List.genericIndex: слишком большой индекс"

genericReplicate        :: (Integral a) => a -> b -> [b]
genericReplicate n x    =  genericTake n (repeat x)
 
zip4                    :: [a] -> [b] -> [c] -> [d] -> [(a,b,c,d)]
zip4                    =  zipWith4 (,,,)

zip5                    :: [a] -> [b] -> [c] -> [d] -> [e] -> [(a,b,c,d,e)]
zip5                    =  zipWith5 (,,,,)

zip6                    :: [a] -> [b] -> [c] -> [d] -> [e] -> [f] -> 
                              [(a,b,c,d,e,f)]
zip6                    =  zipWith6 (,,,,,)

zip7                    :: [a] -> [b] -> [c] -> [d] -> [e] -> [f] ->
                              [g] -> [(a,b,c,d,e,f,g)]
zip7                    =  zipWith7 (,,,,,,)

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 _ _ _ _ _      =  []

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 _ _ _ _ _ _    =  []

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 _ _ _ _ _ _ _  =  []

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 _ _ _ _ _ _ _ _ = []

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))
                                 ([],[],[],[])

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))
                                 ([],[],[],[],[])

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))
                                 ([],[],[],[],[],[])

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))
                         ([],[],[],[],[],[],[])


Описание Haskell 98
наверх | назад | вперед | содержание | предметный указатель функций
Декабрь 2002