Clojure: Сворачивание списков, функции свёртки reduce
Функции map и filter обрабатывают списки, сохраняя саму структуру. Но иногда нужно избавиться от этой самой структуры, вычислив какое-то итоговое значение. Простейший пример — сумма всех чисел в списке. Или текст, собранный из списка строк.
В процедурных языках для получения итоговых значений по списку проходят с использованием цикла и промежуточный результат хранят в отдельной переменной — в так называемом аккумуляторе.
Декларативным же аналогом такого цикла будет операция сворачивания (folding) или, как ещё говорят, получение свёртки (fold). Суть сворачивания списка заключается в последовательном применении некоторой бинарной операции к очередному элементу списка и текущему значению аккумулятора у с целью получить новое значение аккумулятора. Давайте рассмотрим процесс сворачивания списка (list 1 2 3 4) в сумму чисел. Начальным значением аккумулятора будет 0, а операцией — +. Сложить числа можно как минимум двумя способами:
- двигаясь от первого элемента к последнему, слева-направо
(((0 + 1) + 2) + 3) + 4
- двигаясь от последнего элемента к первому, справа-налево
1 + (2 + (3 + (4 + 0)))
Для операции сложения не имеет значения то, какой из вариантов мы выберем. Потому что операция сложения ассоциативна. Но далеко не все операции таковы: например, при конкатенации строк важно, последнюю мы будем с первой складывать или наоборот!
Однако из-за того, что Clojure недостаточно ленив, то в нем используется только свертка слева-направо, с помощью функции reduce:
(reduce + 0 (list 1 2 3)) ; 6
(reduce - 0 (list 1 2 3)) ; -6
Попробуем теперь выводить каждое новое значение на экран, игнорируя аккумулятор:
(defn f [acc x]
(println x))
(reduce f nil '(1 2 3))
; => 1
; => 2
; => 3
В большинстве случаев используют левую свёртку (reduce) потому, что она более интуитивна — двигается от первого элемента к последнему — и работает эффективнее. Однако иногда полезна именно правая, но в стандартной библиотеке она отсутствует.
Стоит напоследок упомянуть, что reduce не может обходить несколько списков одновременно, как это делает map, поэтому придется предварительно подготовить обрабатываемые списки в промежуточный.
Задание
Реализуйте функцию max-delta, которая должна принимать два списка чисел и вычислять максимальную разницу (абсолютное значение разницы) между соответствующими парами элементов.
Пример использования:
(max-delta
(list 10 -15 35)
(list 2 -12 42)) ; 8
Вам пригодятся функции Math/abs и max:
(Math/abs 42) ; 42
(Math/abs -13) ; 13
(max 1 5 3) ; 5
Упражнение не проходит проверку — что делать? 😶
Если вы зашли в тупик, то самое время задать вопрос в «Обсуждениях». Как правильно задать вопрос:
- Обязательно приложите вывод тестов, без него практически невозможно понять что не так, даже если вы покажете свой код. Программисты плохо исполняют код в голове, но по полученной ошибке почти всегда понятно, куда смотреть.
В моей среде код работает, а здесь нет 🤨
Тесты устроены таким образом, что они проверяют решение разными способами и на разных данных. Часто решение работает с одними входными данными, но не работает с другими. Чтобы разобраться с этим моментом, изучите вкладку «Тесты» и внимательно посмотрите на вывод ошибок, в котором есть подсказки.
Мой код отличается от решения учителя 🤔
Это нормально 🙆, в программировании одну задачу можно выполнить множеством способов. Если ваш код прошел проверку, то он соответствует условиям задачи.
В редких случаях бывает, что решение подогнано под тесты, но это видно сразу.
Прочитал урок — ничего не понятно 🙄
Создавать обучающие материалы, понятные для всех без исключения, довольно сложно. Мы очень стараемся, но всегда есть что улучшать. Если вы встретили материал, который вам непонятен, опишите проблему в «Обсуждениях». Идеально, если вы сформулируете непонятные моменты в виде вопросов. Обычно нам нужно несколько дней для внесения правок.
Кстати, вы тоже можете участвовать в улучшении курсов: внизу есть ссылка на исходный код уроков, который можно править прямо из браузера.
Ваше упражнение проверяется по этим тестам
1(ns reduce-test
2 (:require [test-helper :refer [assert-solution]]
3 [index :refer [max-delta]]))
4
5(assert-solution
6 [['() '()] ['(-5) '(-15)] ['(0) '(42)] ['(10 -15 35) '(2 -12 42)]]
7 [0 10 42 8]
8 max-delta)
9Решение учителя откроется через:
