Почему фолд слева ожидать (a → b → a) вместо (b → a → a)?

Интересно, почему функция, ожидаемая словом слева, имеет подпись типа a -> b -> a вместо b -> a -> a. Есть ли конструктивное решение?

В Haskell, например, я должен написать foldl (\xs x -> x:xs) [] xs, чтобы отменить список вместо более короткого foldl (:) [] xs (что было бы возможно с b -> a -> a). С другой стороны, существуют варианты использования, которые требуют стандартного a -> b -> a. В Scala это может быть добавлено: xs.foldLeft(List.empty[Int]) ((xs, x) => xs:+x), которое может быть записано как xs.foldLeft(List.empty[Int]) (_:+_).

Проводится ли соразмерно больше случаев использования, требующих заданной сигнатуры типа вместо альтернативного, или существуют другие решения, которые привели к тому, что дизайн, оставшийся слева, имеет в Haskell и Scala (и, вероятно, много других языков)?

Ответы

Ответ 1

Концептуально говоря, правая складка, скажем foldr f z [1..4], заменяет список следующего вида

со значением выражения следующего вида

Если бы мы представляли это выражение в одной строке, все круглые скобки связывались бы справа, поэтому имя right fold: (1 `f` (2 `f` (3 `f` (4 `f` z)))). Левая складка в некотором смысле двойственна к правой складке. В частности, мы хотели бы, чтобы форма соответствующей диаграммы для левой складки была зеркальным отображением для левой складки, как в следующем:

Если бы мы выписали эту диаграмму в одной строке, мы получили бы выражение, где все круглые скобки ассоциированы слева, что хорошо сочетается с именем левой складки:

((((z `f` 1) `f` 2) `f` 3) `f` 4)

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

Ответ 2

Подпись типа foldl :: (a -> b -> a) -> a -> [b] -> a; естественно, что функция объединения имеет начальное значение слева, потому что она сочетается с элементами списка. Точно так же вы заметите, что foldr имеет это наоборот. Усложнение в определении обратного - это то, что вы используете выражение лямбда, где flip было бы лучше: foldl (flip (:)) [] xs, что также имеет приятное сходство между понятиями flip и reverse.

Ответ 3

Потому что вы пишете (a /: bs) для foldLeft в короткой форме; это оператор, который подталкивает a через все bs, поэтому естественно написать функцию таким же образом (т.е. (A,B) => A). Обратите внимание, что foldRight делает это в другом порядке.

Ответ 4

Скажите, что у вас есть это:

List(4, 2, 1).foldLeft(8)(_ / _)

То же самое, что:

((8 / 4) / 2) / 1