Data.Foldable

class Foldable (t :: Type -> Type) where Исходный код

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

Экземпляры могут быть автоматически получены путём включения расширения DeriveFoldable. Например, полученный экземпляр для бинарного дерева может быть:

{-# LANGUAGE DeriveFoldable #-}
data Tree a = Empty
            | Leaf a
            | Node (Tree a) a (Tree a)
    deriving Foldable

Более подробное описание можно найти в разделе Обзор в Data.Foldable.

Законы класса см. в разделе Законы в Data.Foldable.

foldrM :: (Foldable t, Монадный m) => (a -> b -> m b) -> b -> t a -> m b Исходный код

Монадное сложение элементов структуры справа налево.

Учитывая структуру t с элементами (a, b, c, ..., x, y), результат сложения с операторной функцией f эквивалентен:

foldrM f z t = do
    yy <- f y z
    xx <- f x yy
    ...
    bb <- f b cc
    aa <- f a bb
    return aa -- Just @return z@ when the structure is empty

Для Монады m, заданных двух функций f1 :: a -> m b и f2 :: b -> m c, их композиция по Клейсли (f1 >=> f2) :: a -> m c определяется следующим образом:

(f1 >=> f2) a = f1 a >>= f2

Другой способ понять foldrM заключается в том, что он эквивалентен применению к z композиции по Клейсли:

foldrM f z t = f y >=> f x >=> ... >=> f b >=> f a $ z

Моноидные эффекты foldrM выполняются справа налево, и, например, сложения бесконечных списков будут разветвляться.

Если на каком-то шаге оператор связывания (>>=) завершается (как, например, mzero в MonadPlus), оцененные эффекты будут взяты из хвоста последовательности элементов. Если вам нужно оценить моноидные эффекты слева направо или, возможно, завершиться после начальной последовательности элементов, вам нужно использовать foldlM вместо этого.

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

a `f` (b `f` (c `f` (... (x `f` (y `f` z))))).

Примеры

>>> let f i acc = do { print i ; return $ i : acc }
>>> foldrM f [] [0..3]
3
2
1
0
[0,1,2,3]

foldlM :: (Foldable t, Монадный m) => (b -> a -> m b) -> b -> t a -> m b Исходный код

Монадное сложение элементов структуры слева направо.

Учитывая структуру t с элементами (a, b, ..., w, x, y), результат сложения с операторной функцией f эквивалентен:

foldlM f z t = do
    aa <- f z a
    bb <- f aa b
    ...
    xx <- f ww x
    yy <- f xx y
    return yy -- Just @return z@ when the structure is empty

Для Монады m, заданных двух функций f1 :: a -> m b и f2 :: b -> m c, их композиция по Клейсли (f1 >=> f2) :: a -> m c определяется следующим образом:

(f1 >=> f2) a = f1 a >>= f2

Другой способ понять foldlM заключается в том, что он эквивалентен применению к z композиции по Клейсли:

foldlM f z t =
    flip f a >=> flip f b >=> ... >=> flip f x >=> flip f y $ z

Моноидные эффекты foldlM выполняются слева направо.

Если на каком-то шаге оператор связывания (>>=) завершается (как, например, mzero в MonadPlus ), оцененные эффекты будут взяты из начального сегмента последовательности элементов. Если вам нужно оценить моноидные эффекты справа налево или, возможно, завершиться после обработки хвоста последовательности элементов, вам нужно использовать foldrM вместо этого.

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

((((z `f` a) `f` b) ... `f` w) `f` x) `f` y

Примеры

>>> let f a e = do { print e ; return $ e : a }
>>> foldlM f [] [0..3]
0
1
2
3
[3,2,1,0]

traverse_ :: (Foldable t, Прикладной f) => (a -> f b) -> t a -> f () Исходный код

Преобразуйте каждый элемент структуры в Applicative действие, вычислите эти действия слева направо и игнорируйте результаты. Для версии, которая не игнорирует результаты, см. traverse.

traverse_ это то же самое, что и mapM_, но обобщено на Applicative действия.

Примеры

>>> traverse_ print ["Hello", "world", "!"]
"Hello"
"world"
"!"

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

for_ является traverse_ со своими аргументами, перевернутыми местами. Для версии, которая не игнорирует результаты, см. for. Это forM_ обобщено на Applicative действия.

for_ похож на forM_, но обобщен на Applicative действия.

Примеры

>>> for_ [1..4] print
1
2
3
4

sequenceA_ :: (Foldable t, Applicative f) => t (f a) -> f () Source

Выполнить каждое действие в структуре слева направо и проигнорировать результаты. Для версии, которая не игнорирует результаты, см. sequenceA.

sequenceA_ похож на sequence_, но обобщен на Applicative действия.

Примеры

>>> sequenceA_ [print "Hello", print "world", print "!"]
"Hello"
"world"
"!"

asum :: (Foldable t, Alternative f) => t (f a) -> f a Source

Сумма набора действий, используя (<|>), обобщение concat.

asum похож на msum, но обобщен на Alternative.

Примеры

>>> asum [Just "Hello", Nothing, Just "World"]
Just "Hello"

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

Применить к каждому элементу структуры монадическое действие, выполнить эти действия слева направо и проигнорировать результаты. Для версии, которая не игнорирует результаты, см. mapM.

mapM_ похож на traverse_, но специализирован на монадических действиях.

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

forM_ является mapM_ со своими аргументами, перевернутыми местами. Для версии, которая не игнорирует результаты, см. forM.

forM_ похож на for_, но специализирован на монадических действиях.

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

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

sequence_ похож на sequenceA_, но специализирован на монадических действиях.

msum :: (Foldable t, MonadPlus m) => t (m a) -> m a Source

Сумма набора действий, используя (<|>), обобщение concat.

msum похож на asum, но специализирован на MonadPlus.

Примеры

>>> msum [Just "Hello", Nothing, Just "World"]
Just "Hello"

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

Конкатенация всех элементов контейнера списков.

Примеры

>>> concat (Just [1, 2, 3])
[1,2,3]

>>> concat (Left 42)
[]

>>> concat [[1, 2, 3], [4, 5], [6], []]
[1,2,3,4,5,6]

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

Применить функцию ко всем элементам контейнера и конкатенировать полученные списки.

Примеры

>>> concatMap (take 3) [[1..], [10..], [100..], [1000..]]
[1,2,3,10,11,12,100,101,102,1000,1001,1002]

>>> concatMap (take 3) (Just [1..])
[1,2,3]

and :: Foldable t => t Bool -> Bool Source

and возвращает конъюнкцию контейнера значений типа Bool. Для получения результата True, контейнер должен быть конечным; False, однако, результат получается из False значения, конечного по отношению к левому концу.

Примеры

>>> and []
True

>>> and [True]
True

>>> and [False]
False

>>> and [True, True, False]
False

>>> and (False : repeat True) -- Infinite list [False,True,True,True,...
False

>>> and (repeat True)
* Hangs forever *

or :: Foldable t => t Bool -> Bool Source

or возвращает дизъюнкцию контейнера значений типа Bool. Для получения результата False, контейнер должен быть конечным; True, однако, результат получается из True значения, конечного по отношению к левому концу.

Примеры

>>> or []
False

>>> or [True]
True

>>> or [False]
False

>>> or [True, True, False]
True

>>> or (True : repeat False) -- Infinite list [True,False,False,False,...
True

>>> or (repeat False)
* Hangs forever *

any :: Foldable t => (a -> Bool) -> t a -> Bool Source

Определяет, удовлетворяет ли какое-либо из элементов структуры предикату.

Примеры

>>> any (> 3) []
False

>>> any (> 3) [1,2]
False

>>> any (> 3) [1,2,3,4,5]
True

>>> any (> 3) [1..]
True

>>> any (> 3) [0, -1..]
* Hangs forever *

all :: Foldable t => (a -> Bool) -> t a -> Bool Source

Определяет, удовлетворяют ли все элементы структуры предикату.

Примеры

>>> all (> 3) []
True

>>> all (> 3) [1,2]
False

>>> all (> 3) [1,2,3,4,5]
False

>>> all (> 3) [1..]
False

>>> all (> 3) [4..]
* Hangs forever *

maximumBy :: Foldable t => (a -> a -> Ordering) -> t a -> a Source

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

Примеры

>>> maximumBy (compare `on` length) ["Hello", "World", "!", "Longest", "bar"]
"Longest"

minimumBy :: Foldable t => (a -> a -> Ordering) -> t a -> a Исходный код

Наименьший элемент непустой структуры относительно заданной функции сравнения. Порядок структуры используется для разделения связей: если есть несколько наименьших элементов, выбирается самый левый из них.

Примеры

>>> minimumBy (compare `on` length) ["Hello", "World", "!", "Longest", "bar"]
"!"

notElem :: (Foldable t, Eq a) => a -> t a -> Bool infix 4 Исходный код

notElem является отрицанием elem.

Примеры

>>> 3 `notElem` []
True

>>> 3 `notElem` [1,2]
True

>>> 3 `notElem` [1,2,3,4,5]
False

>>> 3 `notElem` [1..]
False

>>> 3 `notElem` ([4..] ++ [3])
* Hangs forever *

find :: Foldable t => (a -> Bool) -> t a -> Maybe a Исходный код

Функция find принимает предикат и структуру и возвращает самый левый элемент структуры, соответствующий предикату, или Nothing если такого элемента нет.

Примеры

>>> find (> 42) [0, 5..]
Just 45

>>> find (> 12) [1..7]
Nothing

Класс Foldable обобщает некоторые общие функции Data.List на структуры, которые могут быть приведены к суммарному значению по одному элементу за раз.

Левые и правые слияния

Вклад каждого элемента в конечный результат комбинируется с аккумулятором с помощью подходящего оператора. Оператор может быть явно задан вызывающим абонентом, как в foldr, или может быть неявным, как в length. В случае foldMap, вызывающий абонент предоставляет функцию, отображающую каждый элемент в подходящий Monoid, что позволяет объединить вклады по элементам с помощью функции mappend моноида.

Ключевое различие заключается между левоассоциативными и правоассоциативными слияниями:

• При левоассоциативных слияниях аккумулятор является частичным слиянием элементов, которые предшествуют текущему элементу, и передается оператору в качестве первого (левого) аргумента. Наружное применение оператора объединяет вклад последнего элемента структуры с вкладами всех его предшественников.
• При правоассоциативных слияниях аккумулятор является частичным слиянием элементов, которые следуют за текущим элементом, и передается оператору в качестве второго (правого) аргумента. Наружное применение оператора объединяет вклад первого элемента структуры с вкладами всех его преемников.

Эти два типа слияний типизируются левоассоциативным строгим foldl' и правоассоциативным ленивым foldr.

foldl' :: Foldable t => (b -> a -> b) -> b -> t a -> b
foldr  :: Foldable t => (a -> b -> b) -> b -> t a -> b

Пример использования:

>>> foldl' (+) 0 [1..100]
5050
>>> foldr (&&) True (List.repeat False)
False

Первый аргумент обоих – это явный оператор, который объединяет вклад элемента структуры с частичным слиянием, соответственно, либо предшествующих, либо последующих элементов структуры.

Второй аргумент обоих – это начальное значение аккумулятора z типа b. Это результат слияния, когда структура пуста. Когда структура непуста, это значение аккумулятора, объединённое с первым элементом в левоассоциативных слияниях, или с последним элементом в правоассоциативных слияниях.

Третий и последний аргумент – это структура Foldable содержащая элементы (a, b, c, …).

• foldl' принимает аргумент оператора вида:

  f :: b -- accumulated fold of the initial elements
    -> a -- current element
    -> b -- updated fold, inclusive of current element
  

  Если последний элемент структуры – y, результат слияния:

  g y . … . g c . g b . g a $ z
    where g element !acc = f acc element
  

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

• foldr принимает аргумент оператора вида:

  f :: a -- current element
    -> b -- accumulated fold of the remaining elements
    -> b -- updated fold, inclusive of current element
  

  результат слияния:

  f a . f b . f c . … $ z

  Если каждый вызов f для текущего элемента e, (указанного ниже как (f e)) возвращает структуру, в которой её второй аргумент захвачен в лениво вычисляемой компоненте, то слияние оставшихся элементов доступно вызывающему абоненту foldr в виде ожидающего вычисления (thunk), которое вычисляется только тогда, когда эта компонента оценивается.

  В противном случае, если какой-либо из (f e) игнорирует свой второй аргумент, слияние останавливается на этом, и оставшиеся элементы не используются. В результате, foldr хорошо подходит для определения как рекурсивных, так и краткозамкнутых редукций.

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

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

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

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

• Ленивые методы fold, foldMap и toList не имеют правоассоциативных аналогов.
• Строгий метод foldMap' не имеет левоассоциативного аналога.

Таким образом, для некоторых структур Foldable foldr' столь же эффективен, как foldl' для строгого сокращения, а foldl может быть так же уместен для рекурсивных слияний, как и foldr.

Наконец, в некоторых менее распространённых структурах (например, списках с добавлением в конец snoc) итерации справа налево эффективнее, чем слева направо. Такие структуры плохо подходят для экземпляра Foldable и, возможно, лучше всего обрабатываются через свои специфичные для типа интерфейсы. Если тем не менее предоставляется экземпляр Foldable , материал в следующих разделах также применим к ним, заменив каждый метод на метод с противоположной ассоциативностью (если доступен) и поменяв порядок аргументов оператора слияния.

Возможно, придётся уделить особое внимание строгости оператора слияния, когда его строгость отличается между первым и вторым аргументами. Например, в то время как (+) ожидается, что будет коммутативным и строгим по отношению к обоим аргументам, оператор конкатенации списков (++) не является коммутативным и строг только по отношению к начальному конструктору первого аргумента. Слияние:

myconcat xs = foldr (\a b -> a ++ b) [] xs

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

revconcat xs = foldr (\a b -> b ++ a) [] xs

в котором общая стоимость увеличивается как с количеством объединяемых списков, так и с количеством в конечном итоге потреблённых элементов. Более эффективный способ объединения списков в обратном порядке – использовать:

revconcat = foldr (++) [] . reverse

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

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

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

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

Различие между этими типами свёртки имеет решающее значение, как при принятии решения о том, какой метод Foldable использовать для эффективного выполнения сокращения, так и при написании экземпляров Foldable для новых структур. Ниже приводится более подробный обзор каждого типа.

Общие примеры строгого рекурсивного сокращения — это различные функции агрегирования, такие как sum, product, length, а также более сложные сводки, такие как подсчёт частоты. Эти функции возвращают только одно значение после обработки всей структуры входных данных. В таких случаях ленивая обработка хвоста структуры входных данных не только не нужна, но и неэффективна. Поэтому эти и подобные свёртки следует реализовывать в терминах строгих левоассоциативных методов Foldable (обычно foldl') для эффективного сокращения в постоянном пространстве.

Обратно, реализация Foldable для новой структуры должна гарантировать, что foldl' фактически выполняет строгое левоассоциативное сокращение.

Метод foldMap' является частным случаем foldl', в котором начальное значение аккумулятора — mempty, а оператор — mappend . f, где f отображает каждый элемент входных данных в Monoid в вопросе. Поэтому foldMap' является подходящим выбором практически при тех же условиях, что и foldl', и его реализация для данной структуры Foldable также должна быть строгим левоассоциативным сокращением.

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

length  = getSum     . foldMap' (const (Sum 1))
sum     = getSum     . foldMap' Sum
product = getProduct . foldMap' Product

[ Фактические значения по умолчанию используют принуждения для оптимизации getSum и getProduct. ]

Полный список строгих рекурсивных функций в этом модуле:

• При условии, что оператор строго в отношении своего левого аргумента:

  foldl' :: Foldable t => (b -> a -> b) -> b -> t a -> b

• При условии, что mappend строго в отношении своего левого аргумента:

  foldMap' :: (Foldable t, Monoid m) => (a -> m) -> t a -> m

• При условии, что экземпляр определён правильно:

  length    :: Foldable t => t a -> Int
  sum       :: (Foldable t, Num a) => t a -> a
  product   :: (Foldable t, Num a) => t a -> a
  maximum   :: (Foldable t, Ord a) => t a -> a
  minimum   :: (Foldable t, Ord a) => t a -> a
  maximumBy :: Foldable t => (a -> a -> Ordering) -> t a -> a
  minimumBy :: Foldable t => (a -> a -> Ordering) -> t a -> a
  

Общие примеры ленивого корекурсивного сокращения — это функции, которые отображают и сплющивают структуру в ленивый поток значений результата, т. е. итератор по преобразованным элементам входных данных. В таких случаях важно выбрать метод Foldable который ленив в отношении хвоста структуры, например, foldr (или foldMap, если результат Monoid имеет ленивый mappend как, например, у ByteString Builders).

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

Функция toList ниже лениво преобразует структуру Foldable в список. Обратите внимание, что это преобразование может быть необратимым, например, для контейнера с ключами (Map, HashMap, …) выходной поток содержит только значения, а не ключи. Обратимые преобразования в/из списков пар (key, value) обычно доступны в модулях для конкретных типов контейнеров.

toList = foldr (:) []

Более сложным примером является конкатенация списка списков, выраженная как вложенная правая свёртка (обходя (++)). Мы можем проверить, что определение действительно лениво, выполнив свёртку бесконечного списка списков и взяв начальный сегмент.

>>> myconcat = foldr (\x z -> foldr (:) z x) []
>>> List.take 15 $ myconcat $ List.map (\i -> [0..i]) [0..]
[0,0,1,0,1,2,0,1,2,3,0,1,2,3,4]

Конечно, в этом случае другой способ достижения того же результата — это генератор списка:

myconcat xss = [x | xs <- xss, x <- xs]

Полный список ленивых корекурсивных функций в этом модуле:

• При условии, что функция сокращения ленива в отношении своего второго аргумента (в противном случае лучше использовать строгое рекурсивное сокращение):

  foldr  :: Foldable t => (a -> b -> b) -> b -> t a -> b
  foldr1 :: Foldable t => (a -> a -> a) -> t a -> a
  

• При условии, что Monoid mappend ленива в отношении своего второго аргумента (в противном случае лучше использовать строгое рекурсивное сокращение):

  fold    :: Foldable t => Monoid m => t m -> m
  foldMap :: Foldable t => Monoid m => (a -> m) -> t a -> m
  

• При условии, что экземпляр определён правильно:

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

Примеры сокращения с коротким замыканием включают различные булевы предикаты, проверяющие, удовлетворяют ли некоторые или все элементы структуры заданному условию. Поскольку они не обязательно потребляют весь список, они обычно используют foldr с оператором, который условно строго в отношении своего второго аргумента. Как только выполняется условие завершения, второй аргумент (хвост структуры входных данных) игнорируется. Результат не возвращается, пока это не произойдёт.

Ключевой отличительной чертой этих свёрок является условность строгости во втором аргументе; он иногда вычисляется, а иногда нет.

Самый простой (вырожденный случай) из них — это null, определяющий, пуста ли структура или нет. Для этого нужно только посмотреть на первый элемент, и только в той мере, существует ли он, а не его значение. В этом случае завершение гарантировано, и структуры входных данных бесконечной длины подходят.

Естественно, его стандартное определение использует ленивую свёртку foldr.

null = foldr (\_ _ -> False) True

Более общий пример — any, который применяет предикат к каждому элементу входных данных по очереди, пока не найдёт первый элемент, для которого предикат истиннен, после чего он возвращает успех. Если в бесконечном потоке входных данных предикат ложен для всех элементов, any не завершит работу, но, поскольку он работает в постоянном пространстве, он, как правило, не выйдет из памяти, он просто будет зацикливаться вечно.

Полный список свёртки с коротким замыканием в этом модуле:

• Свёртки булевых предикатов. Эти функции строго проверяют элементы до тех пор, пока не будет выполнено условие, но затем возвращают результат, игнорируя остальную часть (ленивые в отношении хвоста). Они могут зацикливаться бесконечно, если входные данные неограничены, и ни один элемент не удовлетворяет условию завершения.

  null    :: Foldable t => t a -> Bool
  elem    :: Foldable t => Eq a => a -> t a -> Bool
  notElem :: (Foldable t, Eq a) => a -> t a -> Bool
  and     :: Foldable t => t Bool -> Bool
  or      :: Foldable t => t Bool -> Bool
  find    :: Foldable t => (a -> Bool) -> t a -> Maybe a
  any     :: Foldable t => (a -> Bool) -> t a -> Bool
  all     :: Foldable t => (a -> Bool) -> t a -> Bool
  

• Многие экземпляры (<|>) (например, экземпляр Maybe) являются условно ленивыми и используют или не используют свой второй аргумент в зависимости от значения первого. Они используются со свёртками ниже, которые завершаются как можно раньше, но в противном случае, как правило, продолжают работу. Некоторые экземпляры (например, для List) всегда строгие, но результат ленив в хвосте вывода, так что asum для списка списков на самом деле является корекурсивным. Эти свёртки определены в терминах foldr.

  asum :: (Foldable t, Alternative f) => t (f a) -> f a
  msum :: (Foldable t, MonadPlus m) => t (m a) -> m a
  

• Точно так же оператор (*>) в некоторых Applicative функторах и (>>) в некоторых монадах являются условно ленивыми и могут прервать цепочку вычислений. Нижеприведённые свёртки будут завершаться как можно раньше, но даже бесконечные циклы могут быть продуктивными здесь, когда они вычисляются исключительно ради своего потока побочных эффектов IO. См. Data.Traversable для обсуждения связанных функций.

  traverse_  :: (Foldable t, Applicative f) => (a -> f b) -> t a -> f ()
  for_       :: (Foldable t, Applicative f) => t a -> (a -> f b) -> f ()
  sequenceA_ :: (Foldable t, Applicative f) => t (f a) -> f ()
  mapM_      :: (Foldable t, Monad m) => (a -> m b) -> t a -> m ()
  forM_      :: (Foldable t, Monad m) => t a -> (a -> m b) -> m ()
  sequence_  :: (Foldable t, Monad m) => t (m a) -> m ()
  

• Наконец, есть ещё один частный случай, foldlM.

  foldlM :: (Foldable t, Monad m) => (b -> a -> m b) -> b -> t a -> m b

  Последовательность монадных эффектов идёт слева направо. Если на каком-то шаге оператор связывания (>>=) прерывается (как, например, mzero с MonadPlus, или исключение с MonadThrow, и т. д.), то вычисленные эффекты будут из начальной части последовательности элементов.

  :set -XBangPatterns
  import Control.Monad
  import Control.Monad.Trans.Class
  import Control.Monad.Trans.Maybe
  import Data.Foldable
  let f !_ e = when (e > 3) mzero >> lift (print e)
  runMaybeT $ foldlM f () [0..]

  0 1 2 3 Nothing

  Контрастируйте это с foldrM, которая упорядочивает монадные эффекты справа налево и поэтому расходится при свёртке неограниченной структуры входных данных, никогда не имея возможности прервать свёртку.

  let f e _ = when (e > 3) mzero >> lift (print e)
  runMaybeT $ foldrM f () [0..]

  …зависает…

  Когда структура конечна, foldrM выполняет монадные эффекты справа налево, возможно, прерывая свёртку после обработки хвостовой части последовательности элементов.

  let f e _ = when (e < 3) mzero >> lift (print e)
  runMaybeT $ foldrM f () [0..5]

  5 4 3 Nothing

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

foldr' :: Foldable t => (a -> b -> b) -> b -> t a -> b
foldl  :: Foldable t => (b -> a -> b) -> b -> t a -> b
foldl1 :: Foldable t => (a -> a -> a) -> t a -> a
foldrM :: (Foldable t, Monad m) => (a -> b -> m b) -> b -> t a -> m b

Левые ленивые свёртки (используемые корекурсивно) и foldrM (используемые для упорядочения действий справа налево) могут быть эффективными в структурах, чьи экземпляры Foldable используют эффективный итератор справа налево для вычисления ленивых левых свёрок снаружи внутрь с правого элемента.

Строгая foldr' наименее вероятно будет полезна, так как структуры, поддерживающие упорядочение только справа налево, не очень распространены.

До сих пор мы не обсуждали генеративную рекурсию. В отличие от рекурсивного сокращения или корекурсии, вместо обработки последовательности элементов, уже находящихся в памяти, генеративная рекурсия предполагает получение, возможно, неограниченной последовательности значений из начального значения-затравки. Каноническим примером этого является unfoldr для списков, с вариантами, доступными для векторов и различных других структур.

Ключевая проблема со списками, когда они используются генеративно как итераторы, а не как контейнеры для бедных (см. [1]), заключается в том, что такие итераторы потребляют память, когда используются более одного раза. Однократное прохождение списка как итератора будет выполняться в постоянном объёме памяти, но как только список сохраняется для повторного использования, вся последовательность его элементов хранится в памяти, а второе прохождение считывает копию, а не генерирует элементы заново. Иногда лучше вычислять элементы заново, чем запоминать список.

Запоминание происходит, потому что встроенный список Haskell [] представлен как данные, либо пустые, либо ячейка cons, содержащая первый элемент и хвост списка. Класс Foldable позволяет использовать альтернативное представление итераторов как функций, которые принимают оператор и начальное значение аккумулятора и возвращают итоговый результат.

Пакет fmlist использует этот подход, представляя список через его foldMap действие.

Ниже мы реализуем аналогичную структуру данных, используя представление, основанное на foldr. Это пример кодирования Чёрча (названного в честь Альonzo Church, изобретателя лямбда-исчисления).

{-# LANGUAGE RankNTypes #-}
newtype FRList a = FR { unFR :: forall b. (a -> b -> b) -> b -> b }

Поле unFR этого типа по существу является его методом foldr со списком в качестве первого, а не последнего аргумента. Таким образом, мы сразу получаем экземпляр Foldable (и функцию toList отображающую FRList в обычный список).

instance Foldable FRList where
    foldr f z l = unFR l f z
    -- With older versions of @base@, also define sum, product, ...
    -- to ensure use of the strict 'foldl''.
    -- sum = foldl' (+) 0
    -- ...

Мы можем преобразовать обычный список в FRList с помощью:

fromList :: [a] -> FRList a
fromList as = FRList $ \ f z -> foldr f z as

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

-- | Immediately return the initial accumulator
nil :: FRList a
nil = FRList $ \ _ z -> z
{-# INLINE nil #-}

-- | Fold the tail to use as an accumulator with the new initial element
cons :: a -> FRList a -> FRList a
cons a l = FRList $ \ f z -> f a (unFR l f z)
{-# INLINE cons #-}

Более важно, что мы также можем напрямую определить ключевой строительный блок для генеративной рекурсии:

-- | Generative recursion, dual to `foldr`.
unfoldr :: (s -> Maybe (a, s)) -> s -> FRList a
unfoldr g s0 = FR generate
  where generate f z = loop s0
          where loop s | Just (a, t) <- g s = f a (loop t)
                       | otherwise = z
{-# INLINE unfoldr #-}

Что, например, может быть специализировано для числовых диапазонов:

-- | Generate a range of consecutive integral values.
range :: (Ord a, Integral a) => a -> a -> FRList a
range lo hi =
    unfoldr (\s -> if s > hi then Nothing else Just (s, s+1)) lo
{-# INLINE range #-}

Программа ниже, при компиляции с оптимизацией:

main :: IO ()
main = do
    let r :: FRList Int
        r = range 1 10000000
     in print (sum r, length r)

выводит ожидаемый результат без заметной работы сборщика мусора, несмотря на повторное использование FRList термина r.

(50000005000000,10000000)
    52,120 bytes allocated in the heap
     3,320 bytes copied during GC
    44,376 bytes maximum residency (1 sample(s))
    25,256 bytes maximum slop
         3 MiB total memory in use (0 MB lost due to fragmentation)

Слабая нормальная форма FRList — это абстракция лямбды, а не значение данных, и повторное использование не приводит к запоминанию. Повторное использование итератора выше несколько искусственно, при вычислении нескольких сгибов над общим списком, вы обычно должны пройти по списку только один раз. Цель состоит в том, чтобы продемонстрировать, что отдельные вычисления sum и length выполняются эффективно в постоянном объёме памяти, несмотря на повторное использование. Это не было бы так с списком [1..10000000].

Однако это искусственно упрощённое сокращение. Чаще всего, вероятно, будут какие-то выделения памяти во внутреннем цикле, но временное хранилище будет собираться мусором по мере необходимости, и общее использование памяти останется умеренным и не будет масштабироваться с размером списка.

Если мы вернёмся к встроенным спискам (т.е. []), но избежим повторного использования, выполнив сокращение за один проход, как показано ниже:

data PairS a b = P !a !b -- We define a strict pair datatype

main :: IO ()
main = do
    let l :: [Int]
        l = [1..10000000]
     in print $ average l
  where
    sumlen :: PairS Int Int -> Int -> PairS Int Int
    sumlen (P s l) a = P (s + a) (l + 1)

    average is =
        let (P s l) = foldl' sumlen (P 0 0) is
         in (fromIntegral s :: Double) / fromIntegral l

результат снова получается в постоянном объёме памяти:

5000000.5
         102,176 bytes allocated in the heap
           3,320 bytes copied during GC
          44,376 bytes maximum residency (1 sample(s))
          25,256 bytes maximum slop
               3 MiB total memory in use (0 MB lost due to fragmentation)

(и, фактически, быстрее, чем с FRList на небольшой фактор).

Структура списка [] работает как эффективный итератор, когда используется только один раз. Когда утечки памяти из-за повторного использования списков не влияют, и/или запоминание на самом деле желательно, стандартная реализация списка, вероятно, будет быстрее. Это не предложение заменить все ваши использования [] генеративной альтернативой.

Тип FRList можно было бы дополнительно расширить экземплярами Functor, Applicative, Monad, Alternative, и т.д., и тогда он мог бы предоставить полностью функциональный тип списка, оптимизированный для повторного использования без утечек памяти. Однако, если всё, что требуется, это экономичная с точки зрения памяти, дружественная к повторному использованию итерация, меньше, возможно, больше, и просто Foldable может быть достаточно.

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

Пакет foldl реализует прочный общий фреймворк для работы с этой ситуацией. Если вы решите сделать это сами, с небольшими предосторожностями, самые простые случаи несложно обработать напрямую. Вам просто нужно накапливать отдельные агрегаты как строгие компоненты одного типа данных, а затем применить финальное преобразование, чтобы извлечь составной результат. Например, вычисление среднего значения требует вычисления как sum , так и length структуры (непустой) и деления суммы на длину:

import Data.Foldable (foldl')

data PairS a b = P !a !b -- We define a strict pair datatype

-- | Compute sum and length in a single pass, then reduce to the average.
average :: (Foldable f, Fractional a) => f a -> a
average xs =
    let sumlen (P s l) a = P (s + a) (l + 1 :: Int)
        (P s l) = foldl' sumlen (P 0 0) xs
     in s / fromIntegral l

Приведённый выше пример несколько искусственный, некоторые структуры отслеживают свою длину внутри и могут вернуть её за O(1) времени, поэтому этот конкретный рецепт для средних значений не всегда самый эффективный. В целом, составные агрегатные функции больших структур выигрывают от однократного сокращения. Это особенно верно, когда повторное использование списка и запоминание его элементов таким образом избегаются.

Для многих структур разумные экземпляры Foldable могут быть получены автоматически, включив расширение GHC DeriveFoldable. Когда это работает, обычно нет необходимости определять пользовательский экземпляр вручную. Хотя в некоторых случаях можно получить немного более быстрый настроенный код, требуется осторожность, чтобы не создавать медленный код или код, который недостаточно ленив, строг или правилен.

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

Ниже мы создаём экземпляр Foldable для типа данных, представляющего бинарное дерево (конечное) с обходом в глубину.

>>> data Tree a = Empty | Leaf a | Node (Tree a) a (Tree a)

Подходящий экземпляр будет:

>>> :{
instance Foldable Tree where
   foldr f z Empty = z
   foldr f z (Leaf x) = f x z
   foldr f z (Node l k r) = foldr f (f k (foldr f z r)) l
:}

Случай Node — это правая свертка левого поддерева, начальное значение которого — правая свертка остальной части дерева.

Например, когда f является (:), все три случая возвращают непосредственное значение, соответственно z или ячейку cons, содержащую x или l, при этом остальная часть структуры, если таковая имеется, захвачена в ленивом туннеле. Это соответствует ожидаемому эффективному корекурсивному поведению foldr.

Альтернативно, можно определить foldMap:

instance Foldable Tree where
   foldMap f Empty = mempty
   foldMap f (Leaf x) = f x
   foldMap f (Node l k r) = foldMap f l <> f k <> foldMap f r

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

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

instance Foldable Tree where
   foldr f z Empty = z
   foldr f z (Leaf x) = f x z
   foldr f z (Node l k r) = foldr f (f k (foldr f z r)) l
   --
   foldMap f Empty = mempty
   foldMap f (Leaf x) = f x
   foldMap f (Node l k r) = foldMap f l <> f k <> foldMap f r
   --
   foldl f z Empty = z
   foldl f z (Leaf x) = f z x
   foldl f z (Node l k r) = foldl f (f (foldl f z l) k) r

Теперь итерация слева направо и справа налево по элементам структуры одинаково эффективна (обратите внимание на порядок вывода при использовании foldl):

>>> foldr (\e acc -> e : acc) [] (Node (Leaf 1) 2 (Leaf 3))
[1,2,3]
>>> foldl (\acc e -> e : acc) [] (Node (Leaf 1) 2 (Leaf 3))
[3,2,1]

Мы можем продолжить это и определить другие методы, отличные от по умолчанию...

Структура определения фактически допускает деревья, неограниченные с одной или обеих сторон. Единственная свертка, которая может правдоподобно завершиться для дерева, неограниченного с обеих сторон, — это null, когда она определена, как показано ниже. Определение по умолчанию в терминах foldr расходится, если дерево неограничено слева. Здесь мы определяем вариант, который избегает прохождения по дереву, чтобы найти самый левый элемент, и просто проверяет корневой узел.

   null Empty = True
   null _     = False

Это разумный выбор и для конечных деревьев.

На практике неограниченные деревья встречаются довольно редко и едва ли можно сказать, что они Foldable. Они обычно используют обход по ширине, и поддерживают только корекурсивные и краткосрочные сгибы (расходятся при строгом сокращении).

Возвращаясь к более простым экземплярам, определённым только в терминах foldr, довольно удивительно, что достаточно эффективная стандартная реализация строгого foldl' определяется через ленивый foldr , когда последний явно предоставляется экземпляром. Может быть полезно взглянуть на то, как это работает.

Иногда полезно, чтобы результатом применения foldr была функция. Это делается путём отображения элементов структуры в функции с одинаковыми типами аргумента и результата. Затем функции по элементам объединяются, чтобы дать конечный результат.

Например, мы можем поменять строгую левую свертку foldl' , написав:

foldl' f z xs = flippedFoldl' f xs z

с функцией flippedFoldl' , определённой ниже, с seq используется для обеспечения строгости в аккумуляторе:

flippedFoldl' f [] z = z
flippedFoldl' f (x : xs) z = z `seq` flippedFoldl' f xs (f z x)

Переписав с использованием лямбд, это:

flippedFoldl' f [] = \ b -> b
flippedFoldl' f (x : xs) = \ b -> b `seq` r (f b x)
    where r = flippedFoldl' f xs

Вышеприведённое имеет вид правой свертки, что позволяет переписать на:

flippedFoldl' f = \ xs -> foldr f' id xs
    where f' x r = \ b -> b `seq` r (f b x)

Теперь мы можем перевернуть это, чтобы получить foldl':

foldl' f z = \ xs -> foldr f' id xs z
          -- \ xs -> flippedFoldl' f xs z
  where f' x r = \ b -> b `seq` r (f b x)

Функция foldr f' id xs, применённая к z, строится рекурсивно, а её члены применяются к жадно вычисляемому аккумулятору прежде, чем дальнейшие члены применяются к результату. Как требуется, это выполняется в постоянном объёме памяти и может быть оптимизировано до эффективной циклической структуры.

(Фактическое определение foldl' помещает лямбда-выражения в определении f' выше как oneShot, что позволяет произвести дальнейшую оптимизацию).

Конструктор типов Endo из Data.Monoid связывает с каждым типом b newtype-инкапсулированный тип функций, отображающих b на себя. Функции из типа в себя называются эндоморфизмами, отсюда и название Endo. Тип Endo b является Monoid при композиции функций:

newtype Endo b = Endo { appEndo :: b -> b }
instance Semigroup Endo b where
    Endo f <> Endo g = Endo (f . g)
instance Monoid Endo b where
    mempty = Endo id

Для каждого Monoid m, у нас также есть Dual моноид Dual m, который объединяет элементы в обратном порядке:

newtype Dual m = Dual { getDual :: m }
instance Semigroup m => Semigroup Dual m where
    Dual a <> Dual b = Dual (b <> a)
instance Monoid m => Monoid Dual m where
    mempty = Dual mempty

С учётом вышеизложенного, ожидается, что экземпляры Foldable будут удовлетворять следующим законам:

Метод foldr должен быть эквивалентен по значению и строгости замене каждого элемента a структуры Foldable на Endo (f a), композиции их посредством foldMap и применению результата к базовому случаю z:

foldr f z t = appEndo (foldMap (Endo . f) t ) z

Аналогично, метод foldl должен быть эквивалентен по значению и строгости композиции функций flip f a в обратном порядке и применению результата к базовому случаю:

foldl f z t = appEndo (getDual (foldMap (Dual . Endo . flip f) t)) z

Когда элементы структуры берутся из Monoid, определение fold должно совпадать с foldMap id:

fold = foldMap id

Метод length должен совпадать с foldMap отображением каждого элемента на Sum 1 (Тип Sum абстрагирует числа как моноид относительно сложения).

length = getSum . foldMap (Sum . const 1)

sum, product, maximum, и minimum должны быть в сущности эквивалентны foldMap формам, например

sum     = getSum     . foldMap' Sum
product = getProduct . foldMap' Product

но обычно более эффективны, когда определяются более непосредственно как:

sum = foldl' (+) 0
product = foldl' (*) 1

Если структура Foldable имеет экземпляр Functor, то для каждой функции f, отображающей элементы в Monoid, она должна удовлетворять:

foldMap f = fold . fmap f

что подразумевает

foldMap f . fmap g = foldMap (f . g)

Поскольку Foldable не имеет Functor как суперкласс, можно определять экземпляры Foldable для структур, которые ограничивают типы их элементов. Поэтому, Set может быть Foldable, даже если множества сохраняют свои элементы в порядке возрастания. Это требует сравнимости элементов, что исключает определение экземпляра Functor для Set.

Класс Foldable позволяет использовать привычные выражения из типа List со структурами контейнеров, которые лучше подходят для данной задачи. Это поддерживает использование более подходящих типов данных Foldable, таких как Seq, Set, NonEmpty, и т. д., без необходимости новых выражений (см. [1] о том, когда не следует использовать списки).

Более общие методы класса Foldable теперь экспортируются из Prelude вместо оригинальных методов, специфичных для списков (см. предложение FTP). Варианты, специфичные для списков, пока доступны в GHC.OldList, но этот модуль предназначен только как временная помощь и может быть удалён в будущем.

Неожиданности могут возникнуть из-за экземпляра Foldable для 2-кортежа (a,), который теперь ведёт себя как контейнер с 1 элементом в своём втором слоте. В контекстах, где ожидается конкретный мономорфный тип, и вы хотите иметь возможность полагаться на ошибки типов для управления рефакторингом, может иметь смысл определить и использовать менее полиморфные варианты некоторых методов Foldable.

Ниже приведены два примера, демонстрирующие определение многоразового менее полиморфного sum и одноразовой специализации length:

{-# LANGUAGE TypeApplications #-}

mySum :: Num a => [a] -> a
mySum = sum

type SlowVector a = [a]
slowLength :: SlowVector -> Int
slowLength v = length @[] v

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

Возможно, стоит отметить, что, поскольку функция elem в классе Foldable несёт только ограничение Eq на тип элемента, поиск наличия или отсутствия элемента в структуре обычно занимает O(n) времени, даже для упорядоченных структур, таких как Set, которые потенциально способны выполнять поиск быстрее. (Функция member модуля Set несёт ограничение Ord, и может выполнять поиск за O(log n) времени).

Требуется альтернатива методу elem Foldable для абстракции потенциально более быстрого, чем линейный, поиска в общих структурах контейнеров. Этого можно достичь, определив дополнительный тип класса (например, HasMember ниже). Экземпляры такого типа класса (которые также являются Foldable) могут использовать линейный поиск elem в качестве крайнего средства, когда более быстрый поиск не поддерживается.

{-# LANGUAGE FlexibleInstances, MultiParamTypeClasses #-}

import qualified Data.Set as Set

class Eq a => HasMember t a where
    member :: a -> t a -> Bool

instance Eq a => HasMember [] a where
    member = elem
[...]
instance Ord a => HasMember Set.Set a where
    member = Set.member

Вышесказанное предполагает, что elem может быть неуместным в классе Foldable . Альтернативные идеи дизайна запрашиваются на трекере багов GHC через задачу #20421.

Обратите внимание, что некоторые оптимизации, специфичные для структуры, конечно, могут быть возможны непосредственно в соответствующем экземпляре Foldable, например, с Set, размер множества известен заранее, без итерации для подсчёта элементов, и его экземпляр length использует это, чтобы вернуть размер напрямую.

• [1] «Когда следует использовать списки в Haskell (в основном, не следует)», Иоганнес Валдманн, в arxiv.org, Программирование языков (cs.PL), по адресу https://arxiv.org/abs/1808.08329.
• [2] «Суть паттерна итератора», Джереми Гиббонс и Бруно Оливейра, в Mathematically-Structured Functional Programming, 2006, онлайн по адресу http://www.cs.ox.ac.uk/people/jeremy.gibbons/publications/#iterator.
• [3] «Учебное пособие по универсальности и выразительности fold», Грэхем Хаттон, J. Functional Programming 9 (4): 355–372, июль 1999, онлайн по адресу http://www.cs.nott.ac.uk/~pszgmh/fold.pdf.