Доказательство и выводы
Перевод статьи 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. Скоро подъедет подкаст, не теряйтесь.
