Vadim Yalo
Apr 13, 2017 · 5 min read

Перевод статьи 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

devSchacht

Подкаст. Переводы. Веб-разработка.

Vadim Yalo

Written by

devSchacht

Подкаст. Переводы. Веб-разработка.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade