Бесплатный курс по Racket. Зарегистрируйтесь для отслеживания прогресса →

Racket: Сворачивание списков, функции свёртки foldl и foldr

Функции map и filter обрабатывают списки, сохраняя саму структуру. Но иногда нужно избавиться от этой самой структуры, вычислив какое-то итоговое значение. Простейший пример — сумма всех чисел в списке. Или текст, собранный из списка строк.

В процедурных языках для получения итоговых значений по списку проходят с использованием цикла и промежуточный результат хранят в отдельной переменной — в так называемом аккумуляторе.

Декларативным же аналогом такого цикла будет операция сворачивания (folding) или, как ещё говорят, получение свёртки (fold). Суть сворачивания списка заключается в последовательном применении некоторой бинарной операции к очередному элементу списка и текущему значению аккумулятора у с целью получить новое значение аккумулятора. Давайте рассмотрим процесс сворачивания списка (list 1 2 3 4) в сумму чисел. Начальным значением аккумулятора будет 0, а операцией — +. Сложить числа можно как минимум двумя способами:

  1. Двигаясь от первого элемента к последнему, слева направо.
  (((0 + 1) + 2) + 3) + 4
  1. Двигаясь от последнего элемента к первому, справа налево.
  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
Упражнение не проходит проверку — что делать? 😶

Если вы зашли в тупик, то самое время задать вопрос в «Обсуждениях». Как правильно задать вопрос:

  • Обязательно приложите вывод тестов, без него практически невозможно понять что не так, даже если вы покажете свой код. Программисты плохо исполняют код в голове, но по полученной ошибке почти всегда понятно, куда смотреть.
В моей среде код работает, а здесь нет 🤨

Тесты устроены таким образом, что они проверяют решение разными способами и на разных данных. Часто решение работает с одними входными данными, но не работает с другими. Чтобы разобраться с этим моментом, изучите вкладку «Тесты» и внимательно посмотрите на вывод ошибок, в котором есть подсказки.

Мой код отличается от решения учителя 🤔

Это нормально 🙆, в программировании одну задачу можно выполнить множеством способов. Если ваш код прошел проверку, то он соответствует условиям задачи.

В редких случаях бывает, что решение подогнано под тесты, но это видно сразу.

Прочитал урок — ничего не понятно 🙄

Создавать обучающие материалы, понятные для всех без исключения, довольно сложно. Мы очень стараемся, но всегда есть что улучшать. Если вы встретили материал, который вам непонятен, опишите проблему в «Обсуждениях». Идеально, если вы сформулируете непонятные моменты в виде вопросов. Обычно нам нужно несколько дней для внесения правок.

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

Нашли ошибку? Есть что добавить? Пулреквесты приветствуются https://github.com/hexlet-basics
Если вы столкнулись с трудностями и не знаете, что делать, задайте вопрос в нашем большом и дружном сообществе