Ненаучно о монадах

Всем привет.

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

Примеры кода будут написаны на языке Kotlin, т.к. он достаточно популярен, и в то же время достаточно функционален (в обоих смыслах этого слова).

Начнем с понятия функтора, вот он:

interface Functor<A>
В чем его смысл? Функтор — это абстракция над произвольным вычислением (computation), возвращающим результат типа А. Мы абстрагируемся от того, как создать новый функтор, и, что самое важное, от того, как вычислить его значение А. В частности, за интерфейсом функтора может прятаться функция с произвольным числом аргументов, и не обязательно чистая функция.

Примеры реализаций функтора:

  • константа
  • функция с произвольным числом аргументов, возвращающая результат типа A
  • псевдослучайный генератор с состоянием (Random)
  • аппаратный генератор случайных чисел
  • чтение объекта с диска или из сети
  • асинхронное вычисление — в реализацию функтора передается callback, который будет вызван когда-нибудь потом

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

Интерфейс функтора не позволяет ни получить значение типа A из Functor<A>, ни создать новый Functor<A> по существующему значению типа A. Но даже с такими ограничениями функтор небесполезен — если для некоторого типа B мы умеем преобразовывать A в B (иными словами, существует функция (a: A) -> B), то мы можем написать функцию (f: Functor<A>) -> Functor<B> и назвать её map:

interface Functor<A> {
fun <B> map(f: (A) -> B): Functor<B>
}

В отличие от самого функтора, метод map не может быть произвольной функцией:
— map((a) -> a) должен вернуть тот же функтор
— map((a) -> f(a)).map((b) -> g(b)) должно быть идентично map(a -> g(f(a))

В качестве примера реализуем функтор, который возвращает значение A, содержащее в себе некоторое количество случайных бит. Наш интерфейс в Котлине так просто использовать не получится (но при желании можно), поэтому напишем extension method:

// функтор — вычисление, работающие с результатами типа А, поддерживает метод map
data class MyRandom<A>(
val get: (bits: Int) -> A
) {
companion object {
val intRandom: MyRandom<Int> = MyRandom { Random.nextBits(it) }
val hexRandom: MyRandom<String> = intRandom.map { it.toString(16) }
}
}

// метод map для функтора
fun <A, B> MyRandom<A>.map(f: (A) -> B): MyRandom<B> =
MyRandom(get = {bits -> f(get(bits)) })

fun main(args: Array<String>) {
println(«random=» + MyRandom.intRandom.get(12)) // выводит random=1247
println(«hexRandom=» + MyRandom.hexRandom.get(12)) // выводит hexRandom=c25
}

Другие примеры функторов с полезным map

  • иммутабельный List<A>
  • MyInputStream<A>
  • Optional<A>

Теперь можно перейти к монадам.

Монада — это функтор с двумя дополнительными операциями. Прежде всего, монада, в отличие от функтора, содержит операцию создания из константы, эта операция называется lift:

fun <A> lift(value: A): Monad<A> = TODO()

Вторая операция называется flatMap, она сложнее, поэтому сначала приведем наш интерфейс монады целиком:

interface Monad<A> {
// монада является функтором, но map реализовывать отдельно не нужно —
// он выражается через flatMap и lift
fun <B> map(f: (A) -> B): Monad<B> = flatMap { a -> lift(f(a)) }
fun <B> flatMap(f: (A) -> Monad<B>): Monad<B>
}

fun <A> lift(value: A): Monad<A> = TODO()

Самое важное отличие монады от функтора — монады можно комбинировать друг с другом, порождая новые монады и при этом абстрагируясь от того, как именно реализована монада — читает ли она с диска, принимает ли она дополнительные параметры для вычисления своего значения, существует ли это значение вообще. Второй важный момент — монады комбинируются не параллельно, а последовательно, оставляя возможность добавлять логику в зависимости от результата первой монады.

Пример:

// монада, которая читает из сети Int
// сама по себе монада является константой — это просто обертка над функцией
// сокет передается извне при выполнении монады за пределами этого кода
val readInt: Monad<Int> = TODO()

// монада, которая читает из сети нужное кол-во байт
fun readBytes(len: Int): Monad<ByteArray> = TODO()

// монада, которая сначала читает длину массива, потом сам массив
val bytes: Monad<ByteArray> = readInt.flatMap {len ->
if (len > 0)
readBytes(len) // после чтения заголовка — читаем массив
else
lift(ByteArray(0)) // массив пустой, возвращаем пустой массив
}

Впрочем, в этом примере нет никакого упоминания о сети. С тем же успехом данные могут читаться из файла или из базы данных. Они могут читаться синхронно или асинхронно, здесь же может быть обработка ошибок — всё зависит от конкретной реализации монады, сам же код останется неизменным.

Сначала пример попроще, монада Option. В котлине нужна не особо, но в Java/Scala исключительно полезна:

data class Option<A>(val value: A?) {
fun <B> map(f: (A) -> B): Option<B> = flatMap { a -> lift(f(a)) }
fun <B> flatMap(f: (A) -> Option<B>): Option<B> = when(value) {
null -> Option(null)
else -> f(value)
}
}
fun <A> lift(value: A?): Option<A> = Option(value)

fun mul(a: Option<Int>, b: Option<Int>): Option<Int> =
a.flatMap { a ->
b.map { b ->
a * b
}
}

fun main(args: Array<String>) {
println(mul(Option(4), Option(5)).value) // 20
println(mul(Option(null), Option(5)).value) // null
println(mul(Option(4), Option(null)).value) // null
println(mul(Option(null), Option(null)).value) // null
}

В качестве монады позаковыристей, давайте завернем в монаду работу с базой данных:

data class DB<A>(val f: (Connection) -> A) {
fun <B> map(f: (A) -> B): DB<B> = flatMap { a -> lift(f(a)) }
fun <B> flatMap(f: (A) -> DB<B>): DB<B> = DB { conn ->
f(this.f(conn)).f(conn)
}
}

fun <A> lift(value: A): DB<A> = DB { value }

fun select(id: Int): DB<String> = DB { conn ->
val st = conn.createStatement()
// ….
TODO()
}

fun update(value: String): DB<Unit> = DB { conn ->
val st = conn.createStatement()
// ….
TODO()
}

fun selectThenUpdate(id: Int): DB<Unit> = select(id).flatMap { value ->
update(value)
}

fun executeTransaction(c: Connection): Unit {
// создать монаду, которая выполнит всю транзакцию
// при создании монады никакие запросы в базу не идут
val body: DB<Unit> = selectThenUpdate(42)
// выполняем монаду, которая сделает select и update
body.f(c)
c.commit()
}

Глубока ли кроличья нора?
Разнообразных монад существует огромное множество, но основное их назначение — абстрагирование бизнес-логики приложения от каких-то деталей выполняемых вычислений:

  • что значение может не существовать: data class Option<A>(value: A?)
  • что вычисление завершится с ошибкой: data class Either<Error, A>(value: Pair<Error?, A?>)
  • что вычисление может быть ленивым: data class Defer<A>(value: () -> A)
  • или асинхронным: java.util.concurrent.CompletableFuture<A>
  • или иметь функциональное состояние: data class State<S, A>(value: (S) -> Pair<S, A>)

Список вопросов, оставшихся неосвещенными:

  • аппликативные функторы — промежуточное звено между функторами и монадами
  • коллекции как монады
  • композиции разнотипных монад — стрелка клейсли, монадические трансформеры
  • sequence/traverse
  • монады как эффекты
  • монады и рекурсия, переполнение стека, trampolining
  • Tagless Final encoding
  • IO монада
  • и вообще весь зоопарк стандартных монад

Что дальше?
arrow-kt.io
typelevel.org/cats/typeclasses.html
wiki.haskell.org/All_About_Monads

Мой эксперимент — полноценное приложение в ФП стиле на Scala:
github.com/scf37/fpscala2

P.S. Хотел небольшую заметку, получилось как всегда.

Источник