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

Всем привет.

После четырех лет программирования на 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, содержащее в себе некоторое количество случайных бит. Наш интерфейс в Котлине так просто использовать не получится (но при желании можно ^[1]), поэтому напишем 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 ^[2]
typelevel.org/cats/typeclasses.html ^[3]
wiki.haskell.org/All_About_Monads ^[4]

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

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

Автор: Scf

Источник ^[6]