Подтвердить что ты не робот

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

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

4b9b3361

ОТВЕТЫ

Ответ 1

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

  • Мы хотим запрограммировать только с помощью функций. ( "функциональное программирование (FP)" в конце концов).

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

    f(x) = 2 * x

    g(x,y) = x / y

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

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

  • Другие проблемы: некоторые функции могут выйти из строя (т.е. g(2,0), делить на 0). В FP нет исключений (исключение не является функцией). Как мы его решаем?

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

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

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

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

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

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

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

  • Замечательные проблемы, которые могут быть решены с помощью этого метода:

    • имеющий глобальное состояние, которое может использовать каждая функция в последовательности функций ( "программа" ): solution StateMonad.

    • Нам не нравятся "нечистые функции": функции, которые дают разные выходные данные для одного входа. Поэтому отметьте эти функции, чтобы они вернули значение с тегами/коробкой: IO monad.

Общее счастье!

Ответ 2

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

Haskell не нуждается в абстракции монады. Нет необходимости выполнять IO на чистом языке. Тип IO позаботится об этом просто отлично. Существующий монадический десурагирование блоков do можно заменить десурагированием на 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 формирует математическую конструкцию, известную как category. Но есть и другие способы формирования категорий. Например, категория Kleisli позволяет дополнить объекты, которые должны быть дополнены. Категория Kleisli для Maybe будет состоять из (.) :: (b -> Maybe c) -> (a -> Maybe b) -> (a -> Maybe c) и id :: a -> Maybe a. То есть объекты в категории увеличивают (->) с помощью Maybe, поэтому (a -> b) становится (a -> Maybe b).

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

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

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

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

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

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

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

Ответ 3

Бенджамин Пирс сказал в 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 фактически не использует >>=, но он может). Однако невозможно безопасно покинуть монаду IO (т.е. Вы не можете выполнить действие IO и вернуть чистое значение - это значение всегда будет обернуто в монаду IO). Другим примером является изменяемые массивы: после того, как вы вышли из монады 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), но и равномерно обрабатывать определяемые пользователем типы данных и встроенные примитивы.

Ответ 4

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

Наивное построение системы ввода-вывода для 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

Не так уж плохо!

Итак, что все это связано с монадами?

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

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)

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

Во всяком случае, мы теперь достигли формулировки 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

Очевидно, что это не эффективная реализация IO, но она в принципе пригодна для использования.

Ответ 5

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

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

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

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

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

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

Ответ 6

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

Монада списка обычно используется для борьбы с детерминизмом. Операция bind выбирает один элемент списка (интуитивно все из них в параллельных мирах), позволяет программисту выполнять некоторые вычисления с ними, а затем объединяет результаты во всех мирах в один список (путем конкатенации или сглаживания вложенного списка). Вот как можно было бы определить функцию перестановки в монадической структуре 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)

Ниже приведен пример сеанса репликации:

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

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

Ответ 7

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

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

Смятение о монадах состоит в том, что, будучи настолько общим, т.е. механизмом для составления функций, они могут использоваться для многих вещей, что побуждает людей полагать, что монады - это состояние, об ИО и т.д., когда они только о "составление функций".

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