Elixir: Рекурсивные функции с аккумуляторами
Типичный способ работы со списками -- использование рекурсивных функций и аккумуляторов. Рассмотрим эту тему на примерах.
Пример 1
Допустим, у нас есть список пользователей:
users = [
{:user, 1, "Bob", 23},
{:user, 2, "Helen", 20},
{:user, 3, "Bill", 15},
{:user, 4, "Kate", 14}
]
Здесь каждый пользователь представлен кортежем из 4-х элементов:
- :user -- тэг для обозначения типа данных;
- id -- идентификатор пользователя;
- name -- имя пользователя;
- age -- и его возраст.
И мы хотим отфильтровать совершеннолетних пользователей. То есть, получить новый список, где будут только пользователи старше 16 лет.
Применим рекурсивную функцию с аккумулятором:
defmodule Solution do
def filter_adults(users), do: filter_adults(users, [])
defp filter_adults([], acc), do: Enum.reverse(acc)
defp filter_adults([user | users], acc) do
{:user, _, _, age} = user
if age > 16 do
filter_adults(users, [user | acc])
else
filter_adults(users, acc)
end
end
end
Solition.filter_adults(users)
# => [
# => {:user, 1, "Bob", 23},
# => {:user, 2, "Helen", 20}
# => ]
Функция получает на вход два аргумента: список пользователей, и ещё один список, где будет накапливаться результат выполнения -- аккумулятор. В начале выполнения список пользователей полный, а аккумулятор пустой. На каждом шаге итерации мы будем брать один элемент из первого списка, и, если он нам нужен, то класть его в аккумулятор. В итоге первый список опустошится, а аккумулятор наполнится.
Наша рекурсивная функция имеет два тела (clause). Первое тело выполняется, когда список пользователей пустой. То есть, это завершение фильтрации. И тут нужно просто отдать накопленный результат.
Второе тело и делает всю работу. Сперва список пользователей с помощью оператора cons делится на голову и хвост (это можно делать прямо в описании аргументов функции). Голова -- это текущий элемент списка, который мы будем анализировать. Хвост -- это остаток списка, который мы передадим дальше, в следующий рекурсивный вызов.
Анализ элемента тут простой: определяем возраст пользователя. Пользователей младше 16 лет мы игнорируем, а старше добавляем в аккумулятор, опять с помощью оператора cons.
Элементы в аккумуляторе накапливаются в обратном порядке. Если это не важно, то аккумулятор можно вернуть, как есть. Если желательно сохранить оригинальный порядок, то аккумулятор нужно развернуть.
Пример 2
Второй пример. Допустим, из списка пользователей нужно извлечь их идентификаторы и имена. То есть, получить список кортежей вида:
{id, name}
Реализация:
defmodule Solution do
def get_id_name(users), do: get_id_name(users, [])
defp get_id_name([], acc), do: Enum.reverse(acc)
defp get_id_name([user | users], acc) do
{:user, id, name, _} = user
get_id_name(users, [{id, name} | acc])
end
end
Solution.get_id_name(users)
# => [{1, "Bob"}, {2, "Helen"}, {3, "Bill"}, {4, "Kate"}]
Опять два тела у функции. Первое тело отвечает за завершение рекурсии и возврат результата, накопленного в аккумуляторе.
Второе тело обрабатывает каждый элемент списка, извлекает из кортежа нужные id
и name
, и сохраняет их в аккумуляторе.
Хорошая практика -- предлагать как публичный АПИ функцию с одним аргументом. А функцию с аккумулятором скрывать от пользователей модуля. Потому что аккумулятор может быть сложнее, чем просто список, и пользователям модуля незачем об этом знать.
Пример 3
И вот пример со сложным аккумулятором. Допустим нам нужно разделить пользователей на два списка: несовершеннолетние и взрослые.
defmodule Solution do
def split_teens_and_adults(users), do: split_teens_and_adults(users, {[], []})
defp split_teens_and_adults([], {teens, adults}) do
{Enum.reverse(teens), Enum.reverse(adults)}
end
defp split_teens_and_adults([user | users], {teens, adults}) do
{:user, _, _, age} = user
if age > 16 do
split_teens_and_adults(users, {teens, [user | adults]})
else
split_teens_and_adults(users, {[user | teens], adults})
end
end
end
Solution.split_teens_and_adults(users)
# => {[{:user, 3, "Bill", 15}, {:user, 4, "Kate", 14}],
# => [{:user, 1, "Bob", 23}, {:user, 2, "Helen", 20}]}
В этот раз наш аккумулятор -- это кортеж из двух списков. В первом теле функции, как обычно, возвращаем результат. И тут мы разворачиваем оба списка. Во втором теле функции обрабатываем каждый элемент списка, извлекаем и проверяем возраст. Тех, кто моложе 16 лет, кладем в первый список в аккумуляторе, остальных во второй список.
Задание
В функции filter_adults/1
критерием фильтрации является возраст пользователя. Но этот возраст явно указан в коде функции. Нужно реализовать функцию filter_by_age/2
, которая принимает список пользователей и возраст.
users = [
{:user, 1, "Bob", 23},
{:user, 2, "Helen", 20},
{:user, 3, "Bill", 15},
{:user, 4, "Kate", 14}
]
Solution.filter_by_age(users, 16) # [{:user, 1, "Bob", 23}, {:user, 2, "Helen", 20}]
Solution.filter_by_age(users, 14) # [{:user, 1, "Bob", 23}, {:user, 2, "Helen", 20}, {:user, 3, "Bill", 15}]
Solution.filter_by_age(users, 22) # [{:user, 1, "Bob", 23}]
Упражнение не проходит проверку — что делать? 😶
Если вы зашли в тупик, то самое время задать вопрос в «Обсуждениях». Как правильно задать вопрос:
- Обязательно приложите вывод тестов, без него практически невозможно понять что не так, даже если вы покажете свой код. Программисты плохо исполняют код в голове, но по полученной ошибке почти всегда понятно, куда смотреть.
В моей среде код работает, а здесь нет 🤨
Тесты устроены таким образом, что они проверяют решение разными способами и на разных данных. Часто решение работает с одними входными данными, но не работает с другими. Чтобы разобраться с этим моментом, изучите вкладку «Тесты» и внимательно посмотрите на вывод ошибок, в котором есть подсказки.
Мой код отличается от решения учителя 🤔
Это нормально 🙆, в программировании одну задачу можно выполнить множеством способов. Если ваш код прошел проверку, то он соответствует условиям задачи.
В редких случаях бывает, что решение подогнано под тесты, но это видно сразу.
Прочитал урок — ничего не понятно 🙄
Создавать обучающие материалы, понятные для всех без исключения, довольно сложно. Мы очень стараемся, но всегда есть что улучшать. Если вы встретили материал, который вам непонятен, опишите проблему в «Обсуждениях». Идеально, если вы сформулируете непонятные моменты в виде вопросов. Обычно нам нужно несколько дней для внесения правок.
Кстати, вы тоже можете участвовать в улучшении курсов: внизу есть ссылка на исходный код уроков, который можно править прямо из браузера.