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

    Всем привет.

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

    Подробнее
    Реклама

    Комментарии 47

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

      а дальше идет:


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

      Никак не могу подружить это у себя в голове:(

        +3

        для функтора не определена операция его создания, для монады определена операция создания из константы. Как фабричный метод.

          +1

          Спасибо, так понятнее.

        +4
        По многочисленным статьям я уже выучил что такое монада и какие они бывают, что у нее должны быть методы return и bind, но все равно ничего не понимаю:) При этом Option, Either, Defer, Future и т.д. — вполне понятные с практической точки зрения типы данных.

          +1

          Именно поэтому в статье столько примеров. Монада — это абстракция над вычислением. Она скрывает процесс получения значений, позволяя сфокусироваться на обработке этих значений. Код для Option/Either/Defer/Future выглядит идентично, отличается лишь тип монады.

            +1
            Мне кажется, полезно все-таки не забывать, что у монады есть и другая сторона. Тот же Бекман еще много лет назад на канале C9 прекрасно излагал моноиды и монады просто в терминах функциональной композиции (я чуток упрощаю, конечно). И никаких return и bind. И все при этом понятно, и от типа можно полностью абстрагироваться. Эта другая сторона (происходящая из теории категорий, очевидно), она нам показывает, почему собственно монады могут комбинироваться, и что для этого нужно.

            Это не в порядке критики, такой подход как тут — он тоже вполне хорош, они друг друга дополняют.
              0

              Не подскажете, где можно почитать подробнее?

                0
                Не, то что я упоминал — это не почитать, это скорее посмотреть. C9 это канал Microsoft, если я не забыл, то он вот тут. А вот конкретно на видео Бекмана ссылку найти не смог, сорри. Тому видео уже наверное лет 10 будет. Но кажется мне, что вот это оно.
            0
            Я могу сравнить монаду с… промисом?
              0
              Нет. Promise даже не частный случай монады. Постараться, конечно, можно, и сделать так, чтобы обещания были обёрнуты в монаду, но это будут не те Promise, к которым Вы, скорее всего, привыкли.
                0

                js Promise почти является монадой. Единственная причина, почему нет — поддержка синтаксиса .then({then: ...})
                https://stackoverflow.com/questions/45712106/why-are-promises-monads

              +1

              На самом деле все просто. Монада — это интерфейс, который объединяет эти типы. Что общего у Option и Either? Ну, их оба можно создать, оба иногда нужно смаппить (например "если есть значение, прибавь к нему единичку"), а иногда значение такого типа нужно спроецировать на такой же тип (типичный пример, когда мы пытаемся из массива массивов получить один плоский массив. Отсюда и название flatMap. Если посмотреть чуть шире, станет понятно, что операция работает для любых монад, в том числе и Option).


              Вроде бы звучит вполне логично, нет?:) По сути это просто интерфейс. Типов которые вот такие штуки умеют. А дальше на это можно навертеть. Например, с помощью функции flatMap можно склеить два значения и написать map2. А с функций map2 можно рекурсивно вызвать на списке и получить map для списка. Нахрена оно такое надо? Ну например можно превратить List<Option<T>> в Option<List<T>>. Если есть хотя бы один нулл, то будет нулл, иначе будет коллекция результатов. То же самое с Either, например парсим список строк в числа, мы можем вместо списка результатов парсинга каждой отдельной строчки получить список результат от вектора, то есть либо вектор всех распаршеных чисел, либо первую ошибку (можно все ошибки получить, зависит от деталей реализации). Короче, дальше поверх этой абстракции можно писать всякие удобные композирующие штуки. Если работали со стримами (это где на коллекциях можно вызывать filter/map/...), то могли почувствовать, насколько это удобно. Реализовали интерфейс с парой методов типа "верни мне итератор", и получили кучу методов вроде фильтрации и группировок из коробки. Монада это как раз такой интерфейс.

              +6
              f(this.f(conn)).f(conn)

              WTF?
                0

                чего тут непонятного — мы вычисляем текущую монаду, результат вычисления передаем в f, получаем вторую монаду, вычисляем её на том же connection.


                Что касается именований, однобуквенные названия удобнее использовать в композиции. Вот так было бы слишком тяжеловесно:


                flatMapOperation(this.operation(conn)).operation(conn)

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

                    Надеюсь в основном при использовании ФП-языков и ФП подходов так не пишут
                      0
                      А что плохого в однобуквенном, не вообще, а в том частном случае, когда мы можем абстрагироваться от конкретных функций? Такое обозначение наоборот помогает/заставляет абстрагироваться — мы лучше понимаем, что никакого конкретного фиксированного смысла у этой функции нет, и она может быть вообще любой, пока сигнатура соответствует.

                      Вас же надеюсь не смущает, когда в математике используется символ суммы, и индексы/пределы суммирования практически всегда называются скажем i и N?

                      >Надеюсь в основном при использовании ФП-языков и ФП подходов так не пишут
                      Это зависит от того, что вы делаете. Если вы пишете реализацию монады Option, то вам до лампочки, что там за функции в map и flatMap, и назвать их f или g более чем нормально и правильно.

                      А если вы пользуетесь этой же монадой в «прикладном» коде — эти функции обычно будут иметь вполне определенный смысл (а с ним вероятно и название — хотя все еще не обязательно).

                      Ну то есть, у вас есть List. Вы хотите сделать List, скажем, отформатировать все числа по определенному формату. Вы используете map, которому передаете функцию форматирования с сигнатурой Int->String. Для List смысл вашей функции не важен. А при взгляде с другой стороны это будет функция, называющаяся например format. Но опять же — если вы эту функцию format не используете повторно, она вполне может оказаться безымянной.

                        0
                        Ну потому что всегда есть возможность придумать осмысленное имя и улучшить читаемость кода. Тут у вас 2 разных f и это плохо читается. В каких-то случаях f может читаться нормально, но и там можно назвать function или mappingFunction или mapper. Где-то лучше назвать callback. Переменная должна отражать какую-то суть.
                          +1
                          callback отражает сущность ровно в той же степени, что и f.
                  0
                  Забейте. Столько шума вокруг этих монад, что складывается впечатление будто это что-то очень сложное и важное. Грубо говоря это просто класс с методами map и flatMap.
                    +1

                    pure забыли.


                    И это еще если забыть, что мы тут обсуждаем монаду над категорией Hask типов вашего языка. А ведь у этой категории, как минимум, есть интересные и полезные субкатегории.

                      +2

                      И тут вдруг, кто-то говорит, что функция (функциональная стрелка), тоже образует монаду, а приличный класс Set, реализующий множество уникальных элементов — не образует, хотя неполиморфные методы map и flatMap написать для него можно.
                      Монады, действительно, не что-то сложное, но что-то важное, и это не только класс с такими методами. Я поддерживаю автора статьи в том, что для программистов, монады это абстракция вычислений, как композиции.

                        +1
                        Set, реализующий множество уникальных элементов — не образует, хотя неполиморфные методы map и flatMap написать для него можно.

                        Образует. Просто не в Hask/Kotl/etc, а в подкатегории типов с порядком.


                        Вообще на более выразительных, чем хаскель, языках можно было бы поиграться с выражением таковых подкатегорий.

                      0

                      Сколько статей по функциональному программированию и нигде не нахожу проведения аналогий с другими языками. От того они все кажутся как совсем из другого мира, но ведь так не может быть.
                      Подскажите, пожалуйста, кто знает за C#:
                      1) Функтор = Делегат = Лямбда (возможно с неким замкнутым контекстом)?
                      2) Монада = условный Task с отдельными выходами ContinueWith под разный результат?
                      3) Монада Option = Nullable?

                        0

                        Специально делал примеры на Котлине — их можно механически перевести в С#, запустить и поиграться. Интерфейс монады очень прост — два метода, flatMap и lift. Сложно понять идеологию монады.


                        Приведенные примеры — это частные случаи функторов и монад, монада же — это абстракция. "Task — это монада" мало что дает для понимания, т.к. Task — слишком частный случай.


                        Функтор в общем случае — это как фабрика объектов. При этом неизвестно ни как создать эту фабрику, ни как получить из нее объект. Мы только знаем, что эта фабрика существует и можем сделать map, когда этот объект (или объекты) будут созданы. И функтор не обязан быть ни чистым, ни иммутабельным


                        Монада позволяет последовательно "соединять" такие фабрики, получая на выходе новую фабрику. Смысл в том, что можно писать логику, абстрагируясь от того, откуда собственно берутся данные.

                          0
                          Ну ёлки палки, не пишите глупости. Функтор, в общем случае, это никакая ни фабрика объектов. В лучшем случае, его можно считать аналогом контейнеров, но и это тоже не особо верно. Функтор — это преобразователь функций. Хотим мы функцию над int преобразовать в функцию над списками из int, с сохранением определённых свойств, для этого у нас есть функтор.

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

                            "Функтор — это преобразователь функций" AKA стрелок AKA морфизмов — это часть определения функтора из теории категорий. Достаточно бессмысленного определения с точки зрения практического применения. Посмотрите на мой пример MyRandom — где там преобразование функций? Где там категории? Какую они несут пользу программисту?


                            Про монаду можно согласиться, но....


                            Смысл моей статьи не в пересказе теории (таких статей и так полно), а в развороте этой теории в практическую плоскость.

                              0
                              Недостаточно назвать нечто map, чтобы это нечто автоматически стало частью функтора. Должны выполняться определённые свойства, которые и позволяют сохранять свойства компоновки. Я Kotlin плохо знаю, но если судить по тому, что у Вас происходит внутри MyRandom обращение к Random, map необходимые свойства не обеспечивает.

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

                                если речь про identity и композицию — то обеспечивает.

                          +1

                          1) Функтор — это не лямбда, т.к. мы не можем его вызвать и получить значение.
                          Это обертка над операцией с результатом определенного типа.
                          2) Монада — это обертка над типом в которую можно передать функцию над этим типом и получить монаду над результатом функции.
                          3) Нет* (Если аналог функции map написать руками, то будет)


                          Наиболее яркий представитель монады — IEnumerable
                          Есть методы:
                          Select = map
                          SelectMany = flatMap
                          Repeat(_, 1) = lift
                          Task тоже является монадой, так как содержит аналоги методов map, flatMap, lift

                            +1
                            2) Монада — это обертка над типом в которую можно передать функцию над этим типом и получить монаду над результатом функции.


                            Это самое понятное определение монады, которое я когда-либо слышал.
                              0

                              И именно это написано в сигнатуре функции bind (flatMap):
                              bind :: Monad m => m a -> (a -> m b) -> m b
                              И почему говорят, что Хаскелл это сложно? :)

                                0

                                Потому что это только начальный уровень. Вот пример из Хаскеля посложнее:


                                newtype Parser a = Parser { unParser :: String -> [(String, a)] }
                                instance Functor Parser where
                                  fmap f = Parser . (fmap . fmap . fmap) f . unParser
                            0
                            2) Проще монаду представить на примере класса IEnumerable<T>, который является реализацией монады List (но с оговоркой, что нет метода создания IEnumerable<T> из T, но его легко можно написать самому как экстеншон). В качестве flatMap выступает функция SelectMany.
                            3) Да, вы правы. В качестве flatMap здесь может быть либо оператор "?.", либо в общем виде функция вроде этой:
                            TResult Map<TInput, TResult>(this TInput o, Func<TInput, TResult> evaluator)
                                        where TResult : class
                                        where TInput : class
                            {
                                  if (o == null) return null;
                                  return evaluator(o);
                            }
                            
                              0

                              В C# на самом деле есть даже do-синтаксис для монад, просто он замаскирован для работы с коллекциями. Но при желании можно заставить работать и для своих типов :)


                              var res = from n in TryReadInt()
                                        from m in TryReadInt()
                                        select n + m;
                              0
                              fun <B> map(f: (A) -> B): Option<B> = flatMap { a -> lift(f(a)) }
                              Объясните, для чего нужена функция lift и почему нельзя написать flatMap { a -> Option(f(a)) }?
                              И второй вопрос, больше по Kotlin — я правильно понимаю, что можно написать так: flatMap { lift(f(it)) }?
                                0

                                1) можно, на практике так и делают. Отличие в том, что lift — это часть интерфейса (API) монады, а вызов конструктора — это деталь реализации.


                                2) можно. Я просто считаю, что нескоращенная версия выразительней.

                                0
                                ИМХО, для лайтового введения в тему слишком много небрежного написано.
                                Функтор — это абстракция над произвольным вычислением (computation), возвращающим результат типа А.
                                Функтор — это абстракция над способом структурной организации данных, экземпляр функтора F<A> — это какие-то данные типа A (вычисленные или ещё нет), которые как-то собраны в какую-то структуру данных F.
                                Абстракция над вычислением, как автор же говорит в комментариях, это монада.
                                аппаратный генератор случайных чисел
                                Функтор всегда параметризован типом. Чем тип генератора случайных чисел или самой последовательности случайных чисел параметризован? Поэтому вряд ли это пример функтора.
                                  0
                                  Функтор — это абстракция над способом структурной организации данных

                                  Вовсе нет. Функтор не обязан быть чистым или иммутабельным. Например, из функции InputStream.read(buff, off, len) можно сделать Functor.

                                  Функтор всегда параметризован типом.

                                  Да, типом данных, которые этот функтор генерирует. Не вижу проблемы, если честно

                                    +1
                                    Функтор не обязан быть чистым или иммутабельным.
                                    Не обязан, о чём я в следующем же предложении сказал.
                                    Есть функторы, которые не абстрагируют вычисления. Например, графы, деревья, аппликативный функтор ZipList. В целом, интерфейс Functor очень бедный, о чём в статье упоминалось, чтобы смотреть на функторы как абстракцию вычислений.
                                    Да, типом данных, которые этот функтор генерирует.
                                    Генератор случайных чисел генерирует числа. Он же не может генерировать строки, например, или бинарные деревья, иначе он уже не будет генератором чисел. А построить генератор экземпляров произвольного типа невозможно.
                                      0
                                      Он же не может генерировать строки, например, или бинарные деревья, иначе он уже не будет генератором чисел.

                                      Но это же функтор! Пример прямо из статьи — как из генератора случайных чисел сделать генератор случайных строк той же случайности.

                                  0
                                  Как же я, оказывается, привык видеть [ ] вместо < >
                                    0

                                    я тоже, я тоже...

                                    +1
                                    В статье ничего не сказано о трех необходимых монадных законах. В результате некоторые читатели пришли к выводу, что монада — это класс или интерфейс с методами flat и map.

                                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                  Самое читаемое