Elixir: Неизменяемые структуры данных

Эликсир, как и большинство других функциональных языков, основан на иммутабельности данных.

Польза иммутабельности:

• исключает ошибки, связанные с модификацией одной области памяти из разных мест в коде;
• в том числе из разных потоков, что существенно упрощает многопоточное программирование;
• упрощает сборку мусора;
• сохраняются все промежуточные версии данных, что упрощает отладку;
• компилятор имеет больше возможностей для оптимизации кода.

Плата за это -- несколько менее эффективные структуры данных, чем в императивных языках. Можно говорить, что в среднем производительность мутабельных и иммутабельных структур данных сопоставимая, но в крайних случаях производительность хуже, иногда существенно хуже.

Как это работает

Допустим, мы создали некую структуру данных, сохранили ее в некой области памяти, и присвоили как значение некой переменной. При этом в переменной сохраняется ссылка на эту область памяти.

Я могу передавать переменную в функцию. Значение передается по ссылке, а не копируется. Но функция не может изменить это значение. Так что передача по ссылке безопасна.

Эликсир гарантирует, что выделенная память не модифицируется. Но переменную, которая указывает на эту область памяти, можно изменить. То есть, указать на другую область памяти.

Для примера рассмотрим код:

my_list = [1, 2, 3]
# => [1, 2, 3]
my_list = my_list ++ [4, 5]
# => [1, 2, 3, 4, 5]
my_list = my_list ++ [6, 7, 8]
# => [1, 2, 3, 4, 5, 4, 5, 6, 7, 8]

Здесь мы имеем 3 списка, каждый из них размещен в своей области памяти. И здесь только одна переменная, которая сперва указывает на первый список, затем на второй, затем на третий.

Переиспользование памяти (Structure Sharing)

Любые данные нужно как-то модифицировать, иммутабельные данные не исключение. Если каждый раз при модификации мы будем создавать полную копию данных, то это будет очень не эффективно и по использованию памяти, и по использованию CPU.

Поэтому полного копирования не происходит. Вместо этого, при создании новой структуры данных BEAM переиспользует часть или всю старую структура. Иммутабельность позволяет это делать.

В примере выше, 3 списка совместно используют одну и ту же область памяти. А новая память выделяется только под новые элементы. Аналогично работает и Map.

my_map = %{a: 42}
# => %{a: 42}
other_map = Map.put(my_map, :b, 500)
# => %{a: 42, b: 500}
yet_another_map = Map.put(my_map, :c, 100500)
# => %{a: 42, c: 100500}

my_map
# => %{a: 42}
other_map
# => %{a: 42, b: 500}
yet_another_map
# => %{a: 42, c: 100500}

Задание

Реализуем шифр Цезаря -- простой способ шифрования путем сдвига каждого символа на константу.

Нужно реализовать функцию encode/2, которая принимает набор символов (charlists) и сдвиг, и возвращает зашифрованный набор символов (charlists).

Solution.encode('Hello', 10)
# => 'Rovvy'
Solution.encode('Hello', 5)
# => 'Mjqqt'

Также нужно реализовать функцию decode/2, которая принимает зашифрованную набор символов (charlists) и сдвиг, и возвращает оригинальный набор символов (charlists).

Solution.decode('Rovvy', 10)
# => 'Hello'
Solution.decode('Mjqqt', 5)
# => 'Hello'