Зачем нам нужны монады?

По моему скромному мнению, ответы на известный вопрос "Что такое монада?" особенно те, за кого проголосовали, попытайтесь объяснить, что такое монада, не объясняя, почему монады действительно необходимы . Могут ли они быть объяснены как решение проблемы?

Зачем нам нужны монады?

1. Мы хотим программировать только с использованием функций . («Функциональное программирование (ФП)» в конце концов).

2. Тогда у нас есть первая большая проблема. Это программа:

   f(x) = 2 * x

   g(x,y) = x / y

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

   Решение: составить функции . Если хочешь сначала, gа потом fпросто пиши f(g(x,y)). Таким образом, «программа» является функцией , а также: main = f(g(x,y)). Да, но ...

3. Больше проблем: некоторые функции могут не работать (т.е. g(2,0)делятся на 0). У нас нет «исключений» в FP (исключение не является функцией). Как мы это решаем?

   Решение: Давайте позволим функциям возвращать два вида вещей : вместо того, чтобы иметь g : Real,Real -> Real(функция из двух действительных в действительное число), давайте позволим g : Real,Real -> Real | Nothing(функция из двух действительных в (действительное или ничего)).

4. Но функции должны (быть проще) возвращать только одну вещь .

   Решение: давайте создадим новый тип данных, которые будут возвращаться, « тип бокса », который может быть реальным или быть просто ничем. Следовательно, мы можем иметь g : Real,Real -> Maybe Real. Да, но ...

5. Что происходит сейчас с f(g(x,y))? fне готов потреблять Maybe Real. И мы не хотим менять каждую функцию, с которой мы можем соединиться, gчтобы использовать a Maybe Real.

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

   В нашем случае: g >>= f(подключение / Compose gк f). Мы хотим >>=получить gвыходные данные, проверить их и, в случае, если они Nothingпросто не вызывают fи не возвращают Nothing; или наоборот, извлеките в штучной упаковке Realи кормить fего. (Этот алгоритм является просто реализацией >>=для Maybeтипа). Также обратите внимание, что >>=должно быть написано только один раз для «типа бокса» (другой ящик, другой алгоритм адаптации).

6. Возникают многие другие проблемы, которые могут быть решены с использованием этого же шаблона: 1. Используйте «коробку» для кодификации / хранения различных значений / значений, и такие функции gвозвращают эти «коробочные значения». 2. Иметь компоновщик / компоновщик, g >>= fчтобы помочь соединить gвывод fс входом, так что нам вообще не нужно ничего менять f.

7. Замечательные проблемы, которые могут быть решены с помощью этой техники:

   • имея глобальное состояние, что каждая функция в последовательности функций («программа») может совместно использовать: решение StateMonad.

   • Нам не нравятся «нечистые функции»: функции, которые дают разные выходные данные для одного и того же ввода. Поэтому давайте пометим эти функции, заставив их возвращать теговое / коробочное значение: IOmonad.

Всего счастья!

Ответ, конечно, «мы не делаем» . Как и во всех абстракциях, это не обязательно.

Haskell не нуждается в абстракции монады. Это не обязательно для выполнения ввода-вывода на чистом языке. IOТип заботится о том только штрафом сам по себе. Существующая монадическая desugaring из doблоков может быть заменена desugaring к bindIO, returnIOиfailIO как это определено в GHC.Baseмодуле. (Это не документированный модуль по взлому, поэтому мне придется указать на его источник документации). Так что нет, абстракция монады не нужна.

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

В функциональных языках самым мощным инструментом для повторного использования кода была композиция функций. Старый добрый (.) :: (b -> c) -> (a -> b) -> (a -> c)оператор чрезвычайно мощный. Это позволяет легко писать крошечные функции и склеивать их с минимальными синтаксическими или семантическими издержками.

Но есть случаи, когда типы работают не совсем правильно. Что вы делаете, когда у вас есть foo :: (b -> Maybe c)и bar :: (a -> Maybe b)? foo . barне проверяет, потому что bи Maybe bне одного типа.

Но ... это почти правильно. Вы просто хотите немного свободы. Вы хотите иметь возможность относиться так, Maybe bкак если бы это было в принципе b. Это плохая идея - просто относиться к ним как к одному типу. Это более или менее то же самое, что нулевые указатели, которые Тони Хоар, как известно, назвал ошибкой в ​​миллиард долларов . Поэтому, если вы не можете относиться к ним как к одному типу, возможно, вы найдете способ расширить механизм компоновки (.).

В этом случае важно действительно изучить теорию, лежащую в основе (.). К счастью, кто-то уже сделал это для нас. Оказывается, что сочетание (.)и idобразуют математическую конструкцию, известную как категория . Но есть и другие способы формирования категорий. Например, категория Клейсли позволяет немного дополнить составляемые объекты. Категория Клейсли для Maybeсостоит из (.) :: (b -> Maybe c) -> (a -> Maybe b) -> (a -> Maybe c)и id :: a -> Maybe a. То есть объекты в категории дополняют (->)с Maybe, так (a -> b)становится (a -> Maybe b).

И вдруг мы расширили возможности композиции до вещей, над которыми традиционная (.)операция не работает. Это источник новой силы абстракции. Категории Клейсли работают с большим количеством типов, чем просто Maybe. Они работают с каждым типом, который может собрать соответствующую категорию, подчиняясь законам категории.

1. Левая личность: id . f=f
2. Правильная идентичность: f . id=f
3. Ассоциативность: f . (g . h)=(f . g) . h

Пока вы можете доказать, что ваш тип подчиняется этим трем законам, вы можете превратить его в категорию Клейсли. И что в этом такого? Что ж, получается, что монады - это то же самое, что и категории Клейсли. Monad«ы returnтак же , как Клейсли id. Monad«s (>>=)не совпадает с Клейсли(.) , но это оказывается очень легко писать друг с точки зрения другого. И законы категорий такие же, как законы монад, когда вы переводите их через разницу между (>>=)и (.).

Так зачем переживать все это? Почему естьMonad абстракция в языке? Как я упоминал выше, это позволяет повторно использовать код. Он даже позволяет повторно использовать код в двух разных измерениях.

Первое измерение повторного использования кода происходит непосредственно от наличия абстракции. Вы можете написать код, который работает во всех случаях абстракции. Там весь пакет monad-loops , состоящий из циклов, которые работают с любым экземпляромMonad .

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

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

Бенджамин Пирс сказал в TAPL

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

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

Как @Carl и Sigfpe , вы можете оборудовать тип данных всеми вам операциями, не прибегая к монадам, классам типов или любым другим абстрактным вещам. Однако монады позволяют вам не только писать повторно используемый код, но и абстрагироваться от всех лишних деталей.

В качестве примера, скажем, мы хотим отфильтровать список. Самый простой способ - использовать filterфункцию:, filter (> 3) [1..10]которая равна[4,5,6,7,8,9,10] .

Несколько более сложная версия filter, которая также проходит аккумулятор слева направо,

swap (x, y) = (y, x)
(.*) = (.) . (.)

filterAccum :: (a -> b -> (Bool, a)) -> a -> [b] -> [b]
filterAccum f a xs = [x | (x, True) <- zip xs $ snd $ mapAccumL (swap .* f) a xs]

Чтобы получить все i, что i <= 10, sum [1..i] > 4, sum [1..i] < 25мы можем написать

filterAccum (\a x -> let a' = a + x in (a' > 4 && a' < 25, a')) 0 [1..10]

что равно [3,4,5,6].

Или мы можем переопределить nubфункцию, которая удаляет повторяющиеся элементы из списка, с точки зрения filterAccum:

nub' = filterAccum (\a x -> (x `notElem` a, x:a)) []

nub' [1,2,4,5,4,3,1,8,9,4]равно [1,2,4,5,3,8,9]. Список передается здесь как аккумулятор. Код работает, потому что можно оставить монаду списка, поэтому все вычисления остаются чистыми ( notElemна >>=самом деле не используются , но могут). Однако невозможно безопасно покинуть монаду ввода-вывода (т.е. вы не можете выполнить действие ввода-вывода и вернуть чистое значение - значение всегда будет заключено в монаду ввода-вывода). Другой пример - изменяемые массивы: после того, как вы оставили монаду ST, в которой находится изменяемый массив, вы больше не можете обновлять массив в постоянное время. Итак, нам нужна монадическая фильтрация из Control.Monadмодуля:

filterM          :: (Monad m) => (a -> m Bool) -> [a] -> m [a]
filterM _ []     =  return []
filterM p (x:xs) =  do
   flg <- p x
   ys  <- filterM p xs
   return (if flg then x:ys else ys)

filterMвыполняет монадическое действие для всех элементов списка, получая элементы, для которых возвращается монадическое действие True.

Пример фильтрации с массивом:

nub' xs = runST $ do
        arr <- newArray (1, 9) True :: ST s (STUArray s Int Bool)
        let p i = readArray arr i <* writeArray arr i False
        filterM p xs

main = print $ nub' [1,2,4,5,4,3,1,8,9,4]

печатает [1,2,4,5,3,8,9]как ожидалось.

И версия с монадой ввода-вывода, которая спрашивает, какие элементы возвращать:

main = filterM p [1,2,4,5] >>= print where
    p i = putStrLn ("return " ++ show i ++ "?") *> readLn

Например

return 1? -- output
True      -- input
return 2?
False
return 4?
False
return 5?
True
[1,5]     -- output

И в качестве окончательной иллюстрации, filterAccumможно определить с точки зрения filterM:

filterAccum f a xs = evalState (filterM (state . flip f) xs) a

с StateTмонадой, которая используется под капотом, будучи просто обычным типом данных.

Этот пример иллюстрирует, что монады позволяют не только абстрагировать вычислительный контекст и писать чистый повторно используемый код (благодаря компоновке монад, как объясняет @Carl), но также и обрабатывать пользовательские типы данных и встроенные примитивы единообразно.

Я не думаю, что это IOследует рассматривать как особенно выдающуюся монаду, но она, безусловно, одна из самых поразительных для начинающих, поэтому я буду использовать ее для своего объяснения.

Наивное построение системы ввода-вывода для Haskell

Самая простая мыслимая система ввода-вывода для чисто функционального языка (и на самом деле та, с которой начинал Haskell) заключается в следующем:

main₀ :: String -> String
main₀ _ = "Hello World"

С ленивостью этой простой подписи достаточно для создания интерактивных терминальных программ - хотя и очень ограниченных. Больше всего расстраивает то, что мы можем выводить только текст. Что, если мы добавим несколько более интересных выходных возможностей?

data Output = TxtOutput String
            | Beep Frequency

main₁ :: String -> [Output]
main₁ _ = [ TxtOutput "Hello World"
          -- , Beep 440  -- for debugging
          ]

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

Что ж, когда мы берем нашу main₁программу и просто передаем файл в процесс (используя средства операционной системы), мы практически реализуем чтение файла. Если бы мы могли запустить чтение файлов из языка Haskell ...

readFile :: Filepath -> (String -> [Output]) -> [Output]

Это будет использовать «интерактивную программу» String->[Output], передать ей строку, полученную из файла, и получить неинтерактивную программу, которая просто выполняет данную.

Здесь есть одна проблема: у нас нет понятия о том, когда файл читается. [Output]Список уверен , что дает хороший заказ к выходам , но мы не получили заказ , когда входы будут сделаны.

Решение: сделать входные события также пунктами в списке дел.

data IO₀ = TxtOut String
         | TxtIn (String -> [Output])
         | FileWrite FilePath String
         | FileRead FilePath (String -> [Output])
         | Beep Double

main₂ :: String -> [IO₀]
main₂ _ = [ FileRead "/dev/null" $ \_ ->
             [TxtOutput "Hello World"]
          ]

Хорошо, теперь вы можете заметить дисбаланс: вы можете прочитать файл и сделать вывод зависимым от него, но вы не можете использовать содержимое файла, чтобы принять решение, например, также прочитать другой файл. Очевидное решение: сделать результат входных событий также чем-то типа IO, а не просто Output. Это, конечно, включает в себя простой вывод текста, но также позволяет читать дополнительные файлы и т.д ..

data IO₁ = TxtOut String
         | TxtIn (String -> [IO₁])
         | FileWrite FilePath String
         | FileRead FilePath (String -> [IO₁])
         | Beep Double

main₃ :: String -> [IO₁]
main₃ _ = [ TxtIn $ \_ ->
             [TxtOut "Hello World"]
          ]

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

• main₃выдает полный список действий. Почему бы нам просто не использовать подпись :: IO₁, которая имеет это как особый случай?

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

data IO₂ = TxtOut String IO₂
         | TxtIn (String -> IO₂)
         | Terminate

main₄ :: IO₂
main₄ = TxtIn $ \_ ->
         TxtOut "Hello World"
          Terminate

Не плохо!

Так какое отношение все это имеет к монадам?

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

getTime :: (UTCTime -> IO₂) -> IO₂
randomRIO :: Random r => (r,r) -> (r -> IO₂) -> IO₂
findFile :: RegEx -> (Maybe FilePath -> IO₂) -> IO₂

Здесь, очевидно, есть образец, и нам лучше написать

type IO₃ a = (a -> IO₂) -> IO₂    -- If this reminds you of continuation-passing
                                  -- style, you're right.

getTime :: IO₃ UTCTime
randomRIO :: Random r => (r,r) -> IO₃ r
findFile :: RegEx -> IO₃ (Maybe FilePath)

Теперь это начинает казаться знакомым, но мы все еще имеем дело только с тонко замаскированными простыми функциями под капотом, и это рискованно: каждое «действие-значение» несет ответственность за фактическую передачу результирующего действия любой содержащейся функции (иначе поток управления всей программой легко нарушается одним плохим поведением в середине). Нам лучше сделать это требование явным. Что ж, оказывается, это законы монады , хотя я не уверен, что мы сможем сформулировать их без стандартных операторов связывания / объединения.

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

data IO₄ a = TxtOut String (IO₄ a)
           | TxtIn (String -> IO₄ a)
           | TerminateWith a

txtOut :: String -> IO₄ ()
txtOut s = TxtOut s $ TerminateWith ()

txtIn :: IO₄ String
txtIn = TxtIn $ TerminateWith

instance Functor IO₄ where
  fmap f (TerminateWith a) = TerminateWith $ f a
  fmap f (TxtIn g) = TxtIn $ fmap f . g
  fmap f (TxtOut s c) = TxtOut s $ fmap f c

instance Applicative IO₄ where
  pure = TerminateWith
  (<*>) = ap

instance Monad IO₄ where
  TerminateWith x >>= f = f x
  TxtOut s c >>= f = TxtOut s $ c >>= f
  TxtIn g >>= f = TxtIn $ (>>=f) . g

Очевидно, что это не эффективная реализация ввода-вывода, но в принципе это удобно.

Монады - это просто удобная структура для решения класса повторяющихся проблем. Во-первых, монады должны быть функторами (т.е. должны поддерживать отображение, не смотря на элементы (или их тип)), они также должны вызывать операцию привязки (или сцепления) и способ создания монадического значения из элемента type ( return). Наконец, bindи returnдолжны удовлетворять два уравнения (левая и правая тождества), также называемые законами монады. (В качестве альтернативы можно определить монады flattening operationвместо привязки.)

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

perm [e] = [[e]]
perm l = do (leader, index) <- zip l [0 :: Int ..]
            let shortened = take index l ++ drop (index + 1) l
            trailer <- perm shortened
            return (leader : trailer)

Вот пример сеанса repl :

*Main> perm "a"
["a"]
*Main> perm "ab"
["ab","ba"]
*Main> perm ""
[]
*Main> perm "abc"
["abc","acb","bac","bca","cab","cba"]

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

Монады служат в основном для объединения функций в цепочку. Период.

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

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

Теперь, одна интересная вещь о монадах, это то, что результат композиции всегда имеет тип «M a», то есть значение внутри конверта, помеченного «M». Эта особенность очень полезна для реализации, например, четкого разделения между чистым и нечистым кодом: объявляйте все нечистые действия как функции типа "IO a" и не предоставляйте никакой функции при определении монады IO для удаления " «значение изнутри« IO a ». В результате ни одна функция не может быть чистой и в то же время извлекать значение из «IO a», потому что нет способа получить такое значение, оставаясь чистым (функция должна быть внутри монады «IO», чтобы использовать такая ценность). (ПРИМЕЧАНИЕ: ну, нет ничего идеального, поэтому «смирительную рубашку IO» можно сломать с помощью «unsafePerformIO: IO a -> a»

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

Позвольте мне уточнить. У вас есть Int, Stringи Realи функции типа Int -> String, String -> Realи так далее. Вы можете легко комбинировать эти функции, заканчивая на Int -> Real. Жизнь хороша.

Затем однажды вам нужно создать новое семейство типов . Это может быть связано с тем, что вам нужно рассмотреть возможность возврата без значения ( Maybe), возврата ошибки ( Either), нескольких результатов ( List) и так далее.

Обратите внимание, что Maybeэто конструктор типа. Он принимает тип, любит Intи возвращает новый тип Maybe Int. Первое, что нужно запомнить: нет конструктора типов, нет монады.

Конечно, вы хотите использовать ваш конструктор типов в вашем коде, и вскоре вы закончите с такими функциями, как Int -> Maybe Stringи String -> Maybe Float. Теперь вы не можете легко комбинировать свои функции. Жизнь больше не хороша.

И вот когда монады приходят на помощь. Они позволяют вам снова комбинировать такие функции. Вам просто нужно изменить состав . для > == .