В функциональном программировании Map и Fold — два чрезвычайно полезных оператора, и они принадлежат каждому функциональному языку. Если операторы Map и Fold настолько мощны и важны, как вы объясните, что мы можем выполнять свою работу, используя Java, даже если в языке программирования Java нет этих двух операторов? Правда в том, что вы уже делаете Map и Fold при кодировании на Java, за исключением того, что вы делаете их вручную каждый раз, используя циклы.
Отказ от ответственности: я не являюсь справочником по функциональному программированию, и эта статья — всего лишь нежное введение; Поклонники FP могут не ценить это много.Вы уже знакомы с этим
Представьте себе список <Double> сумм без НДС. Мы хотим преобразовать этот список в другой соответствующий список сумм с НДС. Сначала мы определяем метод добавления НДС к одной единственной сумме:
public double addVAT(double amount, double rate) {return amount * (1 + rate);}
Теперь давайте применим этот метод к каждой сумме в списке:
public List<Double> addVAT(List<Double> amounts, double rate){
final List<Double> amountsWithVAT = new ArrayList<Double>();
for(double amount : amounts){
amountsWithVAT.add(addVAT(amount, rate));
}
return amountsWithVAT;
}
Здесь мы создаем другой выходной список, и для каждого элемента входного списка мы применяем к нему метод addVAT (), а затем сохраняем результат в выходном списке, который имеет точно такой же размер. Поздравляем, как мы только что сделали, вручную, Map в списке ввода метода addVAT (). Давайте сделаем это во второй раз.
Теперь мы хотим конвертировать каждую сумму в другую валюту, используя курс валюты, поэтому нам нужен новый метод для этого:
public double convertCurrency(double amount, double currencyRate){return amount / currencyRate;}
Теперь мы можем применить этот метод к каждому элементу в списке:
public List<Double> convertCurrency(List<Double> amounts, double currencyRate){
final List<Double> amountsInCurrency = new ArrayList<Double>();
for(double amount : amounts){
amountsInCurrency.add(convertCurrency(amount, currencyRate));
}
return amountsInCurrency;
}
Обратите внимание, что два метода, которые принимают список, похожи, за исключением метода, вызываемого на шаге 2:
- создать список вывода,
- вызовите данный метод для каждого элемента из списка ввода и сохраните результат в списке вывода
- вернуть список вывода.
Вы делаете это часто в Java, и это именно то, что является оператором Map : примените данный метод someMethod (T): T к каждому элементу списка <T>, который дает вам другой список <T> того же размера.
Функциональные языки признают, что эта конкретная потребность (применять метод к каждому элементу коллекции) очень распространена, поэтому они инкапсулируют ее непосредственно во встроенный оператор Map. Таким образом, учитывая метод addVAT (double, double) , мы можем напрямую написать что-то вроде этого, используя оператор Map:
List amountsWithVAT = map (addVAT, amounts, rate)
Да, первый параметр — это функция, так как функции являются первоклассными гражданами в функциональных языках, поэтому их можно передавать в качестве параметра. Использование оператора Map является более кратким и менее подверженным ошибкам, чем цикл for, и намерение также намного более явное, но у нас его нет в Java…
Итак, смысл этих примеров в том, что вы уже знакомы, даже не зная, ключевой концепции функционального программирования: оператора Map.
А теперь для оператора Fold
Возвращаясь к списку сумм, теперь нам нужно вычислить общую сумму как сумму каждой суммы. Очень просто, давайте сделаем это с помощью цикла:
public double totalAmount(List<Double> amounts){
double sum = 0;
for(double amount : amounts){
sum += amount;
}
return sum;
}
По сути, мы только что сделали Fold по списку, используя функцию ‘+ =’, чтобы сложить каждый элемент в один элемент, здесь число, постепенно, по одному за раз. Это похоже на оператор Map, за исключением того, что результатом является не список, а отдельный элемент — скаляр.
Это снова тот код, который вы обычно пишете на Java, и теперь у вас есть название для функциональных языков: « Fold » или «Reduce». Оператор Fold обычно рекурсивен в функциональных языках, и мы не будем его здесь описывать. Однако мы можем достичь того же намерения в итерационной форме, используя некоторое изменяемое состояние для накопления результата между итерациями. В этом подходе Fold берет метод с внутренним изменяемым состоянием, который ожидает один элемент, например someMethod (T), и применяет его повторно к каждому элементу из списка ввода <T>, пока мы не получим один единственный элемент T, результат операции сгиба.
Типичными функциями, используемыми с Fold, являются суммирование, логическое И и ИЛИ, List.add () или List.addAll (), StringBuilder.append (), max или min и т. Д. Мышление с Fold похоже на агрегатные функции в SQL.
Мышление в формах
Думая визуально (с неаккуратными изображениями), Map берет список размером n и возвращает другой список того же размера:
С другой стороны, Fold берет список размером n и возвращает один элемент (скаляр):
Возможно, вы помните мои предыдущие статьи о предикатах , которые часто используются для фильтрации коллекций в коллекции с меньшим количеством элементов. Фактически этот оператор фильтра является третьим стандартным оператором, который дополняет Map и Fold в большинстве функциональных языков.
Шаблон Eclipse
Поскольку Map и Fold довольно распространены, имеет смысл создавать для них шаблоны Eclipse, например, для Map:
Все ближе к карте и сложить в Java
Map и Fold являются конструкциями, которые ожидают функцию в качестве параметра, и в Java единственный способ передать метод — это обернуть его в интерфейс.
В коллекциях Apache Commons два интерфейса особенно интересны для наших нужд: Transformer , с одним методом transform (T): T , и Closure , с одним единственным методом execute (T): void . Класс CollectionUtils предлагает метод collect (Iterator, Transformer), который в основном является оператором Map бедного человека для коллекций Java, и метод forAllDo (), который может эмулировать оператор Fold с помощью замыканий.
В Google Guava класс Iterables предлагает статический метод transform (Iterable, Function), который в основном является оператором Map.
List<Double> exVat = Arrays.asList(new Double[] { 99., 127., 35. });
Iterable<Double> incVat = Iterables.transform(exVat, new Function<Double, Double>() {
public Double apply(Double exVat) {
return exVat * (1.196);
}
});
System.out.println(incVat); //print [118.404, 151.892, 41.86]
Аналогичный метод transform () также доступен в классах Списки для списков и Карты для карт.
Чтобы эмулировать оператор Fold в Java, вы можете использовать интерфейс Closure, например, интерфейс Closure в Apache Commons Collection, с одним единственным методом только с одним параметром, поэтому вы должны внутренне сохранять текущее состояние -mutable-, как ‘+ = ‘делает.
К сожалению, в Guava нет Fold, хотя его регулярно запрашивают , и даже нет функции, похожей на замыкание, но не сложно создать свою собственную, например, вы можете реализовать общий итог выше с помощью чего-то вроде этого:
// the closure interface with same input/output type
public interface Closure<T> {
T execute(T value);
}
// an example of a concrete closure
public class SummingClosure implements Closure<Double> {
private double sum = 0;
public Double execute(Double amount) {
sum += amount; // apply '+=' operator
return sum; // return current accumulated value
}
}
// the poor man Fold operator
public final static <T> T foreach(Iterable<T> list, Closure<T> closure) {
T result = null;
for (T t : list) {
result = closure.execute(t);
}
return result;
}
@Test // example of use
public void testFold() throws Exception {
SummingClosure closure = new SummingClosure();
List<Double> exVat = Arrays.asList(new Double[] { 99., 127., 35. });
Double result = foreach(exVat, closure);
System.out.println(result); // print 261.0
}
Не только для коллекций: сложить поверх деревьев и других структур
Сила Map и Fold не ограничивается простыми коллекциями, но может масштабироваться до любой навигационной структуры, в частности деревьев и графиков.
Представьте себе дерево, использующее класс Node со своими дочерними элементами. Хорошей идеей может быть кодирование после поиска в глубину и в ширину (DFS & BFS) в два универсальных метода, которые принимают Closure в качестве единственного параметра:
public class Node ...{
...
public void dfs(Closure closure){...}
public void bfs(Closure closure){...}
}
Я регулярно использовал эту технику в прошлом, и я могу сказать, что она может значительно сократить размер ваших классов, используя только один универсальный метод вместо множества похожих методов, каждый из которых будет повторять свой собственный обход дерева. Что еще более важно, обход может быть проверен модулем самостоятельно с использованием ложного замыкания. Каждое укупорочное средство также может быть проверено модулем независимо, и все это просто делает вашу жизнь намного проще.
Очень похожая идея может быть реализована с помощью шаблона Visitor, и вы, вероятно, уже знакомы с ним. Я много раз видел в своем коде и в коде нескольких других команд, что посетители хорошо подходят для накопления состояния во время обхода структуры данных. В этом случае посетитель — это просто особый случай закрытия, который нужно передать для использования в складывании.
Одно слово на карте-уменьшить
Вы, наверное, слышали о паттерне Map-Reduce , и да, слова «Map» и «Reduce» в нем относятся к тем же функциональным операторам Map и Fold (также известным как «Reduce»), которые мы только что видели. Хотя практическое применение более изощренно, легко заметить, что Map смущающе параллельна , что очень помогает для параллельных вычислений.