Racket: Сворачивание списков, функции свёртки foldl и foldr
Функции map
и filter
обрабатывают списки, сохраняя саму структуру. Но иногда нужно избавиться от этой самой структуры, вычислив какое-то итоговое значение. Простейший пример — сумма всех чисел в списке. Или текст, собранный из списка строк.
В процедурных языках для получения итоговых значений по списку проходят с использованием цикла и промежуточный результат хранят в отдельной переменной — в так называемом аккумуляторе.
Декларативным же аналогом такого цикла будет операция сворачивания (folding) или, как ещё говорят, получение свёртки (fold). Суть сворачивания списка заключается в последовательном применений некоторой бинарной операции к очередному элементу списка и текущему значению аккумулятора у с целью получить новое значение аккумулятора. Давайте рассмотрим процесс сворачивания списка (list 1 2 3 4)
в сумму чисел. Начальным значением аккумулятора будет 0
, а операцией — +
. Сложить числа можно как минимум двумя способами:
- двигаясь от первого элемента к последнему, слева-направо
(((0 + 1) + 2) + 3) + 4
- двигаясь от последнего элемента к первому, справа-налево
1 + (2 + (3 + (4 + 0)))
Для операции сложения не имеет значения то, какой из вариантов мы выберем. Потому что операция сложения ассоциативна. Но далеко не все операции таковы: например, при конкатенации строк важно, последнюю мы будет с первой складывать или наоборот!
Поэтому в Racket существуют оба способа сворачивания в виде функций foldl
и foldr
— левая и правая свёртки (способы "1" и "2" соответственно).
(foldr + 0 (list 1 2 3)) ; 6
(foldl + 0 (list 1 2 3)) ; 6
Тут всё понятно, сложение ассоциативно, вот и суммы сошлись. Усложним задачу, будем выводить каждое новое значение на экран, игнорируя аккумулятор:
(define (f x acc)
(displayln x))
(foldr f (void) (list 1 2 3))
; => 3
; => 2
; => 1
(foldl f (void) (list 1 2 3))
; => 1
; => 2
; => 3
Разница налицо!
В большинстве случаев используют левую свёртку (foldl
) потому, что она более интуитивна — двигается от первого элемента к последнему — и работает эффективнее. Однако иногда полезна именно правая foldr
, поэтому в стандартной библиотеке есть и она.
Стоит напоследок упомянуть, что foldl
и foldr
могут обходить несколько списков одновременно — так же, как это делает map
. Списки при этом должны иметь одинаковую длину, а функция-аргумент должна принимать n+1
аргументов для n
списков: по одному элементу от каждого списка плюс аккумулятор. Вот пример такого использования левой свёртки:
(define (f greeting name acc)
(string-append acc greeting ", " name "!\n"))
(display
(foldl f ""
(list "Hello" "Hi" "Good day")
(list "Bob" "Alice" "Tom")))
; => Hello, Bob!
; => Hi, Alice!
; => Good day, Tom!
; =>
Задание
Реализуйте функцию max-delta
, которая должна принимать два списка чисел и вычислять максимальную разницу (абсолютное значение разницы) между соответствующими парами элементов.
Пример использования:
(max-delta
(list 10 -15 35)
(list 2 -12 42)) ; 8
Вам пригодятся функции abs
и max
:
(abs 42) ; 42
(abs -13) ; 13
(max 1 5 3) ; 5
Пожалуйста, авторизуйтесь, это необходимо для отслеживания прогресса выполнения уроков. Если у вас ещё нет учётной записи, то сейчас самое время создать аккаунт.