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.

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

>>> fold $ Node (Leaf (Sum 1)) (Sum 3) (Leaf (Sum 5))
Sum {getSum = 9}

>>> fold (repeat Nothing)
* Hangs forever *

>>> take 12 $ fold $ map (\i -> [i..i+2]) [0..]
[0,1,2,1,2,3,2,3,4,3,4,5]
>>> sum $ take 4000000 $ fold $ map (\i -> [i..i+2]) [0..]
2666668666666

>>> foldMap Sum [1, 3, 5]
Sum {getSum = 9}

>>> foldMap Product [1, 3, 5]
Product {getProduct = 15}

>>> foldMap (replicate 3) [1, 2, 3]
[1,1,1,2,2,2,3,3,3]

>>> import qualified Data.ByteString.Lazy as L
>>> import qualified Data.ByteString.Builder as B
>>> let bld :: Int -> B.Builder; bld i = B.intDec i <> B.word8 0x20
>>> let lbs = B.toLazyByteString $ foldMap bld [0..]
>>> L.take 64 lbs
"0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24"

>>> :set -XGeneralizedNewtypeDeriving
>>> import Data.Bits (Bits, FiniteBits, xor, zeroBits)
>>> import Data.Foldable (foldMap')
>>> import Numeric (showHex)
>>> >>> newtype X a = X a deriving (Eq, Bounded, Enum, Bits, FiniteBits)
>>> instance Bits a => Semigroup (X a) where X a <> X b = X (a `xor` b)
>>> instance Bits a => Monoid    (X a) where mempty     = X zeroBits
>>> >>> let bits :: [Int]; bits = [0xcafe, 0xfeed, 0xdeaf, 0xbeef, 0x5411]
>>> (\ (X a) -> showString "0x" . showHex a $ "") $ foldMap' X bits
"0x42"

foldr f z [x1, x2, ..., xn] == x1 `f` (x2 `f` ... (xn `f` z)...)

foldr f z = foldr f z . toList

>>> foldr (||) False [False, True, False]
True

>>> foldr (||) False []
False

>>> foldr (\c acc -> acc ++ [c]) "foo" ['a', 'b', 'c', 'd']
"foodcba"

>>> foldr (||) False (True : repeat False)
True

>>> foldr (||) False (repeat False ++ [True])
* Hangs forever *

>>> take 5 $ foldr (\i acc -> i : fmap (+3) acc) [] (repeat 1)
[1,4,7,10,13]

foldl f z [x1, x2, ..., xn] == (...((z `f` x1) `f` x2) `f`...) `f` xn

foldl f z = foldl f z . toList

>>> foldl (+) 42 [1,2,3,4]
52

>>> foldl (\acc c -> c : acc) "abcd" "efgh"
"hgfeabcd"

>>> foldl (\a _ -> a) 0 $ repeat 1
* Hangs forever *

foldl' f z = foldl' f z . toList

>>> foldr1 (+) [1..4]
10

>>> foldr1 (+) []
Exception: Prelude.foldr1: empty list

>>> foldr1 (+) Nothing
*** Exception: foldr1: empty structure

>>> foldr1 (-) [1..4]
-2

>>> foldr1 (&&) [True, False, True, True]
False

>>> foldr1 (||) [False, False, True, True]
True

>>> foldr1 (+) [1..]
* Hangs forever *

foldl1 f = foldl1 f . toList

>>> foldl1 (+) [1..4]
10

>>> foldl1 (+) []
*** Exception: Prelude.foldl1: empty list

>>> foldl1 (+) Nothing
*** Exception: foldl1: empty structure

>>> foldl1 (-) [1..4]
-8

>>> foldl1 (&&) [True, False, True, True]
False

>>> foldl1 (||) [False, False, True, True]
True

>>> foldl1 (+) [1..]
* Hangs forever *

>>> toList Nothing
[]

>>> toList (Just 42)
[42]

>>> toList (Left "foo")
[]

>>> toList (Node (Leaf 5) 17 (Node Empty 12 (Leaf 8)))
[5,17,12,8]

>>> toList [1, 2, 3]
[1,2,3]

>>> null []
True

>>> null [1]
False

>>> null [1..]
False

>>> length []
0

>>> length ['a', 'b', 'c']
3
>>> length [1..]
* Hangs forever *

>>> 3 `elem` []
False

>>> 3 `elem` [1,2]
False

>>> 3 `elem` [1,2,3,4,5]
True

>>> 3 `elem` [1..]
True

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

>>> maximum [1..10]
10

>>> maximum []
*** Exception: Prelude.maximum: empty list

>>> maximum Nothing
*** Exception: maximum: empty structure

>>> minimum [1..10]
1

>>> minimum []
*** Exception: Prelude.minimum: empty list

>>> minimum Nothing
*** Exception: minimum: empty structure

>>> sum []
0

>>> sum [42]
42

>>> sum [1..10]
55

>>> sum [4.1, 2.0, 1.7]
7.8

>>> sum [1..]
* Hangs forever *

>>> product []
1

>>> product [42]
42

>>> product [1..10]
3628800

>>> product [4.1, 2.0, 1.7]
13.939999999999998

>>> product [1..]
* Hangs forever *

foldrM :: (Foldable t, Monad 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, Monad 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, Applicative 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 () Источник

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 () Источник

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

sequenceA_ аналогична sequence_, но обобщена для действий Applicative.

Примеры

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

asum :: (Foldable t, Alternative f) => t (f a) -> f a Источник

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

asum аналогична msum, но обобщена для Alternative.

Примеры

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

mapM_ :: (Foldable t, Monad m) => (a -> m b) -> t a -> m () Источник

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

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

forM_ :: (Foldable t, Monad m) => t a -> (a -> m b) -> m () Источник

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

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

sequence_ :: (Foldable t, Monad m) => t (m a) -> m () Источник

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

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

msum :: (Foldable t, MonadPlus m) => t (m a) -> m a Источник

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

msum аналогична asum, но специализирована для MonadPlus.

Примеры

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

concat :: Foldable t => t [a] -> [a] Источник

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

Примеры

>>> 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] Источник

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

Примеры

>>> 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 Источник

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 Источник

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 Источник

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

Примеры

>>> 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 Источник

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

Примеры

>>> 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 Источник

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

Примеры

>>> 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' нет левоассоциативного аналога.

Таким образом, для некоторых сворачиваемых структур 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 экземпляра моноиды).

Существуют также гибридные случаи, когда выбранный метод и/или оператор не подходят для поставленной задачи. В результате свёртка может не выдавать промежуточных результатов до обработки всего входа или не вычислять результаты строго по ходу работы, откладывая все вычисления до момента вычисления большого итогового thunk. Таких ситуаций следует избегать: нужно выбрать более подходящий метод 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).

И наоборот, ожидается, что реализация 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 [] представлен как data: он либо пуст, либо является ячейкой cons, содержащей первый элемент и хвост списка. Класс Foldable позволяет представлять итераторы в альтернативном виде — как функции, которые принимают оператор и начальный аккумулятор и выдают сводный результат.

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

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

{-# 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 вместо исходных методов, специфичных для List (см. предложение FTP). Варианты, специфичные для List, пока доступны в GHC.OldList, однако этот модуль предназначен лишь для переходного периода и в будущем может быть удалён.

Неожиданное поведение может быть связано с экземпляром Foldable для пары (a,), которая теперь ведёт себя как одноэлементный контейнер Foldable во втором слоте. В контекстах, где ожидается конкретный мономорфный тип и вы хотите полагаться на сообщения об ошибках типов при рефакторинге, может иметь смысл определить и использовать менее полиморфные варианты некоторых методов 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] «Суть шаблона Iterator», авторы Джереми Гиббонс и Бруно Оливейра, в сборнике Математически структурированное функциональное программирование, 2006; доступно онлайн: http://www.cs.ox.ac.uk/people/jeremy.gibbons/publications/#iterator.
• [3] «Учебное введение во всеобщность и выразительность свёртки», автор Грэм Хаттон, J. Functional Programming 9 (4): 355–372, июль 1999; доступно онлайн: http://www.cs.nott.ac.uk/~pszgmh/fold.pdf.