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

0

В  модуле Foldable   собраны определения программных   сущностей языка  Haskell, которые  определяют общий интерфейс и  утилитарные функции для структур данных, которые могут быть «свёрнуты» в единственное значение.

Другими словами, в этом модуле определяется класс для представления типов, на которые можно обобщить функции foldl (см. стр. 253) и foldr (см. стр. 254). В теории категорий такой интерфейс называется катаморфизмом. Использование:

import Data.Foldable

Многие функции  из этого модуля имеют те же  самые  наименования,  что и функции из стандартного модуля Prelude,  а  также  модулей Monad (см. раздел 7.5.) и List (см. раздел 8.19.), поэтому обычно этот модуль импортируется квалифицированно,  либо одноимённые функции из указанных модулей скрываются при импорте.

Главная программная сущность, определённая в рассматриваемом модуле,  — класс Foldable,  который и определяет интерфейс к типам, чьи значения могут быть свёрнуты.

Класс:  Foldable

Описание: интерфейс к типам данных, значения которых могут быть свёрнуты к атомарному значению. Из всего набора методов можно определить либо метод foldMap, либо метод foldr, остальные методы выражены через указанные. Определение:

class Foldable t where

fold :: Monoid m   => t m   ->  m

foldMap  :: Monoid m   => (a  ->  m)  ->  t a ->  m foldr :: (a  ->  b ->  b)  ->  b ->  t a ->  b foldl :: (a  ->  b ->  a)  ->  a ->  t b ->  a foldr1 :: (a  ->  a ->  a)  ->  t a  -> a

foldl1 :: (a  ->  a ->  a)  ->  t a ->  a

Метод fold комбинирует элементы типа данных при помощи операций класса Monoid (см. стр. 385). С другой стороны, метод foldMap сначала преобразует тип данных в моноид, а лишь затем  производит свёртку. В этом процессе главное, чтобы экземпляры класса Monoid в действительности удовлетворяли теоретикокатегорным законам для моноидов.

Методы foldl и foldr представляют собой левоассоциативную  и правоассоциативную свёртку типов соответственно. Также  и  методы foldl1 и foldr1 являются вариантами методов foldl и foldr, для которых нет надобности ука-

зывать начальное значение для свёртки. В качестве него используется начальный элемент сворачиваемого значения.

Для этого класса определены экземпляры следующих типов: Array,  Digit, Elem, FingerTree,  IntMap, Maybe, Map, Node, Seq, Set, Tree, ViewL, ViewR и []. Функция: foldr’

Описание: строгий вариант правоассоциативной свёртки foldr.

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

foldr’ :: Foldable t => (a  ->  b ->  b)  ->  b ->  t  a ->  b foldr’ f z  xs  = foldl f’ id xs  z

where

f’ k  x  z  = k  $! f x  z

Функция: foldl’

Описание: строгий вариант левоассоциативной свёртки foldl.

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

foldl’ :: Foldable t => (a  ->  b ->  a)  ->  a ->  t  b ->  a foldl’ f z  xs  = foldr f’ id xs  z

where

f’ x  k  z  = k  $! f z  x

Функция: foldrM

Описание: монадический вариант правоассоциативной свёртки foldr.

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

foldrM :: (Foldable t, Monad  m) => (a  ->  b ->  m   b)  ->  b ->  t  a  ->  m   b foldrM f z  xs  = foldl f’ return xs  z

where

f’ k  x  z  = f x  z  >>= k

Функция: foldlM

Описание: монадический вариант левоассоциативной свёртки foldl.

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

foldlM :: (Foldable t, Monad  m) => (a  ->  b ->  m   a)  ->  a ->  t  b  ->  m   a foldlM f z  xs  = foldr f’ return xs  z

where

f’ x  k  z  = f z  x  >>= k

Функция: traverse-

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

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

traverse_ :: (Foldable t, Applicative f) => (a  ->  f b)  ->  t a ->  f () traverse_ f = foldr ((*>) . f) (pure   ())

Функция: for-

Описание: вариант функции traverse_, у которого порядок аргументов обратный.

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

for_ :: (Foldable t, Applicative f) => t a ->  (a  ->  f  b)  ->  f () for_ = flip traverse_

Функция: sequenceA-

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

sequenceA_ :: (Foldable t, Applicative f) => t  (f  a)  ->  f () sequenceA_ = foldr (*>) (pure   ())

Функция: asum

Описание: обобщение функции concat  (см. стр. 309) для набора произвольных действий.

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

asum :: (Foldable t, Alternative f) => t  (f a)  ->  f a asum = foldr (<|>)  empty

Функция: mapM-

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

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

mapM_  :: (Foldable t, Monad  m) => (a  ->  m   b)  ->  t a  ->  m   () mapM_  f = foldr ((>>) . f) (return ())

Функция: forM-

Описание: вариант функции mapM_, у которого аргументы идут в обратном порядке.

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

forM_  :: (Foldable t, Monad  m) => t a ->  (a  ->  m   b)  ->  m   () forM_  = flip mapM_

Функция: sequence-

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

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

sequence_ :: (Foldable t, Monad  m) => t (m a)  ->  m   () sequence_ = foldr (>>)  (return ())

Функция: msum

Описание: обобщение функции concat  (см. стр. 309) для набора произвольных монадических действий.

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

msum  :: (Foldable t, MonadPlus m) => t (m  a)  ->  m   a msum  = foldr mplus mzero

Функция: toList

Описание: преобразует произвольную  структуру в список.

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

toList :: Foldable t => t  a  ->  [a] toList = foldr  (:)  []

Функция: concat

Описание: конкатенация всех списков в сворачиваемой структуре в один список.

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

concat  :: Foldable t =>  t  [a] ->  [a] concat  =  fold

Функция: concatMap

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

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

concatMap :: Foldable t => (a  ->  [b])  ->  t a ->  [b] concatMap = foldMap

Функция: and

Описание: возвращает логическое произведение (операция «И») для  всех значений типа Bool в сворачиваемой структуре данных. Для того чтобы функция вернула результат True, структура должна быть конечной. Для результата False структура может быть бесконечной, но хотя бы одно значение False должно находиться на конечной позиции.

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

and :: Foldable t => t  Bool  ->  Bool and =  getAll  . foldMap  All

Функция: or

Описание: возвращает логическую сумму (операция «ИЛИ»)  для всех значений типа Bool в сворачиваемой структуре данных. Для того чтобы функция вернула результат False, структура должна быть конечной. Для результата True структура может быть бесконечной, но хотя бы одно значение True должно находиться на конечной позиции.

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

or  :: Foldable t => t  Bool  ->  Bool or  =  getAny  . foldMap  Any

Функция: any

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

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

any :: Foldable t => (a  ->  Bool)   ->  t a  ->  Bool any p = getAny  . foldMap  (Any  .  p)

Функция: all

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

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

all :: Foldable t => (a  ->  Bool)   ->  t a  ->  Bool all p = getAll . foldMap  (All .  p)

Функция: sum

Описание: возвращает сумму элементов в сворачиваемой структуре.

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

sum :: (Foldable t, Num  a)  =>  t a ->  a sum = getSum .  foldMap  Sum

Функция: product

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

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

product :: (Foldable t, Num  a)  =>  t a ->  a product = getProduct .  foldMap  Product

Функция: maximum

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

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

maximum  :: (Foldable t, Ord a)  =>  t a ->  a maximum  = foldr1 max

Функция: maximumBy

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

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

maximumBy  :: Foldable t => (a  ->  a ->  Ordering)  ->  t a ->  a maximumBy  cmp = foldr1 max’

where

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

_    ->  y

Функция: minimum

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

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

minimum  :: (Foldable t, Ord a)  => t a ->  a minimum  = foldr1  min

Функция: minimumBy

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

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

minimumBy  :: Foldable t => (a  ->  a ->  Ordering)  ->  t a ->  a minimumBy  cmp = foldr1  min’

where

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

_    ->  x

Функция: elem

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

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

elem :: (Foldable t, Eq a)  => a ->  t a ->  Bool elem = any . (==)

Функция: notElem

Описание: обращение предиката elem.

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

notElem :: (Foldable t, Eq a)  => a ->  t a  ->  Bool notElem x  = not  . elem x

Функция: find

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

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

find :: Foldable t => (a  ->  Bool)   ->  t a ->  Maybe a find p = listToMaybe . concatMap  (\x  ->  if p x

then  [x] else  [])

Данный модуль является обновлённой и более  совершенной  версией модуля FunctorM, который в свою очередь объявлен устаревшим и выводится из состава стандартных библиотек языка Haskell. Совместно с модулем Traversable (см. раздел 8.28.) этот  модуль предоставляет  всю функциональность (и даже больше), которую предоставлял модуль FunctorM.

Остаётся отметить, что  за этот модуль в поставке  языка  Haskell  отвечает Р.  Патерсон, с которым  можно  связаться по  адресу  электронной почты ross@soi.city.ac.uk.

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

По теме:

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