Учимся думать и писать на Erlang (на примере двух комбинаторных задач)

— … Тут я даю ему по морд… Нет, бить нельзя!
— В том-то и дело, что бить нельзя, — лицемерно вздохнул Паниковский. — Бендер не позволяет.
И.Ильф, Е.Петров. Золотой теленок.

Мозголомная Брага жила в прозрачном сосуде и была такая
крепкая, что даже ужас. Она не то что из живота — прямо изо рта
бросилась в голову и стала кидаться там из стороны в сторону,
ломая умственные подпорки и укрепы.
М.Успенский. Там, где нас нет.

Пожалуй каждый, кто впервые приступает к изучению Erlang, ощущает себя в положении Шуры Балаганова, которому запрещено было применение единственного доступного и понятного метода: «бить нельзя…». В Erlang отсутствуют такие привычные для большинства современных языков понятия, как повторное присвоение переменной и, соответственно, накопление результата в одной переменной. (Справедливости ради следует отметить, что поведение типа «глобальная многократно меняющаяся переменная» в Erlang все же можно реализовать. Для этого в каждом процессе имеется словарь хешей, хранящий определяемые программистом пары ключ — значение. Имеются встроенные функции put(Key, Value), get(Key) и еще несколько вспомогательных функций. Но использование такого словаря в приложениях считается плохим стилем и рекомендуется только в исключительных случаях (http://www.erlang.org/doc/man/erlang.html\#put-2)). Как следствие, итерации в цикле невозможно реализовать с помощью привычного наращивания значений итерационной переменной. Накопление результата осуществляется только через рекурсию, а организация циклов — через хвостовую рекурсию. (Конечно, и итерации, и накопление результата в цикле можно реализовать через библиотечные функции для списков lists:foreach(Function, List), lists:foldl(Function, StartValue, List), lists:foldr(Function, StartValue, List) (http://www.erlang.org/doc/man/lists.html) и их аналоги для наборов (http://www.erlang.org/doc/man/sets.html, http://www.erlang.org/doc/man/ordsets.html, http://www.erlang.org/doc/man/gb_sets.html) и массивов (http://www.erlang.org/doc/man/array.html). Но наша цель — научиться писать циклы, а не использовать готовые решения, поэтому здесь мы воздержимся от употребления подобных библиотек).

Таким образом, в Erlang приходится ломать привычные шаблоны мышления и заменять их новыми паттернами, характерными только для этого языка программирования. Конечно, идеальное средство — мозголомная брага, способная ломать все «умственные подпорки и укрепы». Но для нас это, пожалуй, слишком радикальное средство, и мы пойдем другим путем.

В житии святого Антония Великого есть рассказ об одном из его учеников. Ученик стоял в храме и слушал, как святой Антоний читал Псалтырь. Как только прозвучал первый стих первого псалма:
Блажен муж, который не ходит на совет нечестивых...
ученик вышел из храма. С тех пор его никто не видел почти 30 лет, а когда он вновь появился в храме, Антоний Великий спросил, почему он оставил их так надолго и куда исчез. Ученик ответил: «отче, я услышал слова псалма, и удалился в пустыню, чтобы постараться выполнить то, о чем говорится в этих словах, т.е. не ходить на совет нечестивых мыслей». Другими словами, он усвоил практический урок этих слов, и теперь пришел чтобы читать дальше. К сожалению, у нас нет такого резерва времени, да и цели наши не столь возвышенны. Но основной концепт можно перенять.
Мы рассмотрим две стандартные комбинаторные задачи:

1. поиск всех возможных перестановок (permutations) из данного множества по N элементов
2. поиск всех возможных сочетаний (combinations) из данного множества по N элементов

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

Все примеры собраны в модуле combinat.erl и доступны по адресу: https://github.com/raven29/combinat_erl.git

Две цели — две рекурсии

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

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

Другими словами, процедура заключает в себе два этапа: циклический перебор на данном уровне рекурсии и переход на следующий уровень. Соответственно, эти две цели требуют двойного рекурсивного вызова. (Алгоритм основан на наивном переборе и, соответственно, требует оптимизации. Однако он вполне подходит для наших целей, потому что, во-первых, в силу простоты и наглядности позволяет легко иллюстрировать используемые методы и приемы, во-вторых, применяется к обеим рассматриваемым задачам с минимальными различиями, что дает возможность проводить соответствующие сравнения и параллели).

Базовая реализация

Базовый функционал реализован в функциях combinat:permuts_out(List, Number) и combinat:combs_out(List, Number), которые выводят на печать соответственно все перестановки и все сочетания длиной Number из элементов списка List. Ниже приводится функция permuts_out(List, Number), выводящая на печать перестановки. Эта функция дважды вызывается рекурсивно: в 6 строке — для циклического перебора, в 7 строке — для перехода на следующий уровень рекурсии. Именно в этом последнем вызове происходит наращивание результата в переменной [RemainH|Result], а также исключение элементов, содержащихся в этом результате, из общего списка, передаваемого на следующий уровень рекурсии. В четвертом аргументе List хранится исходный список элементов, который требуется для корректного вычисления остатка только в случае перестановок.

permuts_out(List, Number) -> permuts_out(List, [], Number, List). permuts_out(_Remain, Result, Number, _List) when length(Result) == Number ->     io:format("~w~n", [Result]); permuts_out([], _Result, _Number, _List) -> ok; permuts_out([RemainH|RemainT], Result, Number, List) ->     permuts_out(RemainT, Result, Number, List),     permuts_out(List -- [RemainH|Result], [RemainH|Result], Number, List). 

Аналогичная функция для сочетаний отличается от предыдущей функции лишь более простым правилом вычисления передаваемого остатка и отсутствием четвертого аргумента List.

combs_out(List, Number) -> combs_out(List, [], Number). combs_out(_Remain, Result, Number) when length(Result) == Number ->     io:format("~w~n", [Result]); combs_out([], _Result, _Number) -> ok; combs_out([RemainH|RemainT], Result, Number) ->     combs_out(RemainT, Result, Number),     combs_out(RemainT, [RemainH|Result], Number). 

Две рекурсии — две функции

Для большей наглядности два рекурсивных вызова можно представить двумя разными функциями. Окончания в названиях функций соответствуют их назначениям: *_iteration — для итераций по списку остатка на данном уровне рекурсии, *_recursion — для перехода на следующий уровень рекурсии.

permuts_out_2(List, Number) -> permuts_out_iteration(List, [], Number, List). permuts_out_iteration([], _Result, _Number, _List) -> ok; permuts_out_iteration([RemainH|RemainT], Result, Number, List) ->     permuts_out_iteration(RemainT, Result, Number, List),     permuts_out_recursion(List -- [RemainH|Result], [RemainH|Result], Number, List). permuts_out_recursion(_Remain, Result, Number, _List) when length(Result) == Number ->     io:format("~w~n", [Result]); permuts_out_recursion(Remain, Result, Number, List) ->     permuts_out_iteration(Remain, Result, Number, List).  combs_out_2(List, Number) -> combs_out_iteration(List, [], Number, List). combs_out_iteration([], _Result, _Number, _List) -> ok; combs_out_iteration([RemainH|RemainT], Result, Number, List) ->     combs_out_iteration(RemainT, Result, Number, List),     combs_out_recursion(RemainT, [RemainH|Result], Number, List). combs_out_recursion(_Remain, Result, Number, _List) when length(Result) == Number ->     io:format("~w~n", [Result]); combs_out_recursion(Remain, Result, Number, List) ->     combs_out_iteration(Remain, Result, Number, List).  

Пожалуй, этот вариант можно считать антипаттерном, ввиду излишней громоздкости.

Предъявите результат!

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

1. возврат значений в восходящей рекурсии
2. функция обратного вызова (callback)
3. поток-исполнитель и поток-накопитель

Рассмотрим каждый вариант подробно.

Медведь туда — медведь обратно

До сих пор мы делали что-то полезное (если вывод результата на экран компьютера можно считать полезным делом) в теле функции, спускаясь вглубь по нисходящей рекурсии. При обратном движении результат, возвращаемый функцией, никак не использовался. Другими словами, восходящее движение по рекурсии шло «порожняком». При таком подходе невозможно собрать воедино все выводимые значения, т.к. они никак не связаны между собой. Более продуктивным является использование результата, возвращаемого функцией при выходе из рекурсии. В этом случае первый вызов рекурсивной функции может вернуть весь совокупный результат. Модификация базовых функций приведена ниже и включает три момента:

1. возвращение результата [Result] вместо вывода в стандартный поток (строка 3, 11)
2. на «дне» рекурсии возвращается начальное значение — пустой список [ ] вместо атома «ok» (строка 4, 12)
3. накопление результата с помощью суммирования списков "++" вместо последовательного вызова (строка 6, 14)

Функции permuts_res(List, Number) и combs_res(List, Number) возвращают список списков, содержащий соответственно все перестановки и сочетания длиной Number.

permuts_res(List, Number) -> permuts_res(List, [], Number, List). permuts_res(_Remain, Result, Number, _List) when length(Result) == Number ->     [Result]; permuts_res([], _Result, _Number, _List) -> []; permuts_res([RemainH|RemainT], Result, Number, List) ->     permuts_res(RemainT, Result, Number, List) ++     permuts_res(List -- [RemainH|Result], [RemainH|Result], Number, List).  combs_res(List, Number) -> combs_res(List, [], Number). combs_res(_Remain, Result, Number) when length(Result) == Number ->     [Result]; combs_res([], _Result, _Number) -> []; combs_res([RemainH|RemainT], Result, Number) ->     combs_res(RemainT, Result, Number) ++     combs_res(RemainT, [RemainH|Result], Number).  

И делай с ним что хошь!

Иногда бывает удобно не накапливать результат в одной переменной-коллекции, а делать что-нибудь полезное с каждым элементом сразу после его создания. Такой подход позволяет увеличить производительность и значительно уменьшить потребление оперативной памяти. Реализовать можно с помощью функции обратного вызова (callback), которая передается в качестве дополнительного аргумента. Соответствующие варианты приведены ниже.

permuts_clb(List, Number, Callback) -> permuts_clb(List, [], Number, List, Callback). permuts_clb(_Remain, Result, Number, _List, Callback) when length(Result) == Number ->     Callback(Result); permuts_clb([], _Result, _Number, _List, _Callback) -> ok; permuts_clb([RemainH|RemainT], Result, Number, List, Callback) ->     permuts_clb(RemainT, Result, Number, List, Callback),     permuts_clb(List -- [RemainH|Result], [RemainH|Result], Number, List, Callback).  combs_clb(List, Number, Callback) -> combs_clb(List, [], Number, Callback). combs_clb(_Remain, Result, Number, Callback) when length(Result) == Number ->     Callback(Result); combs_clb([], _Result, _Number, _Callback) -> ok; combs_clb([RemainH|RemainT], Result, Number, Callback) ->     combs_clb(RemainT, Result, Number, Callback),     combs_clb(RemainT, [RemainH|Result], Number, Callback).  

В переменной Callback может быть передано имя любой функции от одного аргумента (с арностью единица — согласно терминологии Erlang). Так, например, можно вызвать вывод на печать всех перестановок из элементов [1,2,3] по 2:

combinat:permuts_clb([1,2,3], 2, fun(X)->io:format("~w~n",[X]) end). 

Более содержательное применение функции обратного вызова рассматривается в следующем разделе.

Big Brother is watching you

Другой способ реализовать накопление результата ветвящейся рекурсии в Erlang — использовать два потока. Один поток — исполнитель, в нем запускается наша программа. Другой поток — наблюдатель, в него рекурсивная функция передает полученные результаты. Когда поток-исполнитель завершает свою работу, поток-наблюдатель выводит суммарный результат. Важно: в качестве потока-исполнителя нельзя использовать основной поток (supervisor), в котором запущена оболочка erl, т.к. этот поток не уничтожается после выполнения программы. Он продолжает существовать до выгрузки приложения erl.

Ниже приведена соответствующая реализация. В строке 3 устанавливается «выход по трапу», что обеспечивает передачу сообщения от связанного процесса даже в случае его нормального завершения. По умолчанию, флаг trap_exit установлен в false, что означает получение сообщения от связанного процесса только в случае аварийного завершения. В строке 5 запускается (и одновременно связывается) поток-исполнитель. В этом потоке запускается функция permuts_clb (или combs_clb), которой передаются аргументы List, Number, а также функция обратного вызова Callback, которая передает каждый единичный результат в процесс-наблюдатель:

fun(R)->Supervisor!R end 

В строке 6 запускается функция loop([]) с пустым начальным значением суммарного результата. Эта функция «слушает» сообщения от потока-исполнителя. При получении очередного результата происходит рекурсивный вызов loop(Total ++ [Result]) (строка 14) с аргументом, дополненным вновь пришедшим результатом из потока-исполнителя. По завершении работы потока-исполнителя происходит «выход по трапу»: в loop() передается кортеж специального вида (строка 10), по которому в результате патерн-матчинга выводится общий результат (строка 11) и разрывается связь с потоком-исполнителем (строка 12). Supervisor — pid потока-наблюдателя, Worker — pid потока-исполнителя.

%% Function = permuts_clb | combs_clb proc(Function, List, Number) ->     process_flag(trap_exit, true),     Supervisor = self(),     spawn_link(combinat, Function, [List, Number, fun(R)->Supervisor!R end]),     loop([]).  loop(Total) ->     receive     {'EXIT', Worker, normal} ->         io:format("~w~n", [Total]),         unlink(Worker);     Result ->         loop(Total ++ [Result])     end.  

Функция вызывается с permuts_clb или combs_clb в качестве первого аргумента, в зависимости от решаемой задачи. Например, вывод на печать всех перестановок из элементов [1,2,3] по 2 осуществляется через вызов:

combinat:proc(permuts_clb, [1,2,3], 2). 

Отметим два неочевидных обстоятельства. Во-первых, нельзя запустить loop() перед spawn_link(). Казалось бы, так будет более надежно, т.к. функция-слушатель, запущенная до запуска потока-исполнителя, наверняка не пропустит ни одного сообщения от этого потока. Но опыт показывает, что в этом случае функция-слушатель вообще не получает сообщения от потока-исполнителя. По-видимому, это связано с тем, что статус отношения потоков не обновляется. Во-вторых, использование переменной Supervisor для передачи сообщения в поток-наблюдатель обязательно: конструкция

self()!R 

не работает.

И еще одно небольшое замечание: при экспериментах с функцией proc() могут случаться разные странности, например функция может начать выдавать результат с «запаздыванием», т.е. при каждом вызове выдавать результат предыдущего вызова. Это может происходить от того, что мы запускаем в качестве потока-наблюдателя главный поток. Поэтому после какого-либо сбоя следующий вызов loop() в первую очередь обработает все сообщения от прошлого вызова, если таковые оставались. В этом смысле более надежной будет реализация потока-слушателя также в отдельном потоке, порождаемом функцией spawn() или spawn_link().

Понять — значит включить

В некоторых языках программирования имеется синтаксическая конструкция, называемая "list comprehension". Она позволяет в компактной и изящной форме задать итерационный обход списка, в результате которого генерируется новый список, каждый элемент которого получен из исходного списка применением некоторой функции к каждому элементу исходного списка. Конструкция основана на системе обозначений математической теории множеств. Вот так, например, выглядит в конструкции list comprehension вывод квадратов всех целых чисел от 1 до 9:

[X*X || X <- [1,2,3,4,5,6,7,8,9]]. 

В list comprehension возможна также передача нескольких списков и наложение условий. В качестве примера рассмотрим вывод таблицы умножения от 1 до 9:

[io:format("~w * ~w = ~w~n", [I, J, I*J]) ||      I <- [1,2,3,4,5,6,7,8,9], J <- [1,2,3,4,5,6,7,8,9]]. 

а также таблицы умножения, в которой исключены повторные результаты с перестановкой сомножителей:

[io:format("~w * ~w = ~w~n", [I, J, I*J]) ||      I <- [1,2,3,4,5,6,7,8,9], J <- [1,2,3,4,5,6,7,8,9], I < J]. 

В русскоязычной литературе «list comprehension» переводится как «включение списков», «генерация списков». Основное значение перевода «comprehension» — «постичь», «понять». Так что, в английском языке понять — значит включить.

Следует отметить, что конструкция comprehension существует не только для списков, но и для коллекций других типов. В Erlang имеется list comprehension и binary comprehension.

Самая изящная в своем роде

В конструкции list comprehension можно задать итерационный обход по списку, в результате базовая функция приобретет вид:

permuts_comp(List, Number) -> permuts_comp(List, [], Number). permuts_comp(_Remain, Result, Number) when length(Result) == Number ->     io:format("~w~n", [Result]); permuts_comp(Remain, Result, Number) ->     [permuts_comp(Remain -- [R], [R] ++ Result, Number) || R <- Remain]. 

Функция permuts_comp вызывает себя рекурсивно из list comprehension.
Это, пожалуй, самая изящная функция перестановок из всех возможных.

Если нельзя, но очень хочется…

Обобщение предыдущего результата на функцию сочетаний, к сожалению, не столь очевидно. Дело в том, что в list comprehension в данном случае нужно передавать не весь список, а лишь остаток, определяемый номером из предыдущего вызова. Если бы вместо списков был массив — можно было бы без труда вычислить нужный индекс. Но массивов нет в базовых типах Erlang. Нужно либо использовать библиотеку array, либо организовать массив «вручную».
Это оказывается довольно просто, и соответствующая реализация представлена ниже. Из исходного списка List строим список кортежей ListIndexed, каждый элемент которого содержит элементы исходного списка и целочисленный индекс (строка 2). Для такого преобразования подойдет функция lists:zip(List1, List2) из стандартного модуля lists. При выводе результата используем функцию lists:unzip(ListIndexed), возвращающую индексированному списку исходный вид без индексов (строка 5). И самое главное — в list comprehension теперь можно легко указать требуемое ограничение на индексы, включаемые в итерации (строка 11).

combs_comp(List, Number) ->     ListIndexed = lists:zip(List, lists:seq(1, length(List))),     combs_comp(ListIndexed, [], Number). combs_comp(_Remain, Result, Number) when length(Result) == Number ->     {ResultValue, _I} = lists:unzip(Result),     io:format("~w~n", [ResultValue]); combs_comp(Remain, [], Number) ->     [combs_comp(Remain -- [R], [R], Number) || R <- Remain]; combs_comp(Remain, [{HValue,HIndex}|T], Number) ->     [combs_comp(Remain -- [{R,I}], [{R,I}] ++ [{HValue,HIndex}|T], Number) ||     {R,I} <- Remain, I > HIndex]. 

Выглядит несколько неуклюже, и это — единственная программа среди наших примеров, в которой пришлось прибегнуть к библиотечным функциям lists:zip(List1, List2), lists:unzip(ListTuple), lists:seq(StartValue, Length). Эту попытку также можно считать образчиком антипаттерна, т.к. для поставленной задачи было бы более последовательно воспользоваться модулем array, но это уже будет другая история…