Эта статья является переводом заметки под названием «D Functional Garden», которая расположена здесь и представляет собой небольшую коллекцию интересных сниппетов, интенсивно использующих возможности D в функциональном программировании.
Также, как пишет сам автор статьи, данная коллекция может быть использована как краткий обзор возможностей языка программирования D и может поспособствовать дальнейшему погружению в изучение стандартной библиотеки Phobos.
Инкрементирование элементов
С помощью map можно применить любую функцию к каждому элементу:
import std.algorithm: map; auto result = [1, 2, 3].map!(a => a + 1); assert(result.equal([2 ,3, 4]));
(Примечание переводчика: map может использоваться не только для инкрементирования, поскольку это универсальная функция высшего порядка, которая отображает некую функцию на весь диапазон данных, таким образом, переводя существующий диапазон в такой, в котором некоторая функция была применена к каждому аргументу)
Вычисление минимума
С помощью reduce мы можем применить функцию со начальным значением, к каждому элементу, используя текущее значение функции как новое для следующего ее вызова:
import std.algorithm: min, max, reduce; auto result = [3, 2, 1].reduce!min; assert(result == 1); result = [3, 2, 1].reduce!max; assert(result == 3);
(Примечание переводчика: не знаю, как правильнее передать смысл этого предложения, но суть в том, что reduce позволяет сворачивать список к единственному результату с помощью некоторой функции двух переменных и одного начального значения. Классика жанра — суммирование всех чисел в массиве, при котором начальным значением является 0, функцией — функция сложения, а само начальное значение служит накопителем результата.)
Фильтрация элементов
С помощью filter мы можем профильтровать входной диапазон, выбрав интересующие нас элементы:
import std.algorithm: count, filter; import std.string: indexOf; auto result = ["hello", "world"] .filter!(a => a.indexOf("wo") >= 0) .count; assert(result == 1);
Сортировка в обратном порядке
С помощью алгоритма sort, который требует в качестве аргумента предикат, мы можем осуществить сортировку в обратном порядке таким образом:
import std.algorithm: sort; auto result = [1, 3, 2].sort!"a > b"; assert(result.equal([3, 2, 1]));
(Примечание переводчика: автор намекает на то, что в sort можно подать любой предикат, который отображает некоторым образом соотношение между собой двух соседних элементов, традиционно именуемых в шаблонах как a и b. Таким образом, sort становится универсальным алгоритмом, не зависящим от типов и от конкретных функций сортировки, однако, обращаю внимание на то, что предикат для соотношения элементов должен удовлетворять некоторым математическим соотношениям (транзитивность и коммутативность, к примеру), иначе ждите занимательных сообщений от компилятора)
Разбиение строки в целочисленные значения
Часто используемый паттерн для работы с вводом от пользователя. Разбиение осуществляется с помощью ленивых вычислений:
import std.algorithm: map, splitter; import std.array: array; import std.conv: to; auto result = "1 3 2".splitter().map!(to!int); assert(result.equal([1, 3, 2]));
Подсчет числа уникальных элементов
Стандартный пример из Unix для сортировки и подсчета количества уникальных строк. В D это пример выглядит точно также:
import std.algorithm: count, sort, uniq; auto result = [1, 3, 2, 2, 3].sort().uniq.count; assert(result == 3);
(Примечание переводчика: не забываем про то, что у алгоритма uniq есть свои причуды, поэтому настоятельно рекомендую обратится к этой статье)
Парная сумма
Разобьем наш входной диапазон на кусочки размером 2 и подсчитаем сумму для каждого из них:
import std.algorithm: map, sum; import std.range: chunks; auto result = [1, 2, 3, 4].chunks(2).map!(sum); assert(result.equal([3, 7]));
Подсчет числа символов
Этот подход требует предварительной сортировки массива, но можно использовать словарь (об этом — ниже), для которого сортировка не нужна:
import std.array: array; import std.algorithm: sort, group; import std.typecons: tuple; // create tuples manually auto result = "ABCA".array.sort().group.array; auto expected = [tuple('A', 2), tuple('B', 1), tuple('C', 1)]; assert(expected == cast(typeof(expected)) result);
Список k-мер
Мы можем выполнить итерацию попарно по всем k-мерам и перечислить их. Синтаксис для преобразования кортежа обратно в список может быть несколько сложным для понимания:
import std.algorithm: map; import std.array: array, join; import std.range: dropOne, only, save, zip; import std.conv: to; auto arr = "AGCGA".array; auto result = arr.zip(arr.save.dropOne) .map!"a.expand.only" .map!(to!string) .join(","); assert(result == "AG,GC,CG,GA");
(Примечание переводчика: k-меры — это подпоследовательности данной последовательности длины k. Особенно активно используется это понятие в биоинформатике)
Подсчет количество k-мер
import std.array: array; import std.algorithm: each, map; import std.range: dropOne, only, save, zip; import std.conv: to; int[string] d; auto arr = "AGAGA".array; arr.zip(arr.save.dropOne) .map!"a.expand.only" .map!(to!string) .each!(a => d[a]++); assert(d == ["AG": 2, "GA": 2]);
Фильтрация по индексу
С помощью enumerate мы можем получить индексы элементов, которые можно использовать в функции filter:
import std.algorithm: filter, map; import std.range: enumerate; auto result = [3, 4, 5] .enumerate .filter!(a => a[0] != 1) .map!"a[1]"; assert(result.equal([3, 5]));
Суммирование по нечетным индексам
С помощью enumerate мы можем получить индексы элементов и выбрать из них только нечетные:
import std.algorithm: filter, map, sum; import std.range: enumerate; auto result = [3, 4, 5] .enumerate .filter!(a => a[0] % 2 == 0) .map!"a[1]" .sum; assert(result == 8);
Самое распространенное слово
Вот вам хороший пример использования group:
import std.algorithm: group, map, sort; import std.array: split; import std.string: toLower; import std.typecons: tuple; string text = "Two times two equals four"; auto result = text .toLower .split(' ') .sort() .group; assert(result.equal([tuple("equals", 1u), tuple("four", 1u), tuple("times", 1u), tuple("two", 2u)]));
Форматирование строки в целом потоке алгоритмов над диапазоном
Использование reverseArgs позволит использовать результат выполнения целого набора алгоритмов (UFCS pipeline) в функции наподобие format:
import std.algorithm : filter, map, sum; import std.range : iota; import std.format : format; import std.functional : reverseArgs; auto res = 6.iota .filter!(a => a % 2) // 0 2 4 .map!(a => a * 2) // 0 4 8 .sum .reverseArgs!format("Sum: %d"); assert(res == "Sum: 18");
Ленивый парсер
С помощью cumulativeFold можно написать ленивый парсер, основанный на стековом принципе:
import std.algorithm : cumulativeFold, equal, map, until; import std.range : zip; auto input = "foo()bar)"; auto result = input.cumulativeFold!((count, r){ switch(r) { case '(': count++; break; case ')': count--; break; default: } return count; })(1).zip(input).until!(e => e[0] == 0).map!(e => e[1]); assert(result.equal("foo()bar"));
Быстрая сортировка
Хороший пример того, насколько выразительным может быть функциональное программирование. Также обратите на то, что второй if не обязателен:
import std.algorithm: filter; import std.array: array; int[] qs(int[] arr) { if(!arr.length) return []; if(arr.length == 1) return arr; // необязательно return qs(arr.filter!(a => a < arr[0]).array) ~ arr[0] ~ qs(arr[1..$].filter!(a => a >= arr[0]).array); } assert(qs([3, 2, 1, 4]) == [1, 2, 3, 4]); assert(qs([1]) == [1]); assert(qs([]) == []);
Спасибо большое авторам D Functional Garden за классные примеры!