Elixir: Рекурсивные функции с аккумуляторами

• Пример 1
• Пример 2
• Пример 3

Типичный способ работы со списками -- использование рекурсивных функций и аккумуляторов. Рассмотрим эту тему на примерах.

Пример 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}]

Полезное

• Статья в Hexlet про рекурсию