Главная » Haskell » Модуль List

0

опять же  создан в  рамках  разгрузки  стандартного модуля Prelude  от излишка определений  программных сущностей и разнесения таких определений по разным модулям в зависимости от типа данных. Соответственно, в этом модуле собраны определения функций, которые работают со списками. А поскольку подавляющее большинство функций в этом модуле имеют те же

самые названия, что и функции в модуле Prelude,  этот модуль необходимо импортировать квалифицированно:

import qualified  Data.List  as List

Ну и само собой разумеется, что в этом модуле описаны только функции, поскольку тип данных [] (список) реализован на уровне синтаксиса языка Haskell.

Далее в этом разделе описываются  только функции, дополнительные к функциям стандартного модуля Prelude, поскольку все функции для работы со списками, которые определены в Prelude, определены и в рассматриваемом модуле. Перечень функций из стандартного модуля Prelude приведён в главе 6.. Функция: intersperse

Описание: «прорежает» элементы списка заданным символом.  Например, если на вход этой функции подан символ ’,’ и список "abcde",  то на выходе получится список "a,b,c,d,e".

Определение:

intersperse :: a ->  [a]  ->  [a]

intersperse _

[]

= []

intersperse _

[x]

= [x]

intersperse sep (x:xs) = x  : sep : intersperse sep xs

Функция: transpose

Описание: транспонирует матрицу, представленную в виде списка списков. Например: 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])

Функция: mapAccumL

Описание:  комбинирует   свойства  функций   map    (см.   стр.   356)  и   foldl (см. стр. 253), возвращая пару, состоящую из вычисленного значения аккумулятора и списка, полученного при помощи применения заданной функции к каждому элементу исходного списка.

Определение:

mapAccumL  :: (acc  ->  x  ->  (acc, y)) ->  acc  ->  [x]  ->  (acc, [y]) mapAccumL  _ s  []     = (s, [])

mapAccumL  f s  (x:xs) =  (s’’, y:ys) where

(s’, y) = f s  x

(s’’, ys)  = mapAccumL  f s’ xs

Функция: mapAccumR

Описание:  комбинирует   свойства  функций   map    (см.   стр.   356)   и   foldr (см. стр. 254), возвращая пару, состоящую из вычисленного значения аккумулятора и списка, полученного при помощи применения заданной функции к каждому элементу исходного списка.

Определение:

mapAccumR  :: (acc  ->  x  ->  (acc, y)) ->  acc  ->  [x]  ->  (acc, [y]) mapAccumR  _ s  []     =   (s, [])

mapAccumR  f s  (x:xs) =    (s’’, y:ys) where

(s’’,  y) = f s’ x

(s’, ys)  = mapAccumR  f s  xs

Функция: unfoldr

Описание: функция, обратная по своему действию функции foldr (см. стр. 254). Разворачивает атомарное значение в список, руководствуясь значением Nothing в качестве критерия остановки.

Определение:

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

Just  (a, new_b) ->  a:unfoldr f new_b Nothing                 ->  []

Функция: group

Описание: группирует элементы списка по признаку совпадения следующих друг за другом элементов.

Определение:

group  :: Eq a => [a]  ->  [[a]] group  =  groupBy (==)

Функция: groupBy

Описание: обобщение функции group, позволяющее передавать в качестве первого аргумента предикат для группировки.

Определение:

groupBy :: (a  ->  a ->  Bool)   ->  [a]  ->  [[a]] groupBy _   []     = []

groupBy eq (x:xs) =  (x:ys):groupBy eq zs where

(ys, zs)  = span  (eq  x) xs

Функция: inits

Описание: возвращает список всех начал заданного списка. Последним элементом результата будет как раз исходный список.

Определение:

inits :: [a]  ->  [[a]] inits  []          =  [[]]

inits (x:xs) = [[]] ++ map  (x:) (inits  xs)

Функция: tails

Описание: возвращает список всех окончаний заданного списка. Первым элементом результата будет как раз исходный список.

Определение:

tails :: [a]  ->  [[a]] tails []                 =  [[]]

tails xxs@(_:xs)  = xxs  : tails xs

Функция: isPrefixOf

Описание: возвращает значение True, если первый список является началом второго списка (или они совпадают).

Определение:

isPrefixOf :: (Eq  a)  => [a] ->  [a] ->  Bool isPrefixOf [] _                   =  True

isPrefixOf _   []                 =  False

isPrefixOf (x:xs) (y:ys) = x  == y  &&  isPrefixOf xs  ys

Функция: isSuffixOf

Описание: возвращает значение True, если первый список является окончанием второго списка (или они совпадают).

Определение:

isSuffixOf :: (Eq  a)  => [a] ->  [a] ->  Bool isSuffixOf x  y  = reverse  x  ‘isPrefixOf‘ reverse  y

Функция: isInfixOf

Описание: возвращает значение True, если первый список содержится полностью во втором списке (или они совпадают).

Определение:

isInfixOf :: (Eq  a)  => [a] ->  [a] ->  Bool

isInfixOf needle  haystack  = any (isPrefixOf  needle)  (tails haystack)

Функция: find

Описание: возвращает первый элемент списка, удовлетворяющий заданному предикату.  Если ни  одного такого  элемента в списке  нет, возвращает значение Nothing.

Определение:

find :: (a  ->  Bool)   ->  [a]  ->  Maybe a find p =  listToMaybe . filter p

Функция: partition

Описание: разбивает список на два подсписка, в первом из которых содержатся элементы, удовлетворяющие заданному предикату, во втором  — не удовлетворяющие соответственно.

Определение:

partition :: (a  ->  Bool)   ->  [a] ->  ([a], [a]) partition p xs  = foldr  (select p)  ([], []) xs

where

select p x  ~(ts, fs) | p x             = (x:ts, fs)

| otherwise = (ts, x:fs)

Функция:  elemIndex

Описание: возвращает индекс (начиная с 0) первого элемента списка, который равен заданному. Если ничего не найдено, возвращает значение Nothing. Определение:

elemIndex  :: Eq a => a ->  [a] ->  Maybe Int elemIndex  x  = findIndex  (x ==)

Функция: elemIndices

Описание: возвращает список  индексов всех вхождений заданного  элемента в список.

Определение:

elemIndices :: Eq a => a ->  [a]  ->  [Int] elemIndices x  =  findIndices  (x ==)

Функция: findIndex

Описание: обобщение функции elemIndex, позволяющее передавать первым аргументом предикат, при помощи которого ищутся элементы.

Определение:

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

Функция: findIndices

Описание: обобщение функции elemIndices, позволяющее передавать  первым аргументом предикат, при помощи которого ищутся элементы.

Определение:

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

Набор функций zip3 — zip7 является вариантами функции zip (см. стр. 269) для количества входных списков от 3 до 7 соответственно. Результатом работы будут кортежи размера от 3 до 7.

Также и набор функций zipWith3  — zipWith7  является вариантами функции zipWith (см. стр. 269) для количества входных списков от 3 до 7 соответственно. Результатом работы будут кортежи размера от 3 до 7.

Наконец, набор функций unzip3  —  unzip7  являются  вариантами  функции unzip  (см. стр. 270) для размера кортежей во входном списке от 3 до 7 соответственно. Результатом работы будет кортеж размера от 3 до 7.

Функция: nub

Описание: возвращает список, составленный из элементов исходного списка, в котором нет повторяющихся элементов.

Определение:

nub :: (Eq  a)  =>  [a] ->  [a] nub l = nub’  l  []

where

nub’  [] _                                     = []

nub’  (x:xs) ls | x  ‘elem‘ ls = nub’  xs  ls

| otherwise     = x:nub’ xs  (x:ls)

Функция: nubBy

Описание:  обобщение функции nub, позволяющее передавать в качестве первого параметра предикат, при помощи которого осуществляется сравнение элементов. Определение:

nubBy :: (a  ->  a ->  Bool)  ->  [a] ->  [a] nubBy eq l =  nubBy’  l []

where

nubBy’  [] _                                             = []

nubBy’  (y:ys) xs  | elem_by eq y  xs  = nubBy’  ys  xs

| otherwise            = y:nubBy’ ys  (y:xs)

Функция: delete

Описание: удаляет первое вхождение заданного элемента из списка.

Определение:

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

Функция: deleteBy

Описание:  обобщение функции delete, позволяющее передавать в качестве первого параметра предикат, при помощи которого осуществляется  сравнение элементов.

Определение:

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

Функция: deleteFirstBy

Описание: вариант функции deleteBy,  в котором элементы второго списка удаляются из первого (первые вхождения).

Определение:

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

Функция: (\\)

Описание: возвращает неассоциативную разницу двух списков. В результате применения (xsys)  будет список, состоящий из элементов  списка xs, из которого удалены первые вхождения каждого элемента списка ys.

Определение:

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

Функция: union

Описание: возвращает объединение двух списков. Элементы из второго списка, которые дублируют элементы первого списка, не включаются в результат. Однако первый список включается в результат без изменений, несмотря на дублирование элементов (если таковое имеется).

Определение:

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

Функция: unionBy

Описание: обобщение функции union, позволяющее передавать в качестве первого параметра предикат, при помощи которого осуществляется  сравнение элементов.

Определение:

unionBy  :: (a  ->  a ->  Bool)   ->  [a]  ->  [a] ->  [a]

unionBy  eq xs  ys  = xs  ++ foldl (flip (deleteBy eq))  (nubBy eq ys)  xs

Функция: intersect

Описание: возвращает  пересечение двух списков, состоящее только из тех элементов, которые  входят в оба заданных списка. Однако  если в первом списке имеются дублирующиеся  элементы, все они попадут в результат.

Определение:

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

Функция: intersectBy

Описание: обобщение функции intersect, позволяющее передавать  в качестве первого параметра предикат, при помощи которого  осуществляется  сравнение элементов.

Определение:

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

Функция: insert

Описание: вставляет заданный элемент в список на позицию, на которой он будет меньше или равен следующему элементу в списке. В частности, если исходный список отсортирован, то и результат окажется отсортированным.

Определение:

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

Функция: insertBy

Описание:  обобщение функции insert, позволяющее передавать в качестве первого параметра предикат, при помощи которого осуществляется  сравнение элементов.

Определение:

insertBy :: (a  ->  a ->  Ordering) ->  a ->  [a]  ->  [a] insertBy _     x  [] = [x]

insertBy cmp x  ys@(y:ys’) = case  cmp x  y  of

GT  ->  y:insertBy  cmp x  ys’

_    ->  x:ys

Функция: sortBy

Описание: вариант функции sort (см. стр. 270), в который  можно  передавать в качестве  первого параметра предикат, при помощи  которого  осуществляется сравнение элементов.

Определение:

sortBy :: (a  ->  a ->  Ordering) ->  [a]  ->  [a] sortBy cmp l = mergesort  cmp l

Функция: maximumBy

Описание: вариант функции maximum (см. стр. 311), в который можно передавать в качестве  первого параметра предикат, при помощи  которого  осуществляется сравнение элементов.

Определение:

maximumBy  :: (a  ->  a ->  Ordering) ->  [a] ->  a maximumBy  _ []   = error  "List.maximumBy:  empty list" maximumBy  cmp xs  = foldl1 max xs

where

max x  y  = case  cmp x  y  of GT  ->  x

_   ->  y

Функция: minimumBy

Описание: вариант функции minimum (см. стр. 312), в который можно передавать в качестве  первого параметра предикат, при помощи  которого  осуществляется сравнение элементов.

Определение:

minimumBy  :: (a  ->  a ->  Ordering) ->  [a]  -> a minimumBy  _ []   = error  "List.minimumBy: empty list" minimumBy  cmp  xs  = foldl1 min xs

where

min x  y  =  case  cmp  x  y  of GT  ->  y

_    ->  x

Функция: genericLength

Описание: обобщение функции length (см. стр. 393), позволяющее возвращать в качестве  результата значение типа,  являющегося  экземпляром класса Num (а не только типа Int).

Определение:

genericLength :: (Num i)  => [b] ->  i genericLength  []    = 0

genericLength (_:l) = 1 +  genericLength l

Функция: genericTake

Описание: обобщение функции take (см. стр. 395), позволяющее задавать в качестве входного индекса значение произвольного типа, являющегося экземпляром класса Integral (а не только типа Int).

Определение:

genericTake  :: (Integral i) => i  ->  [a] ->  [a] genericTake  0 _                           =  []

genericTake  _ []                         =  []

genericTake  n (x:xs) | n > 0 = x  : genericTake  (n  1)  xs

genericTake  _

_                        = error  "List.genericTake:  negative argument"

Функция: genericDrop

Описание: обобщение функции drop (см. стр. 395), позволяющее задавать в качестве входного индекса значение произвольного типа, являющегося экземпляром класса Integral (а не только типа Int).

Определение:

genericDrop   :: (Integral i) => i  ->  [a] ->  [a] genericDrop   0 xs                         =  xs

genericDrop   _ []                         =  []

genericDrop   n (_:xs) | n > 0 = genericDrop   (n  1)  xs

genericDrop   _ _                          = error  "List.genericDrop:  negative  argument"

Функция: genericSplitAt

Описание:  обобщение функции split (см. стр. 354), позволяющее задавать в качестве входного индекса значение произвольного  типа, являющегося экземпляром класса Integral (а не только типа Int).

Определение:

genericSplitAt :: (Integral i) => i ->  [b] ->  ([b], [b]) genericSplitAt 0 xs                        =  ([],  xs)

genericSplitAt _ []             = ([],  []) genericSplitAt n (x:xs) | n > 0 =  (x:xs’, xs’’)

where

(xs’, xs’’) = genericSplitAt  (n-1)  xs

genericSplitAt _ _                          = error "List.genericSplitAt:  negative  argument"

Функция: genericIndex

Описание:  обобщение функции index (см. стр. 394), позволяющее задавать в качестве входного индекса значение произвольного  типа, являющегося экземпляром класса Integral (а не только типа Int).

Определение:

genericIndex :: (Integral a)  => [b]  ->  a ->  b genericIndex (x:_)    0                         =  x

genericIndex (_:xs)  n | n > 0         = genericIndex  xs  (n-1)

| otherwise = error "List.genericIndex:  negative  argument." genericIndex _ _                                  = error "List.genericIndex:  index  too  large."

Функция: genericReplicate

Описание: обобщение функции replicate (см. стр. 259), позволяющее задавать в качестве входного индекса значение произвольного типа, являющегося экземпляром класса Integral (а не только типа Int).

Определение:

genericReplicate :: (Integral i) => i ->  a  ->  [a]  genericReplicate n x  =  genericTake  n (repeat x)

Источник: Душкин Р. В., Справочник по языку Haskell. М.: ДМК Пресс, 2008. 544 с., ил.

По теме:

  • Комментарии