Обработка списков на Erlang

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

Если по какому-либо вопросу Вам не хватило информации — пишите в комментариях или поищите по ссылкам, приведенным в конце статьи.

Задача 1: Реализуйте функцию antimap(ListF, X), которая принимает список функций одного аргумента ListF и значение X, и возвращает список результатов применения всех функций из ListF к X.

Пример: antimap([fun(X) -> X + 2 end, fun(X) -> X*3 end], 4). => [6, 12]

В примере, список функций содержит лямбда-функции (анонимные/безымянные функции). Описание такой функции начинается ключевым словом fun и завершается end. Обе функции списка принимают один аргумент, при этом первая возвращает значение аргумента увеличенное на 2, а вторая — умноженное на 3.

Очевидно, наша функция должна завершать работу в случае, если список функций пуст, при этом результатом ее работы должен являться пустой список (первая строка листинг 1). В противном случае (если список функций не пуст) необходимо вернуть список, головой (первым элементом) которого является результат применения первой функции списка к аргументу, а хвостом (остальная часть списка) — результат рекурсивной обработки остальных элементов списка функций (вторая строка листинг 1).

antimap([], _) -> []; %1
antimap([H|T], X) -> [H(X)|antimap(T, X)]. %2

рис. 1 пример использования функции antimap

рис. 1 пример использования функции antimap

Задача 2. Реализуйте функцию iterate(F, N), которая возвращает функцию, применяющую F к своему аргументу N раз (т.е.(iterate(F, 2))(X) == F(F(X)))

Примеры:

F3 = iterate(fun(X) -> X * 2 end, 5), F3(2). => 32
F2 = iterate(fun(X) -> {X} end, 3), F2(1). => {{{1}}}

В первом примере в F3 помещается функция, умножающая аргумент на 2 пять раз, во втором — помещающая аргумент в кортеж 3 раза.

Особенность задачи в том, что требуется вернуть функцию, а не применять ее сразу к аргументу. Кроме того, обратим внимание не то, что в случае отрицательного N поведение функции не определено — в этом случае мы будем бросать исключение.

iterate(_F, N) when N < 0 -> throw({iterate, N}); %1
iterate(F, 1) -> fun(X) -> F(X) end; %2
iterate(F, N) -> %3
fun(X) -> Fun = iterate(F, N - 1), F(Fun(X)) end. %4

В первой строке листинг 2 обрабатывается случай, когда N <= 0, для этого используются охраняющие выражения (ограничители, guards), задаваемые при помощи ключевого слова when.Ничего хитрого в ограничителях нет, в примере листинг 1 мы, также, могли бы их использовать для проверки исходного списка на пустоту, однако, для этого достаточно использовать механизм сравнения с шаблоном, который выглядит более элегантно.

Исключение в первой строке бросается при помощи конструкции throw, но кроме этого можно использовать exit. Не вдаваясь в детали, бросая исключение при помощи throw мы надеемся что оно будет обработано. В приведенном примере при обработке исключения (конструкция catch) будет получен кортеж {iterate, Number}. Если на место throw поставить ключевое слово exti — то был бы получен кортеж {EXIT, {iterate, Number}}, а в случае, если исключение не было бы обработано, завершился бы текущий процесс.

В случае, если функцию к аргументу требуется применить лишь один раз (вторая строка листинг 2) в качестве результата возвращается лямбда-функция, принимающая один аргумент, который передается в функцию F. Возвращается именно функция, а не результат ее работы.

В строках 3-4, также возвращается лямбда-функция, но на этот раз функция F применяется к результату, полученному от рекурсивного вызова iterate.

рис. 2 функция iterate

рис. 2 пример работы iterate

Задача 3. Реализуйте функцию group_by(Fun, List), которая разбивает список List на отрезки, на идущих подряд элементах которых Fun (предикат от двух переменных) возвращает true.
Пример: group_by(fun(X, Y) -> X =< Y end, [1,2,4,3,2,5]). => [[1,2,4], [3], [2,5]]

В приведенном примере, в качестве первого аргумента group_by получает лямбда-функцию, возвращающую false если первый ее аргумент больше второго и true — в остальных случаях.

Исходный код функции group_by приведен на листинг 3.

group_by(_F, []) -> []; %1
group_by(_F, [H]) -> [[H]]; %2
group_by(F, [H1, H2 | T]) -> %3
case F(H1, H2) of %4
true -> %5
[HR | TR] = group_by(F, [H2|T]), %6
[[H1 | HR] | TR]; %7
false -> [[H1] | group_by(F, [H2|T])] %8
end. %9

Очевидно,функция (первый аргумент) должна вызываться для соседних элементов списка (второй аргумент).

Если исходный список пуст — результат работы group_by — пустой список (первая строка листинг 3).

Если исходный список содержит единственный элемент — в результате работы функции должен быть сформирован список, содержащий одну группу из одного элемента (вторая строка листинг 3).

В противном случае (если в списке более 1 элемента), необходимо вычислить функцию F для первых двух элементов списка, от полученного результата будет зависеть дальнейшая работа group_by. Может быть, нам хотелось бы использовать при этом уже знакомые нам ограничители (охраняющие выражения),однако, они не могут содержать вызовов функций, без которых нам не обойтись, поэтому в листинг 3 используется оператор ветвления.

Ветвления Erlang может реализовываться посредством следующих конструкций:

if
<ограничитель_1> -> <выражение_1>;
<ограничитель_2> -> <выражение_1>;
%...
<ограничитель_N> -> <выражение_N>
end.

 

case <выражение> of
<шаблон_1> -> <выражение_1>;
<шаблон_2> -> <выражение_2>;
%...
<шаблон_N> -> <выражение_N>
end.

При выполнении конструкции if..end выполняется поиск ограничителя, который вернет true, а затем управление передается соответствующему выражению. Если ни один из ограничителей не вернул true — генерируется исключение.

В случае, если необходимо проверить истинность какого-либо выражения, удобнее использовать конструкцию case..of..end, при этом, сначала вычисляется выражение, а затем, результат вычисления последовательно сравнивается с шаблонами. Если какой-либо шаблон подошел — выполняется соответствующее ему выражение, в противном случае — генерируется исключение.

В нашей задаче удобнее использовать конструкцию case..of..end, т.к. необходимо проверять истинность выражения F(H1, H2)четвертая строка листинг 3, однако, мы могли бы использовать и конструкцию if..end.

Независимо от того, что вернет F(H1, H2), наша функция должна рекурсивно обработать хвост списка ([H2|T]). При обработке хвоста будет получен промежуточный результат, к которому определенным образом необходимо прибавить элемент H1.

Если F(H1, H2) вернула true — то H1 должен быть добавлен к первому элементу-списку промежуточного результата (строка 7), иначе — из H1 формируется новая группа (новый список), которая добавляется в начало промежуточного результата (строка 8).

рис. 3 пример работы group_by

рис. 3 пример работы group_by

Задача 4. Реализуйте функцию iteratemap(F, X0, N), которая возвращает список длины N, состоящий из результатов последовательного применения F к X0.

Пример: iteratemap(fun(X) -> X*2 end, 1, 4) => [2, 4, 8, 16]

iteratemap(_F, _Val, N) when N =< 0 -> throw({iteratemap, N}); %1
iteratemap(F, Val, 1) -> [F(Val)]; %2
iteratemap(F, Val, N) -> Tmp = F(Val), [Tmp | iteratemap(F, Tmp, N - 1)]. %3

Если N <= 0, поведение функции не определено, выбрасывается исключение, содержащее кортеж, первым элементом которого является название функции (строка 1 листинг 4), бросившей исключение — это позволяет удобно обрабатывать исключения.

Если N равно 1 (строка 2 листинг 4), возвращается список из одного элемента, полученного в результате применения функции к переданному значению (Val).

В противном случае, значение F(Val) сохраняется в переменной Tmp, которая помещается в начало списка-результата и передается в функцию iteratemap для рекурсивной обработки (строка 3).

рис. 4 пример работы iteratemap

рис. 4 пример работы iteratemap

Литература:

  1. http://www.erlang.org / зарубежный сайт, содержащий документацию и статьи по языку, OTP, а также, позволяющий скачать open-source реализации Erlang/OTP;
  2. Д. Васильев, Язык программирования Erlang / http://hlabs.org/development/erlang / учебник по языку Erlang для самых начинающих на русском языке;
  3. F. Hebert, Learn You Some Erlang for great good!, http://learnyousomeerlang.com / хорошая книга по Erlang на английском языке, размещенная в открытом доступе, однако, можно заказать бумажный вариант.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

*

code