Доказательство и выводы

Перевод статьи Tom Harding: Reductio and Abstract ’em. Опубликовано с разрешения автора.

О, привет, незнакомец! Давно не общались. Если тебе интересно, я сменил дом, работу и компанию с момента написания моей последней статьи, отсюда и перерыв. Прости! В любом случае, говоря о страшных переходах, вы когда-нибудь замечали, что вы можете написать каждую функцию списка с reduceRight?

… Э, нет, вы не можете?

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

const head = ([x, ... xs]) =>  x
const cons = ( x, xs ) => [x, ... xs]

Тут же мы можем увидеть, что cons странное имя для prepend. Я объясню почему это так чуть позже, пока что опустим это и пойдем дальше. До тех пор я обещаю, что это не отмазка!

… Так, хорошо. Что ты там говорил?

Давайте начнём со всеми любимой функции списка: map. В этой функции хорошо, что её накопитель другой список - мы преобразуем один список в другой!

const map = (f, xs) => xs.reduceRight(
(acc, x) => cons(f(x), acc), [])
)
// [2, 3, 4]
map(x => x + 1)([1, 2, 3])

Здорово, да? С этой реализацией, довольно просто получить вторую всеми любимую функцию списка —filter:

const filter = (p, xs) => xs.reduceRight(
(acc, x) => p(x) ? cons(x, acc)
: acc,
[]
)
// [1, 2]
filter(x => x < 3)([1, 2, 3, 4])

Бам! Если условие будет выполнено, мы сохраним элемент. В противном случае, мы пробросим накопитель нетронутым. Что насчёт третьей всеми любимой функции списка —reduce? … Ну, это немного сложно, поэтому давайте разбираться с ней.

Хорошо… а что насчёт ____?

Назовите её и мы напишем её! Может начнём с append?

const append = (x, xs) => xs.reduceRight(
(acc, h) => cons(h, acc), [x]
)
// [1, 2, 3, 4]
append(4)([1, 2, 3])

Эта операция reduceRight на самом деле ничего не делает, но начинается с непустым накопителем, в который уже добавлено значение! Таким же способом, мы можем написать concat:

const concat = (xs, ys) =>
xs.reduceRight(
(acc, h) => cons(h, acc), ys
)
// [1, 2, 3, 4]
concat([1, 2])([3, 4])

В любом случае, теперь у нас есть append, мы можем написать reverse:

const reverse = xs => xs.reduceRight(
(acc, x) => append(x, acc), []
)
// [3, 2, 1]
reverse([1, 2, 3])

Она просто берет каждый элемент с конца списка и переносит его в конец накопителя. Легко! Продолжаем, length еще проще:

const length = xs => xs.reduceRight(
(n, _) => n + 1, 0
)
// 4
length([1, 2, 3, 4])

Это всё весело, но это не взрывает мозг; есть вероятность, что вы уже видели получение длины через свёртку в какой-то момент. Почему бы нам не попробовать что-то посложнее? Давайте напишем elemAt — функция которая возвращает элемент по заданному индексу. Например, elemAt(2, xs) тоже самое, что xs[2]. Ах, да, верно: доступ к массиву — это свёртка.

const elemAt = (n, xs) => head(xs.reduce(
([e, n], x) => [n == 0 ? x : e, n - 1],
[undefined, n]
))
// 3
elemAt(2, [1, 2, 3])

Так, вот ещё хитрость: мы считаем индекс до того пока не получим 0, потом “сохраняем” значение из этой позиции. Но подождите! Мы использовали reduce, не reduceRight!

Хорошо, да, вы можете написать эту функцию с помощью reduceRight, и я оставлю это как (довольно сложное) упражнение для читателя. Однако гораздо проще разобраться с reduce. Кроме того, если мы сможем доказать, что reduce может быть записан с помощью reduceRight, это не уловка, не так ли?

const reduce = (f, acc, xs) =>
xs.reduceRight(
(accF, x) => z => accF(f(z, x)),
x => x
)(acc)

Поделом тебе за вопрос! Идея заключается в том, что мы сворачиваем список в функцию для вычисления reduce. Мы начали с x => x, которая ничего не делает, и потом применили новую функцию для каждого элемента в списке. Давайте пройдемся по простейшему примеру:

reduce((x, y) => x - y, 10, [1, 2])
  // Разворачиваем `reduce` в `reduceRight`
== [1, 2].reduceRight(
(g, x) => z => g(
((x, y) => x - y)(z, x)
),
       x => x
)(10)
  // Упрощаем редьюсер
== [1, 2].reduceRight(
(g, x) => z => g(z - x),
x => x
)(10)
  // Поглощаем первый элемент
== [1].reduceRight(
(g, x) => z => g(z - x),
z => (x => x)((x => x - 2)(z))
)(10)
  // Упрощаем некрасивый накопитель
== [1].reduceRight(
(g, x) => z => g(z - x),
x => x - 2
)(10)
  // Поглощаем следующий элемент
== [].reduceRight(
(g, x) => z => g(z - x),
z => (x => x - 2)((x => x - 1)(z))
)(10)
  // Упрощаем некрасивый накопитель
== [].reduceRight(
(g, x) => z => g(z - x),
z => z - 3
)(10)
  // `reduceRight` на [] == acc
== (z => z - 3)(10)
  // Вычисляем
== 7

Мы выжили! Может потребоваться пара прочтений, но основная мысль — это то, что наш накопитель создал функцию, выполняющую каждое действие задом наперёд. Конечно же, reduce и reduceRight вычислят одинаковые значения для (x, y) => x - y, поэтому попробуйте что-нибудь такое (x, y) => [x, y], чтобы почувствовать разницу.

Ты убедился? Мы можем рассмотреть еще примеры, если ты… нет? Ну что ж, хорошо. Давай вернёмся к тому, почему каждая функция списка — это вид reduceRight.

(Поразительно знакомый) список

Список может быть выражен как [] (пустой) или [x, ... xs], непустой список - элемент, за которым еще один список*. Это точно связанный список!

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

Представляем нашего героя

Запишем два выражения, которые определяют как reduceRight работает:

[].reduceRight(f, acc) = acc
[x, ... xs].reduceRight(f, acc) =
f(xs.reduceRight(f, acc), x)

Вот и весь reduceRight. Пустой список сворачивается до накопителя, непустой список сворачивается до fхвостовой свёртки и головы… Код яснее, чем предложение.

Теперь, когда reduceRight позволяет нам устанавливать пустое и непустое представление, и имеет накопитель, мы можем свободно изменять структуру листа полностью. Помните, что мы не можем написать length с помощью map, потому что map не позволяет нам изменять структуру (длину!) листа. Также, мы не можем написать length с помощью filter, потому что filter не имеет накопителя!

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

reduce против reduceRight?

Учитывая то, что вы можете получить reduceRight с помощью reduce, это может показаться странным брать за основу менее популярный. Ответ кроется в ленивых языках и бесконечности, и есть уже много объяснений ленивого reduceRight онлайн - вам не нужна моя плохая попытка!

И так… reduceRight может делать, что угодно со списками?

Да! Для дальнейшего чтения, катаморфизм ещё называется свёрткой, не предполагающую разворачивания (анаморфизм — больше чудесных названий!), и функция Ramda’ы unfold может объяснить, что это значит. Подумайте о функции, создающую диапазон, который разворачивает изначальное число в список от 0 до числа! Всё же, мы можем думать о ней ни как о функции списка, потому что она не функция списка, а просто функция, возвращающая список**.

tl;dr? Когда The Beatles сказали, что всё, что нам нужно — любовь, они, наверное, хотели сказать reduceRight.


На этом всё! Я надеюсь писать на регулярной основе, теперь я заселился. Увидимся в следующий раз!

Берегите себя ♥

* Просто как числа Пеано, где либо ноль (Z), либо на один больше, чем другие числа Пеано (S Peano).

** Если ты морщинистый математик, прости, это пособие для новичков!


Читайте нас на Medium, контрибьютьте на Github, общайтесь в группе Telegram, следите в Twitter и канале Telegram, рекомендуйте в VK и Facebook. Скоро подъедет подкаст, не теряйтесь.

Статья на Github