Эрланг на практике. Функции высшего порядка. Свертка. Конструкторы списков. — Эрланг на практике

Видео может быть заблокировано из-за расширений браузера. В статье вы найдете решение этой проблемы.

Функции высшего порядка
Свертка
Конструкторы списков

Функции высшего порядка

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

Функции высшего порядка (higher-order functions) -- звучит круто, но ничего особо хитрого здесь нет. Это всего лишь функции, которые принимают в аргументах другие функции, или возвращают другие функции. В упражнении ко второму уроку вы уже реализовали несколько таких.

lists:all/2, lists:any/2, lists:filter/2, lists:dropwhile/2 и т.д. -- все они принимают первым аргументом предикат, который является функцией.

В модуле lists много функций высшего порядка. И самые ходовые из них, это lists:map/2 и lists:filter/2.

map применяет переданную функцию к каждому элементу списка и возвращает новый список.

1> List = [1,2,3,4,5].
[1,2,3,4,5]
2> F = fun(Val) -> Val * 2 end.
 #Fun<erl_eval.6.90072148>
3> lists:map(F, List).
[2,4,6,8,10]

4> List2 = [{user, 1, "Bob"}, {user, 2, "Bill"}, {user, 3, "Helen"}].
[{user,1,"Bob"},{user,2,"Bill"},{user,3,"Helen"}]
5> F2 = fun({user, Id, Name}) -> {user, Id, string:to_upper(Name)} end.
 #Fun<erl_eval.6.90072148>
6> lists:map(F2, List2).
[{user,1,"BOB"},{user,2,"BILL"},{user,3,"HELEN"}]

filter использует переданную функцию как предикат для фильтрации списка.

7> lists:filter(fun(Val) -> Val > 3 end, List).
[4,5]
8> lists:filter(fun({user, Id, _}) -> Id rem 2 =:= 0 end, List2).
[{user,2,"Bill"}]

Мы можем взять примеры из прошлого урока, и переписать их с использованием map и filter.

Вспомним список пользователей, с которым мы работали:

get_users() ->
    [{user, 1, "Bob", male, 22},
     {user, 2, "Helen", female, 14},
     {user, 3, "Bill", male, 11},
     {user, 4, "Kate", female, 18}].

Фильтрация пользователей по полу:

get_females(Users) ->
    F = fun({user, _, _, male, _}) -> false;
           ({user, _, _, female, _}) -> true
        end,
    lists:filter(F, Users).

Получение id и name пользователя:

get_id_name(Users) ->
    F = fun({user, Id, Name, _, _}) -> {Id, Name} end,
    lists:map(F, Users).

Если нам нужно сделать и map, и filter, то мы можем применить их по очереди:

get_females_id_name(Users) ->
    Users2 = lists:filter(fun({user, _, _, Gender, _}) -> Gender =:= female end, Users),
    lists:map(fun({user, Id, Name, _, _}) -> {Id, Name} end, Users2).

Но так мы получим 2 прохода по списку. Можно сделать это в один проход, если воспользоваться функцией lists:filtermap/2.

get_females_id_name2(Users) ->
    lists:filtermap(fun({user, _, _, male, _}) -> false;
                       ({user, Id, Name, female, _}) -> {true, {Id, Name}}
                    end, Users).

Есть много примеров, где функция передается аргументом в другую функцию. Но довольно редко бывает, чтобы функция возвращалась как значение. Учебные примеры в книгах вы найдете. А что насчет применения на практике, в реальной работе? Кое что есть :)

В EUnit, фреймворке для модульного тестирования, используются генераторы юнит тестов. Они возвращают список функций.

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

Примеров мало, и это не повседневная практика, а какие-то особые случаи.

Еще с помощью функций, возвращающих функции, можно реализовать ленивые вычисления. Кому интересно, почитайте об этом в 9-й главе книги Чезарини.

Свертка

Еще одна важная штука в функциональном программировании. Ее понять немного сложнее, чем map и filter. Ну давайте разберемся.

Map принимает список, и возвращает список. Свертка принимает список, и возвращает одно значение -- "сворачивает" список.

lists:foldl принимает 3 аргумента:

функцию сворачивания
начальное значение аккумулятора
список

Функция сворачивания принимает 2 аргумента: текущий элемент списка и текущее значение аккумулятора. И должна вернуть новое значение аккумулятора.

Классический пример -- суммирование и произведение элементов списка:

1> List = [1,2,3,4,5].
[1,2,3,4,5]
2> lists:foldl(fun(Item, Acc) -> Acc + Item end, 0, List).
15
3> lists:foldl(fun(Item, Acc) -> Acc * Item end, 1, List).
120

Для суммирования начальное значение аккумулятора 0, и потом к нему прибавляется каждый элемент списка. Для произведения начальное значение аккумулятора 1, и потом на него умножается каждый элемент списка.

Но это учебные примеры, они не интересные :) Давайте сделаем что-нибудь интересное с нашим списком пользователей:

get_users() ->
    [{user, 1, "Bob", male, 22},
     {user, 2, "Helen", female, 14},
     {user, 3, "Bill", male, 11},
     {user, 4, "Kate", female, 18}].

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

В качестве аккумулятора возьмем кортеж из 4х чисел:

{Males, Females, TotalUsers, TotalAge}

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

Реализуем:

get_stat(Users) ->
    F = fun({user, _, _, Gender, Age}, {Males, Females, TotalUsers, TotalAge}) ->
                case Gender of
                    male -> {Males + 1, Females, TotalUsers + 1, TotalAge + Age};
                    female -> {Males, Females + 1, TotalUsers + 1, TotalAge + Age}
                end
        end,
    lists:foldl(F, {0, 0, 0, 0}, Users).

Как видим, тут главное написать сворачивающую функцию, которая пойдет первым аргументом в lists:foldl, и правильно задать начальное значение аккумулятора.

Пробуем применить:

1> Users = main:get_users().
[{user,1,"Bob",male,22},
 {user,2,"Helen",female,14},
 {user,3,"Bill",male,11},
 {user,4,"Kate",female,18}]
2> {M, F, TU, TA} = main:get_stat(Users).
{2,2,4,65}

Средний возраст сразу не получим, но получим данные, чтобы его рассчитать.

3> TA / TU.
16.25

На прошлом уроке мы изучали рекурсивные функции с аккумуляторами. Полезно знать, что все, что можно реализовать таким образом, можно реализовать и через свертку.

Например, мы делили список пользователей по возрасту на два списка: тех, кому меньше 18, и взрослых:

split_by_age(Users) -> split_by_age(Users, {[], []}).

split_by_age([], {Acc1, Acc2}) -> {lists:reverse(Acc1), lists:reverse(Acc2)};

split_by_age([User | Rest], {Acc1, Acc2}) ->
    {user, _, _, _, Age} = User,
    if
        Age < 18 -> split_by_age(Rest, {[User | Acc1], Acc2});
        true -> split_by_age(Rest, {Acc1, [User | Acc2]})
    end.

Вот как можно сделать то же самое через свертку:

split_by_age(Users) ->
    lists:foldl(fun(User, {Acc1, Acc2}) ->
                        {user, _, _, _, Age} = User,
                        if
                            Age < 18 -> {[User | Acc1], Acc2};
                            true -> {Acc1, [User | Acc2]}
                        end
                end,
                {[], []},
                Users).

Этот пример может показаться менее понятным, чем предыдущий. Но это дело привычки. Между тем, рекомендуется применять именно свертку вместо кастомных рекурсивных функций. Выше уровень абстракции, значит меньше кода. Меньше кода, значит меньше возможностей допустить ошибку.

Теперь понятно, почему на прошлом уроке мы сделали один составной аккумулятор, вместо 2-х простых. Это было для того, чтобы перейти к свертке :)

Свертка бывает левая и правая: lists:foldl/3, lists:foldr/3. Левая начинает от головы списка и идет к хвосту. Правая начинает от хвоста и идет к голове. Они могут отличаться результатом, а могут не отличаться, смотря как реализована сворачивающая функция. Но важно знать, что левая свертка реализована с хвостовой рекурсией, а правая с обычной рекурсией, с ростом стека и возвратом назад по стеку.

Конструкторы списков

Конструкторы списков (lists comprehention) -- еще один высокоуровневый способ работы со списками.

Синтаксис напрямую заимствуется из математики. Например, математическое выражение:

{x | x ∈ N, x > 0}

означает: из множества натуральных чисел (N), взять каждый элемент (x), больший нуля.

Соответствующее ему выражение в эрланг:

1> List = [-2,-1,0,1,2].
[-2,-1,0,1,2]
2> [X || X <- List, X > 0].
[1,2]

Из списка List взять каждый элемент, больший нуля.

Конструкторы списков делают то же, что map и filter. filter мы уже увидели, а вот map:

3> [X * 2 || X <- List].
[-4,-2,0,2,4]

Конечно, можно объединять и то, и другое в одном проходе:

4> [X * 2 || X <- List, X > 0].
[2,4]

Но в отличие от функций lists:map/2, lists:filter/2, они могут работать с несколькими списками одновременно:

5> List1 = [1,2].
[1,2]
6> List2 = [a,b].
[a,b]
7> List3 = [cc,dd].
[cc,dd]
8> [{X,Y,Z} || X <- List1, Y <- List2, Z <- List3].
[{1,a,cc},
 {1,a,dd},
 {1,b,cc},
 {1,b,dd},
 {2,a,cc},
 {2,a,dd},
 {2,b,cc},
 {2,b,dd}]

Как видно, элементы списков соединяются "каждый с каждым".

Ну и, конечно, все эти списки можно фильтровать:

9> [{X,Y,Z} || X <- List1, X > 1, Y <- List2, Y =/= a, Z <- List3].
[{2,b,cc},{2,b,dd}]

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

1> List = [{rect, 5, 10}, {rect, 4, 8}, {rect, 4, 3}].
[{rect,5,10},{rect,4,8},{rect,4,3}]
2> [{area, W * H} || {rect, W, H} <- List].
[{area,50},{area,32},{area,12}]

И фильтровать можно по внутренним значениям и по производным от них выражениям:

3> [{area, W * H} || {rect, W, H} <- List, W * H < 40].
[{area,32},{area,12}]

Давайте опять вернемся к нашему списку пользователей:

get_users() ->
    [{user, 1, "Bob", male, 22},
     {user, 2, "Helen", female, 14},
     {user, 3, "Bill", male, 11},
     {user, 4, "Kate", female, 18}].

Отфильтруем по полу с помощью конструкторов списков:

[User || {user, _, _, Gender, _} = User <- Users, Gender =:= female].

И извлечем {Id, Name} так же:

[{Id, Name} || {user, Id, Name, _, _} <- Users].

Ну и напоследок красивый пример из книги Джо Армстронга с пифагоровыми тройками. Вспомним теорему Пифагора: сумма квадратов катетов равна квадрату гипотенузы. Существует не так много вариантов, когда длины катетов и гипотенузы выражаются целыми числами. Самый известный такой вариант: {3, 4, 5}.

Армстронг предлагает найти все такие варианты с помощью конструкторов списков. На входе дана максимальная длина гипотенузы, на выходе нужно получить список всех возможных троек {Катет, Катет, Гипотенуза}, где длины являются целыми числами.

Берем список всех возможных длин:

1> Max = 20.
20
2> Lengthes = lists:seq(1, Max).
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20]

И генерируем все возможные сочетания длин:

3> [{X,Y,Z} || X <- Lengthes, Y <- Lengthes, Z <- Lengthes].
[{1,1,1},
 {1,1,2},
 {1,1,3},
 ...

Промежуточный результат получится очень большой, но это не важно. Дальше его нужно отфильтровать.

4> [{X,Y,Z} || X <- Lengthes, Y <- Lengthes, Z <- Lengthes, X * X + Y * Y =:= Z * Z].
[{3,4,5},
 {4,3,5},
 {5,12,13},
 {6,8,10},
 {8,6,10},
 {8,15,17},
 {9,12,15},
 {12,5,13},
 {12,9,15},
 {12,16,20},
 {15,8,17},
 {16,12,20}]