Функциональные возможности D [перевод]

Эта статья является переводом заметки под названием “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 за классные примеры!