Здравствуйте, меня зовут tmaxx, и я алкоголик понял что такое монады. И, естественно, рассказываю об этом всем вокруг, в том числе и вам. Конечно, это Далеко Не Первая Статья О Монадах на Хабре, но ещё один альтернативный взгляд на проблему, думаю, не помешает.

«Монада», как известно, это «моноид в моноидальной категории эндофункторов», что дает примерно ноль информации несведущему человеку. В программировании, можно попробовать определить монаду как «штуку, реализующую вот такие методы»:

(>>=) :: m a -> (a -> m b) -> m b
return :: a -> m a

Не понятно на Хаскеле? Вот примерный эквивалент на Java:

<A, B> Monad<B> bind(Monad<A> ma, Function<A, Monad<B>> famb); <A> Monad<A> ret(A a);

Все равно остались вопросы? Почему именно такая сигнатура? Что в ней такого особенного, что она используется абсолютно во всех реальных программах написанных на функциональных языках? Попробуем разобраться.

Как проще всего понять что такое Х? Ну конечно написать Х самому! Мы рассмотрим особенности функционального программирования и изобретем по ходу несколько общеизвестных концепций, в том числе монады. Причём делать будем это не на Scala, и даже не на JavaScript, а на той самой энтерпрайзно-многословной Java 8. Почему именно на ней? Это основной и знакомый язык для множества людей (в том числе для меня). Кроме того, многословность и использование длинных имён методов (вместо 2-3-символьных операторов) делает код более-менее читаемым даже для людей, далеких от Java.

Чистые функции

Если уж вы заинтересовались монадами, то наверное знаете, что основным «кирпичиком» функционального программирования (ФП) являются функции. Причём под функцией понимается исключительно функция без состояния и побочных эффектов, имеющая один аргумент возвращающее одно значение. В Java 8 появился дополнительный синтаксис, облегчающий программирование «по-функциональному», и функцию можно создать например так:

Function<Integer, String> intToStr = x -> Integer.toString(x);

Ещё одна функция:

Function<Integer, Integer> square = x -> x * x;

Что делать, если нужна функция 2-х и более аргументов? Нужно вспомнить, что функции в ФП мало отличаются от примитивных значений, и их можно как передавать в другие функции, так и получать из них:

Function<Integer, Function<Integer, Integer>>
add = x -> y -> x + y;

Три аргумента? Тоже не проблема:

Function<Integer, Function<Integer, Function<Integer, Integer>>>
add3 = x -> y -> z -> x + y + z;

Пока вроде выглядит не так плохо, за исключением ужасных многослойных дженериков. Что поделать, на императивном языке можно программировать по-функциональному, но синтаксис для этого не приспособлен. Есть ещё похожая проблема с вызовом функции. Вместо компактного функционального “add3 1 2 3” мы вынуждены писать вызовы явно:

add3.apply(1).apply(2).apply(3); // 6

Подобно тому, как в обычном программировании можно сложить 2 значения и получить третье, в ФП можно объединить 2 функции некоторой операцией и получить новую функцию. Одной из таких операций является композиция. В Хаскеле она обозначается точкой:

fg = f . g

И обозначает что функция fg должна внутри вызвать f, передать результат в качестве аргумента g и вернуть результат. Попробуем написать то же самое на Java:

Function<X, Z> compose(Function<X, Y> f1, Function<Y, Z> f2) {
return x -> f2.apply(f1.apply(x));
}

Что позволяет эта новая операция? Например создать функцию, возвращающую квадрат значения в виде строки:

Function<Integer, String> squareStr = compose(square, intToStr);
squareStr.apply(2); // "4"

Типы и классы типов

Также как и «функция», «тип» в ФП - это более строгое математическое понятие, которое определяется множеством возможных значений (оно может быть бесконечным).

Например Integer - это тип, у него 2³² возможных значений. String - тоже тип с бесконечным множеством значений, но их мы хотя бы можем начать перечислять:

"", "a", "b", ... , "aa", "ab", ...

Как насчёт функции? Является ли функция типом? Тут важны строгие формулировки: сигнатура функции, например Function<Double, Double>, является типом. Конкретная реализация, например add(), - значение этого типа. Реализация может быть определена перечислением значений аргумента и результата.

Как насчёт собственно класса Function<T, R>? Можете перечислить его возможные значения? Хотя бы начать? Не получится. Function - это нечто с параметрами, которые нужно связать с конкретными типами, для того чтобы получился функциональный тип. Такая штука в Хаскелле называется «классом типа» (type class).

Ещё пара классов типов в Java: List или Optional. List<Double> и Optional<Double> - это уже конкретные типы.

Зачем вообще нужен Optional? Для того чтобы показать, что значение функции не определено. Как бы вы реализовали функцию x -> 1 / x? Что возвращать при х = 0? Математически правильного результата не существует. Может быть вернём 0? Многие сейчас брезгливо поморщатся - это же «магическая константа», непонятно почему именно 0, при вызове функции придётся постоянно делать дополнительные проверки результата. Как насчёт null? POSITIVE_INFINITY? Вроде «бесконечность» - неплохой вариант, Java сама так делает. Но так кажется только потому, что это привычный подход, внесённый в IEEE-стандарт. Но он обладает ровно теми же недостатками что и 0. Забыли проверить на нестандартное значение - дальнейшие вычисления могут поломаться.

Стандартный подход в ФП заключается в том, что наша функция должна возвращать не Double, а новый тип, одним из значений которого будет «ошибка». Причём тип хорошо бы переиспользовать для чисел, строк и всего остального. То есть нам нужен класс типа. Раз уж мы пишем все с нуля, давайте сделаем его сами, заодно использовав названия из Хаскеля, насколько возможно:

public class Maybe<T> {
private final T value;
private final boolean nothing;

public boolean isNothing() {
return nothing;
}

public T getValue() {
return value;
}

private Maybe(T value, boolean nothing) {
this.value = value;
this.nothing = nothing;
}

public static <T> Maybe<T> just(T value) {
return new Maybe<T>(value, false);
}

public static <T> Maybe<T> nothing() {
return new Maybe<T>(null, true);
}

@Override
public String toString() {
return nothing ? "Nothing" : "Just " + value;
}
}

Тогда наша функция будет определена как:

Function<Double, Maybe<Double>> inverse = x -> {
double y = 1 / x;
return Double.isFinite(y) ? just(y) : nothing();
}

Пробуем:

Maybe<Double> y = inverse.apply(Double.MIN_VALUE); // "Nothing"

Теперь, когда inverse возвращает особый тип Maybe, мы можем попытаться «забыть» про возможную ошибку и передать результат другой функции:

square.apply(y); // ошибка компиляции

Но компилятор нас сразу поправит. В ФП в целом стараются как можно больше проверок вытащить в compile-time. Этому способствует развитая система типов. Отсюда известная присказка: «компилируется значит работает»

Функторы

Возникает вопрос, а что нам, собственно, делать с полученным Maybe? Ни в одну уже известную функцию его передать не получится. Может «достать» из него обычный double и дальше работать с ним?

if (!y.isNothing()) {
return square.apply(y.getValue());
} else ???

Так, а если Nothing, то ... эээ ... магическое число? Опять та же проблема. В некоторых случаях допустимо «проглотить» признак ошибки и вернуть из функции чистое значение. Но это требует четкого понимания, всех возможных вариантов использования функции и применимо далеко не всегда. Обычно функция, которая получает Maybe, должна возможность «пробросить» его в свой результат, например:

Function<Maybe<Double>, Maybe<Double>> maybeSquare =
x -> x.isNothing() ? Maybe.nothing() :
Maybe.just(square.apply(x.getValue()));
maybeSquare.apply(inverse.apply(2.0)); // Just 0.25

Это работает, но реализация maybeSquare очень похожа на реализацию square. Не хотелось бы писать Maybe-варианты для всех уже определенных функций. Можно ли как-то обобщить? Оказывается можно написать функцию, которая принимает любую функцию (одного аргумента) и возвращает ее Maybe-вариант! Причём такая функция не должна работать только с Double а может быть более обобщенной:

// Haskell fmap :: (a -> r) -> m a -> m r
Function<Maybe<A>, Maybe<R>> fmap(Function<A, R> far) {
return a -> a.isNothing() ? Maybe.nothing() :
Maybe.just(far.apply(a.getValue()));
}

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

Function<Maybe<Double>, Maybe<Double>> maybeSquare =
Maybe.fmap(square);
Function<Double, Maybe<Double>> inverseSquare =
compose(inverse, maybeSquare);
System.out.println(inverseSquare.apply(2.0)); // just(0.25)

Аппликативные Функторы

Все это прекрасно, но у нас также есть функции 2-х и более аргументов, что делать с ними?Можно написать аналог fmap для них (глубоко вздохните и приготовьтесь к тонне дженериков):

// Haskell liftA2 :: (a -> b -> r) -> m a -> m b -> m r
Function<Maybe<A>, Function<Maybe<B>, Maybe<R>>>
liftA2(Function<A, Function<B, R>> fabr) {
return x -> y -> x.isNothing() || y.isNothing() ?
Maybe.nothing() :
Maybe.just(fabr.apply(x.getValue()).apply(y.getValue()));
}

// Haskell liftA3 :: (a -> b -> c -> r) -> m a -> m b -> m c -> m r
Function<Maybe<A>, Function<Maybe<B>, Function<Maybe<C>, Maybe<R>>>>
liftA3(Function<A, Function<B, Function<C, R>>> fabcr) {
return x -> y -> z ->
x.isNothing() || y.isNothing() || z.isNothing() ?
Maybe.nothing() :
Maybe.just(fabcr.apply(x.getValue())
.apply(y.getValue()).apply(z.getValue()));
}

Имена функций могут показаться немного странными, но они общеприняты. К слову, fmap - это синоним liftA и liftA1, и в целом операция «поднимает» функцию из области обычных типов в область обёрток. Более важный вопрос - нам обязательно писать отдельные функции для каждого числа аргументов? Можно ли как-то обобщить?

Попробуем просто передать функцию от 2-х аргументов в ту же fmap:

something = Maybe.fmap(add);

И попросить IDE автоматически вывести тип результата:

Function<Maybe<Double>, Maybe<Function<Double, Double>>>
something = Maybe.fmap(add);

Хм, давайте разбираться, что произошло. На самом деле функция от двух аргументов - это функция от одного (первого) аргумента возвращающая функцию от второго аргумента. fmap честно завернул в Maybe и первый аргумент (то что нужно), и функцию (не совсем то что нужно, но направление верное).

Чтобы получить сигнатуру liftA2 , нам нужно «пропихнуть» Maybe дальше с помощью вот такой функции, немного похожей на fmap:

// Haskell ap :: m (a -> r) -> m a -> m r
Function<Maybe<A>, Maybe<R>> ap(Maybe<Function<A, R>> mfar) {
return mfar.isNothing() ?
x -> nothing() :
x -> just(mfar.getValue().apply(x.getValue()));
}

Теперь liftA2 легко сводится к ap и fmap:

Function<Maybe<A>, Function<Maybe<B>, Maybe<R>>>
liftA2(Function<A, Function<B, R>> fabr) {
return x -> y -> ap(fmap(fabr).apply(x)).apply(y);
}

А liftA3 - к liftA2 и ещё одному ap, и так далее:

Function<Maybe<A>, Function<Maybe<B>, Function<Maybe<C>, Maybe<R>>>>
liftA3(Function<A, Function<B, Function<C, R>>> fabcr) {
return x -> y -> z -> ap(liftA2(fabcr).apply(x).apply(y)).apply(z);
}

Более того, fmap тоже сводится к ap и простой операции под названием pure, которая просто заворачивает значение в Maybe:

Maybe<A> pure(A a) {
return just(a);
}
Function<Maybe<A>, Maybe<R>> fmap(Function<A, R> far) {
return ap(pure(far));
}

Кстати, вы заметили, что мы вовсю начали использовать принцип «компилируется значит работает»? :) Главной сложностью было согласовать все типы и избавиться от ошибок компилятора.

Сводить liftA2 и liftA3 к комбинации pure и ap гораздо проще, чем писать их c нуля. Но у такого подхода есть ещё одно преимущество - он работает для любого функтора, а не только для Maybe! Все что нам нужно для определения нового функтора - это написать pure и ap. После этого любая функция над примитивными типами легко преобразуется в функцию над обертками.

Монады

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

Следущая задача - реализовать среднее гармоническое:

f(x, y) = 1 / ((1 / x + 1 / y) / 2)

Если любой из аргументов равен нулю, можно вернуть Nothing. Поехали:

Function<Double, Double> half = x -> x / 2;

Function<Double, Function<Double, Maybe<Double>>>
denominator = x -> y -> Maybe.fmap(half).apply(
maybeAdd.apply(inverse.apply(x))
.apply(inverse.apply(y))
);
Function<Double, Function<Double, Maybe<Double>>> nope =
x -> y -> inverse.apply(denominator.apply(x).apply(y));

Не работает. В смысле - не компилируется. :)

Функция inverse ожидает Double, а функция denominator возвращает Maybe<Double>. Может залифтить inverse?

Function<Double, Function<Double, Maybe<Maybe<Double>>>>
yeah = x -> y -> Maybe.fmap(inverse)
.apply(denominator.apply(x).apply(y));
yeah.apply(1.0).apply(2.0); // Just Just 1.333...

Лучше, но теперь result имеет странный тип «двойного Maybe». Нужно избавится от одной обертки. В случае Maybe это сделать тривиально:

// Haskell join :: m (m a) -> m a
Maybe<A> join(Maybe<Maybe<A>> mma) {
return mma.isNothing() ? nothing() : mma.getValue();
}

Но! Можно ли вообще избавиться от странных двойных обёрток (и не лифтить наш inverse)? Напомню, нас есть Maybe denominator и Function inverse, добавляющая одну обертку. Нам нужно из них получить обернутый один раз Maybe result. И желательно это оформить как функцию двух аргументов, то есть как функцию первого аргумента, возвращающую фунцкию второго:

// Haskell bind :: m a -> (a -> m r) -> m r
Function<Function<A, Maybe<R>>, Maybe<R>> bind(Maybe<A> ma) {
if (ma.isNothing()) {
return famr -> nothing();
} else {
return famr -> famr.apply(ma.getValue());
}
}

Тогда среднее гармоническое будет выглядеть так:

Function<Double, Function<Double, Maybe<Double>>> gmean = x -> y -> { Function<Function<Double, Maybe<Double>>, Maybe<Double>> bound = Maybe.bind(denominator.apply(x).apply(y));
return bound.apply(inverse);
};
System.out.println(gmean.apply(1.0).apply(3.0)); // 1.5

bind оказывается удивительно универсальной обобщенной функцией. Из неё (и из элементарной pure) можно вывести и join, и ap, а, следовательно, и все «лифты» начиная с fmap. Поэтому именно она вошла в определение обобщенной монады:

interface Monad {
// Haskell pure :: a -> m a
<A> Maybe<A> pure(A a);

// Haskell bind :: m a -> (a -> m r) -> m r
<A, R> Function<Function<A, Maybe<R>, Maybe<R>> bind(Maybe<A> ma);
}

Небольшое замечение по именованию методов. Метод pure в Haskell определён для аппликативного функтора. Для монады определён полностью аналогичный метод return. К сожалению, я не могу использовать в Java зарезервированное слово return для имени метода, поэтому будем дальше использовать pure.

Немного абстрактных рассуждений

Подведём некоторые итоги, рассуждая теперь в терминах абстрактной теории категорий. Категория по определению - это некоторый класс объектов плюс множество морфизмов («стрелок») между ними. Немного похоже на граф, только граф обычно конечный (категория – нет), а еще морфизмов между двумя объектами категории тоже может быть не 1, а бесконечно много.

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

Для того чтобы добавить флаг ошибки в результат функции нам пришлось создать новую категорию - категорию Maybe-типов вместе с морфизмами-функциями между ними. Функтор - это отображение одной категории в другую. То есть правило, по которому каждому обычному типу и каждой обычной функции сопоставляется Maybe-аналог. То есть функтор позволяет «выйти» за пределы конкретной категории типов.

Цель монады в некотором смысле противоположна - она позволяет остаться в рамках одной категории, несмотря на то что аргумент и результат вызываемой функции явно лежат в разных. Хитрым математическим трюком монаду можно превратить в функтор, но я бы на этом не концентрировался. Монады можно объяснить, не объясняя функтор. Функтор просто проще для понимания, и позволяет немного потренироваться в функциональной эквилибристике.

Кстати о понимании. Как лучше визуально представить себе монады? Иногда их изображают чем-то вроде ящиков, в которые кладутся и извлекаются значения. То есть понимают их как некоторый контейнер. Есть много примеров монад-контейнеров: уже реализованный нами Maybe. Или List. Но есть и еще один способ использования монад - как способ сохранить состояние вычислительного процесса, о котором поговорим позже на конкретных примерах. И аналогия с ящиками в этом случае будет хромать.

Я бы представил монады как значение, связанное с некоторым контекстом. Суть контекста зависит от конкретной монады. Как именно связано - не важно. Можно представить значение и контекст лежащие в одном ящике или в мешке, или приклееные друг к другу. В любом случае важен не ящик, а дополнительный контекст лежащий в нем вместе со значением. В случае Maybe - это флаг ошибки, в случае List - хвост списка и так далее.

Важно ещё и то, что монада не обязана предоставлять доступ внутрь ящика - к «голому» значению, а уж тем более к контексту. Вместо этого монада позволяет легко оперировать с уже упакованными значениями. И после каждой операции контекст может изменится. Как именно – контролирует монада.

Монады как контекст выполнения

Простейшим примером контекста выполнения может служить счётчик. Допустим нам просто нужно посчитать, сколько раз мы делаем некоторую операцию. Значение вместе с контекстом будет выглядеть так (метод next увеличивает счетчик):

public class Counter<T> {
private final T value;
private final int count;

public Counter(T value, int count) {
this.value = value;
this.count = count;
}

public int getCount() {
return count;
}

public T getValue() {
return value;
}

public Counter<T> next() {
return new Counter<T>(value, count + 1);
}

public String toString() {
return value + "(" + count + ")";
}
}

Как мы уже знаем, чтобы сделать его монадой нужно реализовать 2 фукции:

Counter<T> pure(T value) {
return new Counter<>(value, 0);
}

Function<Function<A, Counter<R>>, Counter<R>> bind(Counter<A> ma) {
return (Function<A, Counter<R>> famb) -> {
// применяем функцию к “голому” значению:
Counter<R> mb = famb.apply(ma.getValue());
// объединяем контексты:
return new Counter<>(
mb.getValue(), ma.getCount() + mb.getCount());
};
}

Все! Любую чистую функцию, которую мы уже реализовали, теперь можно залифтить в категорию Counter, например:

Function<Counter<Double>, Function<Counter<Double>,
Function<Counter<Double>, Counter<Double>>>> countAdd3 =
Counter.liftA3(add3);

Counter<Double> cx = Counter.pure(10.0).next().next(); // 10.0 (2)
Counter<Double> cy = Counter.pure(20.0).next(); //20.0 (1)
Counter<Double> cz = Counter.pure(30.0); //30.0 (0)
// cкладываем и значения, и контексты счетчиков:
println(countAdd3.apply(cx).apply(cy).apply(cz)); // 60.0 (3)

Всю цепочку реализаций для Counter и остальных монад можно посмотреть на GitHub, но приведу здесь самую сложную реализацию из цепочки:
Function<Counter<A>, Counter<R>> ap(Counter<Function<A, R>> mf) {
return (Counter<A> mx) ->
Counter.<Function<A,R>,R>bind(mf).apply((Function<A, R> f) -> {
Function<Function<A, Counter<R>>, Counter<R>> ffamrmr =
Counter.<A, R>bind(mx);
return ffamrmr.apply(x -> pure(f.apply(x)));
});
}

Если вы уже с трудом справляетесь с обилием дженериков и лямбд в коде – вы не одиноки. Компилятор Java и IDE на данном этапе тоже начинают серьезно путаться и перестают автоматически выводить все типы. Приходится вставлять им (и читателям заодно) подсказки, вроде Counter.<A, R>bind(…) и (Counter<A> mx) -> ...

Haskell имеет гораздо более развитую систему типов, и гораздо лучше приспособлен для таких упражнений, вот, к примеру, код, аналогичный реализации выше:

ap :: Monad m => m (a -> b) -> m a -> m b
ap mf mx =
mf >>= (\f ->
mx >>= (\x ->
return (f x)))

К слову, код ap на Haskell унифицирован (написан один раз для всех монад и внутри использует -> , он же bind). А код на Java написан конкретно для Counter. Можно ли как-то обобщить? Ну то есть добавить default Function<Monad, Monad> ap(Monad<Function> mf) в интерфейс Monad и определить его один раз для всего? К сожалению нет, опять же из-за неприспособленности системы типов Java. Пришлось бы писать что то вроде:

Function<M<A>, M<R>> ap(M<Function<A, R>> mf){ ... }

То есть “типы аргумента и результата функции могут отличаться, но они должны быть завернуты в одну и ту же монаду”. Здесь javac честно признается – “это перебор!” Но мы не будем сдаваться и для всех новых монад просто будем копипастить обобщенные методы (ap, join, lift, …) из предыдущего кода.

Генератор случайных чисел

Рассмотрим задачу посложнее, тоже достаточно математическую (мы дойдём до IO, обещаю!). Реализовать генератор случайных чисел. Возьмём простейший линейно-конгруэнтный генератор:

private static final Long MULTIPLIER = 6364136223846793005L;
public long next() {
seed = seed * MULTIPLIER + 1;
return seed;
}

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

class RandomState {
private final T value;
private final long seed;
public RandomState(T value, long seed) {
this.value = value;
this.seed = seed;
}

public T getValue() {
return value;
}

public long getSeed() {
return seed;
}

public RandomState<T> next() {
return new RandomState<>(value, seed * MULTIPLIER + 1);
}

@Override
public String toString() {
return value + "(" + seed + ")";
}

Получили снова «значение, связанное с контекстом». Попробуем реализовать это как монаду. Для этого, как обычно, нам нужно понять как объединять 2 контекста: seed1 и seed2. В Maybe это было логическое ИЛИ, в Counter - сумма. Здесь нас ждет неожиданная проблема - сиды нельзя объединять, нужно выбрать один из них. Но какой? Очевидно тот, который сгенерирован позднее (иначе наш ГСЧ начнёт повторяться). Но как его определить? Ответ: практически - никак (теоретически способы есть, но неприемлемые из-за производительности).

Попробуем понять в чем проблема. В простом счётчике контекстом является «сколько раз инкрементирован счётчик». Но в ГСЧ нас тоже по сути интересует сколько раз выполнена операция генерации («умножить на большое странное число и прибавить 1»). То есть вместо конечного сида нам нужно хранить начальный сид и счётчик операций! Тогда все объединяется элементарно. А чтобы получить конечное значение, нужно просто вызвать операцию N раз в цикле. Хм... Раз уж мы так далеко продвинулись в ФП, может быть можно как-то не возвращаться обратно к for (i = 0; i < counter; i++)?

Последний шаг который нужно сделать, раз уж мы занимаемся ФП: контекст не обязан быть обычным значением. Или (что то же самое) функция - это самое обычное значение. Контекст может быть функцией! Объединением двух функций-контекстов «умножить и прибавить» является функция-контекст «умножить и прибавить дважды». Оба объединяемых контекста одинаковы, поэтому неважно в каком порядке их объединять. Приблизительно так:

public class Random<T> {
// применить все накопленные функции-контексты, начиная c сида
private final Function<Long, RandomState<T>> runState;

public Random(Function<Long, RandomState<T>> runState) {
this.runState = runState;
}

public RandomState<T> seed() { // сид по умолчанию
return seed(42);
}

public RandomState<T> seed(long seed) { // произвольный сид
return runState.apply(seed);
}

public Random<T> next() {
return new Random<>(
// к уже имеющимся контекстам добавить еще один
(Long s) -> runState.apply(s).next()
);
}

public static <T> Random<T> pure(T value) {
return new Random<>(
// обернуть значение в функцию-контекст
s -> new RandomState<>(value, s)
);
}

public static <A, B> Function<Function<A, Random<B>>, Random<B>>
bind(Random<A> ma) {
return (Function<A, Random<B>> famb) -> {
Function<Long, RandomState<B>> f = (Long s) -> {
// применить контекст A (получив сид+значение)
RandomState<A> sa = ma.runState.apply(s);
// применить к значению переданную функцию
Random<B> mb = famb.apply(sa.getValue());
// применить дополнительно контекст B, сохранить полученный сид
RandomState<B> sb = mb.runState.apply(sa.getSeed());
return sb;
};
};
}

Обратите внимание – вызовы pure и bind не запускают никаких вычислений немедленно. Они только комбинируют ленивые функции. Для того чтобы что-то получить, нужно передать начальный сид:

Random<Double> rx = Random.pure(10.0);
// начальный сид по умолчанию:
System.out.println(rx.initSeed()); // 10.0 (42)

Random<Double> ry = Random.pure(20.0).next(); // сид изменился 1 раз
System.out.println(ry.initSeed()); // 20.0 (9039304369631583587)

Random<Double> rz = Random.pure(30.0).next().next(); // 2 раза
System.out.println(rz.initSeed()); // 30.0 (8647191391818483560)

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

Function<Random<Double>, Function<Random<Double>,
Function<Random<Double>, Random<Double>>>> randomAdd3 =
Random.liftA3(add3);

//сид изменился 3 раза,
System.out.println(
randomAdd3.apply(rx).apply(ry).apply(rz)
.initSeed()); 60.0(-8112431728599112375) - дефолтный начальный сид

System.out.println(
randomAdd3.apply(rx).apply(ry).apply(rz)
.initSeed(13)); // 60.0(5758669995324752264) – используем другой сид

Монада State

Думаю вы уже заметили, что seed – это просто некоторое внутреннее состояние с заданным законом преобразования (определенным в методе next). Ничто не мешает нам обобщить этот метод на произвольный тип и произвольную функцию преобразования:

public class State<T, S> {
private final Function<S, Pair<T, S>> runState;

public Pair<T, S> apply(S seed) {
return runState.apply(seed);
}

public State(Function<S, Pair<T, S>> runState) {
this.runState = runState;
}

public State<T, S> next(Function<S, S> transition) {
return new State<>((S s) -> {
Pair<T, S> p1 = runState.apply(s);
return new Pair<>(p1.getX(), transition.apply(p1.getS()));
});
}

public S init(S initial) {
return runState.apply(initial).getS();
}

public static <T, S> State<T, S> pure(T value) {
return new State<>((S s) -> new Pair<>(value, s));
}
}

bind приводить здесь не буду – смотрите на GitHub. Он очень похож на Random.bind, только параметр Long заменяется обобщенным параметром S.

Функцию перехода в следующее состояние мы можем определить как угодно. Давайте, например, сделаем состояние строкой и добавим логгирование в наши вычисления:

Function<String, String> log(String line) {
return s -> (s == null ? "" : s) + line + ";";
}

Создаем несколько значений с логами:

State<Double, String> sx = State.pure(10.0);
System.out.println(sx); // 10.0 ("") - ничего не залогировано

State<Double, String> sy = State.pure(20.0);
sy = sy.next(log("log1")); // логируем один раз
System.out.println(sy); // 20.0 ("log1")

State<Double, String> sz = State.pure(30.0);
sz = sz.next(log("log2")).next(log("log3")); // логируем еще пару раз

System.out.println(sz); // 30.0 ("log2;log3;")

Вызываем чистую фунцию (все логи сохранены):

Function<State<Double, String>, Function<State<Double, String>,
Function<State<Double, String>, State<Double, String>>>> logAdd3 =
State.liftA3(add3);

System.out.println(
logAdd3.apply(sx).apply(sy).apply(sz)); // 60.0 (log1;log2;log3;)

Вместо логирования, можно определить соответствующие функции переходов для наших Counter и Random, чтобы получить их функциональность из обобщенного State:

Function<Integer, Integer> increment = x -> x == null ? 1 : x + 1;

Function<Long, Long> rand = x -> x == null ? 0 : x * MULTIPLIER + 1;

А еще преобразование состояния не обязано быть одно и то же. В дополнение к next можно передавать, например, функции:
- put - сохранить значение в состояние
- get - восстановить значение из состояния

Ввод-вывод

Если с помощью монад можно возвращать псевдослучайные значения, то может быть можно реализовать и строго случайные? Например последовательность нажатий клавиш на клавиатуре. Именно это и делает монада IO. Из-за скрытого в монаде контекста, можно написать чистую функцию readChar, которая возвращает каждый раз разное значение! Все из-из того, что контекст передаётся в качестве аргумента, и он каждый раз разный (об этом заботится сама монада). Монада, как мы уже говорили, не обязана раскрывать свой контекст, а функции ее использующие не должны завязываться на сущность этого контекста. Все что нам нужно сделать в монаде IO - позаботиться чтобы контекст был каждый раз разным. На Java это будет выглядеть как-то так:

public class IO<T> {
private final T value;

public static <T> IO<T> pure(T value) {
return new IO<>(value);
}

public static <A, R> Function<Function<A, IO<R>>, IO<R>>
bind(IO<A> ma) {
return (Function<A, IO<R>> famr) -> {
IO<R> mb = famr.apply(ma.getValue());
return new IO<>(mb.getValue());
};
}
}

Кстати, а что является “контекстом” в IO? От контекста (и ни от чего больше!) зависит какая следующая клавиша будет нажата. В целом, IO возвращает состояние устройств ввода-вывода, а оно может зависеть от чего угодно. То все что угодно является частью контекста. Теоретически – в контекст IO входит весь мир, внешний по отношению к программе! Разумеется весь мир невозможно хранить в машинной памяти, но ситуацию спасает то, что монада IO (как и всякая другая монада) не обязана предоставлять доступ к любой части контекста. Ну то есть теоретически, контекст IO включает текущую погоду на Марсе. Но IO даст к ней доступ, только если программа выполняется на марсоходе, оборудованном соответствующими датчиками.

Теперь мы наконец можем написать наши первые фукции ввода-вывода для монады IO (сами функции являются императивными, но это скрыто от использующего их кода):

public static IO<Double> readDouble() {
System.out.print("Enter a double:");
double value = new Scanner(System.in).nextDouble();
return new IO<>(value);
};

public static IO<Void> writeDouble(Double value) {
System.out.println(value);
return new IO<>(null);
};

И написать супер полезную программу вычисляющую квадрат произвольного числа:

Function<IO<Double>, IO<Double>> ioSquare = IO.fmap(square);
IO<Double> x = IO.readDouble(); IO.<Double,Void>bind(ioSquare.apply(x)).apply(r -> IO.writeDouble(r));

Выглядит вроде неплохо. Залифтили square, прочитали число, вычислили результат обернутый в монаду (с контекстом). Передали в bind обертку и указание что делать с оберткой (вы не забыли что bind – имеет два аргумента?). bind внутри исполнила указание, напечатав результат.

Но наша программа все еще написана в императивном стиле! В ФП нет команд, нет никакого “сначала делать то, потом это, потом остановиться”. Программа на ФП – это функция. Одна. Возможно вызывающая много других функций.

Цепочки вычислений

Давайте еще упростим. Программа выводящая одно число:

IO<Void> io = IO.writeDouble(1.0);

Отлично – это вызов ровно одной функции. Как вывести два числа? Заметьте, переменная io не используется, но по хорошему должна. Она хранит контекст IO (весь мир с выведенным на экран “1.0”). Куда ее можно передать? Ну конечно в монаду!

IO<Void> io = IO.writeDouble(1.0)
Function<Function<Void, IO<Void>>, IO<Void>> f =
IO.<Void, Void>bind(io);

bind ожидает второй аргумент – функцию которая ничего принимает Void вход и возвращает IO<Void>. Нетрудно догадаться, что это может быть writeDouble:

IO<Void> io = IO.<Void, Void>bind(IO.writeDouble(1.0))
.apply(v -> IO.writeDouble(2.0));

Куда опять девать io? В следующий bind конечно:

IO<Void> io = IO.<Void, Void>bind(
IO.<Void, Void>bind(
IO.writeDouble(1.0)
).apply(v -> IO.writeDouble(2.0))
).apply(v -> IO.writeDouble(3.0));

Работает, но чтобы добавлять новые значения, придется всю программу оборачивать “скобками” bind/apply. Заметим, что в нашем случае самый важный аргумент функции bind – второй (функция вывода). Давайте напишем вспомогательную фунцкию, меняющую аргументы bind местами. В Хаскеле она конечно же обобщенная (для всех монад) и является бинарным оператором =<<, по аналогии с >>= для обычной bind.

// Haskell =<< :: (a -> m r) -> m a -> m r
Function<IO<A>, IO<R>> flip(Function<A, IO<R>> f) {
return ma -> {
Function<Function<A, IO<R>>, IO<R>> bind = bind(ma);
return bind.apply(f);
};
}

Тогда код, выводящий 3 числа, можно переписать так:

IO.flip((Void unused) -> IO.writeDouble(1.0))
.apply(IO.flip((Void unused) -> IO.writeDouble(2.0))
.apply(IO.writeDouble(3.0))); // Вывод: 3.0 2.0 1.0

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

IO.<Void, Void>flip(u -> IO.writeDouble(1.0))
.andThen(IO.<Void, Void>flip(u -> IO.writeDouble(2.0)))
.andThen(IO.<Void, Void>flip(u -> IO.writeDouble(3.0)))
.andThen(IO.<Void, Void>flip(u -> IO.writeDouble(4.0)))
.andThen(IO.<Void, Void>flip(u -> IO.writeDouble(5.0)))
.apply(IO.pure(null)); // Вывод: 1.0 2.0 3.0 4.0 5.0

Обратите внимание на последний apply – он инициализирует контекст IO и выполняется в самом начале. Аналогичный код на Хаскеле будет выглядеть так:

writeDouble(1.0) >>
writeDouble(2.0) >>
writeDouble(3.0) >>
writeDouble(4.0) >>
writeDouble(5.0)

Наконец мы можем написать полноценную функциональную программу с вводом-выводом:

IO.<Void, Double>flip(u -> IO.readDouble())
.andThen(IO.flip((Double d) -> IO.writeDouble(square.apply(d))))
.apply(IO.pure(null));

Аналог на Хаскеле, конечно, выглядит гораздо проще:

do
d <- readDouble()
writeDouble(square d)

Заключение

Разумеется, Java не создавалась как функциональный язык. В ней отсутствует множество вещей, делающих ФП гораздо проще:

• продвинутая система типов

• упрощенный синтаксис для вызова и преобразования функций

• перегрузка бинарных операторов

• оператор do для цепочек вычислений

• кортежи для передачи нескольких переменных

Эта статья – скорее иллюстрация, что если сильно помучится, то практически любой Тюринг-полный язык можно приспособить под любые нужды. В практическом смысле писать так на Java конечно не стоит.

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

Не знаю есть ли способ это сделать. Код на гитхабе:
https://github.com/maxtomin/JavaMonads/