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

habr.png

Всем привет.

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

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

interface Functor


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

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

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


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

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


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


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

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


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

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

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


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


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

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


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


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


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

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


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

Пример:


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

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


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

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


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

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

fun main(args: Array) {
    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(val f: (Connection) -> A) {
    fun  map(f: (A) -> B): DB = flatMap { a -> lift(f(a)) }
    fun  flatMap(f: (A) -> DB): DB = DB { conn ->
        f(this.f(conn)).f(conn)
    }
}

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

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

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

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

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


Глубока ли кроличья нора?


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


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

  • аппликативные функторы — промежуточное звено между функторами и монадами
  • коллекции как монады
  • композиции разнотипных монад — стрелка клейсли, монадические трансформеры
  • 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. Хотел небольшую заметку, получилось как всегда.

© Habrahabr.ru