С какими другими способами можно справиться в чисто функциональном языке, кроме Monads?

Ответ 1

Здесь есть несколько различных вопросов.

Во-первых, IO и State - это разные вещи. State легко сделать самостоятельно: просто передайте дополнительный аргумент каждой функции и верните дополнительный результат, и у вас есть "функция состояния"; например, поверните a -> b в a -> s -> (b,s).

Здесь нет волшебства: Control.Monad.State предоставляет оболочку, которая делает работу с "действиями государства" формы s -> (a,s) удобной, а также как кучу вспомогательных функций, но что он.

I/O по своей природе должен иметь некоторую магию в своей реализации. Но есть много способов выражения ввода/вывода в Haskell, которые не включают слово "монада". Если бы у нас было IO-свободное подмножество Haskell as-is, и мы хотели изобрести IO из царапать, не зная ничего о монадах, есть много вещей, которые мы могли бы сделать.

Например, если все, что мы хотим сделать, это print to stdout, мы можем сказать:

type PrintOnlyIO = String

main :: PrintOnlyIO
main = "Hello world!"

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

Это не очень полезно, потому что мы хотим интерактивности! Так что придумайте новый тип IO, который позволяет это. Самое простое, что приходит на ум -

type InteractIO = String -> String

main :: InteractIO
main = map toUpper

Этот подход к IO позволяет нам писать любой код, который считывает из stdin и записывает в stdout (прелюдия поставляется с функцией interact :: InteractIO -> IO () что делает это, кстати).

Это намного лучше, так как позволяет писать интерактивные программы. Но это все еще очень ограниченный по сравнению со всеми IO, которые мы хотим сделать, а также вполне с ошибкой (если мы случайно попытаемся слишком далеко зайти в stdin, программа будет просто блокироваться, пока пользователь не наберет больше).

Мы хотим иметь возможность делать больше, чем читать stdin и писать stdout. Вот как ранние версии Haskell сделали I/O, приблизительно:

data Request = PutStrLn String | GetLine | Exit | ...
data Response = Success | Str String | ...
type DialogueIO = [Response] -> [Request]

main :: DialogueIO
main resps1 =
    PutStrLn "what your name?"
  : GetLine
  : case resps1 of
        Success : Str name : resps2 ->
            PutStrLn ("hi " ++ name ++ "!")
          : Exit

Когда мы пишем main, мы получаем аргумент ленивого списка и возвращаем ленивый список как результат. Ленточный список, который мы возвращаем, имеет значения, такие как PutStrLn s и GetLine; после получения значения (запроса), мы можем рассмотреть следующий элемент (ответ), и РТС будет обеспечивать, чтобы это было ответом на наши запрос.

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

Здесь другой подход, который гораздо менее подвержен ошибкам, и концептуально очень рядом с тем, как ведет себя Haskell IO:

data ContIO = Exit | PutStrLn String ContIO | GetLine (String -> ContIO) | ...

main :: ContIO
main =
    PutStrLn "what your name?" $
    GetLine $ \name ->
    PutStrLn ("hi " ++ name ++ "!") $
    Exit

Ключ состоит в том, что вместо того, чтобы принимать "ленивый список" ответов как один большой аргумент в начале основного, мы делаем индивидуальные запросы, которые принимают один аргумент за раз.

Наша программа теперь представляет собой обычный тип данных - много похоже на связанный список, кроме вы не можете просто обычным образом пересекать его: когда RTS интерпретирует main, иногда он встречает такое значение, как GetLine, которое содержит функцию; то он должен получить строка из stdin с использованием магии RTS и передать эту строку функции, прежде чем он сможет продолжить. Упражнение: Напишите interpret :: ContIO -> IO ().

Обратите внимание, что ни одна из этих реализаций не связана с "миром". "переходящий мир" на самом деле не работает, как работает I/O в Haskell. Настоящий реализация типа IO в GHC включает внутренний тип, называемый RealWorld, но это только деталь реализации.

Actual Haskell IO добавляет параметр типа, чтобы мы могли писать действия, которые "производите" произвольные значения, поэтому он больше похож на data IO a = Done a | PutStr String (IO a) | GetLine (String -> IO a) | .... Это дает нам больше поскольку мы можем создавать "действия IO", которые производят произвольные значения.

(Поскольку Рассел О'Коннор указывает, этот тип - просто свободная монада. Мы можем легко записать экземпляр Monad.)

Где монады входят в это, тогда? Оказывается, нам не нужно Monad для I/O, и нам не нужно Monad для состояния, так зачем нам это вообще нужно? ответ таков, что мы этого не делаем. Нет ничего волшебного в классе типа Monad.

Однако, когда мы работаем с IO и State (и списками и функциями и Maybe и парсеров и стиль продолжения и...) достаточно долго, мы в конечном счете, выясняют, что они ведут себя довольно аналогично в некотором роде. Мы можем написать функцию, которая печатает каждую строку в списке, и функцию, которая выполняется каждое вычисление состояния в списке и потоки состояния через, и они будут выглядят очень похожими друг на друга.

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

Учитывая bindIO :: IO a -> (a -> IO b) -> IO b и returnIO :: a -> IO a, мы мог написать любую программу IO в Haskell, не думая о монадах. Но мы, вероятно, закончили бы тиражирование многих функций в Control.Monad, например, mapM и forever и when и (>=>).

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

Ответ 2

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

Впечатывание эффекта используется в Disciple Compiler для Haskell, но, насколько мне известно, потребуется значительная работа компилятора, чтобы включить его, скажем, в GHC. Я оставлю обсуждение деталей тем, кто лучше информирован, чем я.

Ответ 3

Ну, во-первых, что такое состояние? Он может проявляться как изменяемая переменная, которой у вас нет в Haskell. У вас есть только ссылки на память (IORef, MVar, Ptr и т.д.) И действия IO/ST, чтобы действовать на них.

Однако само состояние также может быть чистым. Чтобы подтвердить этот обзор, тип "Поток":

data Stream a = Stream a (Stream a)

Это поток значений. Однако альтернативный способ интерпретировать этот тип - изменяющееся значение:

stepStream :: Stream a -> (a, Stream a)
stepStream (Stream x xs) = (x, xs)

Это становится интересным, когда вы разрешаете двум потокам общаться. Затем вы получаете автомат категории Авто:

newtype Auto a b = Auto (a -> (b, Auto a b))

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

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

data LS a b =
    forall s.
    LS s ((a, s) -> (b, s))

Ответ 4

Взгляните на История Хаскелла: быть ленивым с классом. Он описывает два разных подхода к выполнению операций ввода-вывода в Haskell, прежде чем были изобретены монады: продолжения и потоки.

Ответ 5

Существует подход под названием Functional Reactive Programming, который представляет изменяющиеся во времени значения и/или потоки событий как абстракцию первого класса. Недавним примером, который приходит мне на ум, является Elm (он написан в Haskell и имеет синтаксис, подобный Haskell).

Ответ 6

Это не может быть (не если под "состоянием" вы подразумеваете "I/O или изменяемое поведение переменной, как на процедурном языке" ). Во-первых, вы должны понять, откуда берется использование монадов для изменяемых переменных или ввода-вывода. Несмотря на распространенное мнение, монадический ввод-вывод не происходит на таких языках, как Haskell, но с таких языков, как ML. Eugenio Moggi разработал оригинальные монады при изучении использования теории категорий для денотационной семантики нечистых функциональных языков, таких как ML. Чтобы понять, почему, считайте, что монада (в Haskell) может быть разделена на три свойства:

• Существует различие между значениями (в Haskell, типа a) и выражениями (в Haskell, типа IO a).
• Любое значение может быть преобразовано в выражение (в Haskell путем преобразования x в return x).
• Любая функция над значениями (возвращающая выражение) может быть применена к выражению (в Haskell, вычисляя f =<< a).

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

• Выражение, подобное print "Hello, world!\n", может иметь побочные эффекты, но его значение, например (), не может. Поэтому нам нужно провести различие между двумя случаями в денотационной семантике.
• Значение, например 3, может использоваться везде, где требуется выражение. Поэтому нашей денотационной семантике нужна функция, чтобы превратить значение в выражение.
• Функция принимает значения в качестве аргументов (формальные параметры для функции на строгом языке не имеют побочных эффектов), но могут применяться к выражению. Таким образом, нам нужен способ применения (выражения) возвращающей функции к выражению.

Таким образом, любая денотационная семантика для нечистого функционального (или процедурного) языка будет иметь структуру монады под капотом, даже если эта структура явно не используется при описании того, как I/O работает на языке.

Как насчет чисто функциональных языков?

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

• Monadic I/O
• Продолжения
• Уникальность/линейные типы
• Диалоги

Монадический ввод-вывод очевиден. Продолжение на основе ввода-вывода выглядит следующим образом:

main k = print "What is your name? " $
    getLine $ \ myName ->
    print ("Hello, " ++ myName ++ "\n") $
    k ()

Каждое действие ввода-вывода принимает "продолжение", выполняет его действие, а затем хвостовые вызовы (под капотом) - продолжение. Итак, в приведенной выше программе:

• print "What is your name? " выполняется, затем
• getLine выполняется, затем
• print ("Hello, " ++ myName ++ "\n") выполняется, затем
• k работает (который возвращает управление ОС).

Монада продолжения является очевидным синтаксическим улучшением вышеизложенного. Более важно, семантически, я могу видеть только два способа сделать работу ввода-вывода в приведенном выше примере:

• Сделать действия ввода/вывода (и продолжения) возвращать "тип ввода/вывода", описывающий ввод-вывод, который вы хотите выполнить. Теперь у вас есть монада ввода-вывода (продолжение на основе монады) без оболочки newtype.
• В результате действия I/O (и продолжения) возвращают то, что по существу (), и делают ввод/вывод как побочный эффект вызова отдельных операций (например, print, getLine и т.д.), Но если оценка выражения на вашем языке (что имеет в виду правая часть определения main выше) является побочным эффектом, я бы не считал это чисто функциональным.

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

main w0 = let
        w1 = print "What is your name? " w0
        (w2, myName) = getLine w1
        w3 = print $ "Hello, " ++ myName ++ "!\n"
    in w3

Разница между линейными типами и типами уникальности заключается в том, что в линейных типах результат должен быть w3 (он должен быть типа World), тогда как в типах уникальности результат может быть чем-то вроде w3 `seq` () вместо. w3 нужно просто оценить для ввода/вывода.

Опять же, государственная монада является очевидным синтаксическим улучшением вышеизложенного. Более важно, семантически, у вас снова есть два варианта:

• Сделайте операции ввода-вывода, такие как print и getLine, строгие в аргументе World (так что предыдущая операция выполняется сначала и боковая (так что операции ввода-вывода происходят как побочные, эффект их оценки). Опять же, если у вас есть побочные эффекты оценки, на мой взгляд, что на самом деле не чисто функциональный.
• Сделать тип World фактически представляющим собой ввод-вывод, который необходимо выполнить. Это имеет ту же проблему, что и реализация GHC IO с хвостовыми рекурсивными программами. Предположим, что мы изменим результат main на main w3. Теперь main хвост вызывает себя. Любая функция, вызывающая хвост, на чисто функциональном языке, не имеет значения (это просто бесконечный цикл); это основной факт о том, как денотационная семантика рекурсии работает на чистом языке. Опять же, я бы не рассматривал какой-либо язык, который нарушил это правило (особенно для "специального" типа данных, такого как World), чтобы быть чисто функциональным.

Итак, действительно, уникальность или линейные типы a) создают программы, которые становятся более ясными/чистыми, если вы завершаете их в государственной монаде и b) на самом деле не являются способом делать ввод-вывод на чисто функциональном языке.

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

main resps = [
    PrintReq "What is your name? ",
    GetLineReq,
    PrintReq $ "Hello, " ++ myName ++ "!\n"
  ] where
    LineResp myName = resps !! 1

Однако вы заметите несколько недостатков этого подхода:

• Непонятно, как включать процедуры ввода-вывода в этот подход.
• Вам нужно использовать числовую или позиционную индексацию, чтобы найти ответ, соответствующий данному запросу, который является довольно хрупким.
• Нет очевидного способа охватить ответ только над действиями после его получения; если эта программа каким-то образом использовала myName перед выдачей соответствующего запроса getLine, компилятор согласился бы с вашей программой, но он был бы тупиком во время выполнения.

Простым способом решения всех этих проблем является объединение диалогов в продолжениях, например:

type Cont = [Response] -> [Request]
print :: String -> Cont -> Cont
print msg k resps = PrintReq msg : case resps of
    PrintResp () : resps1 -> k resps1
getLine :: (String -> Cont) -> Cont
getLine k resps = GetLineReq : case resps of
    GetLineResp msg : resps1 -> k msg resps1

Код теперь выглядит так же, как и код для продолжения, проходящего по сравнению с I/O, приведенным ранее. Фактически, диалоги являются отличным типом результата для ваших продолжений в системе ввода-вывода на основе продолжения или даже в монадической системе ввода-вывода на основе monad. Однако, обратившись к продолжениям, применяется тот же самый аргумент, поэтому мы видим, что даже если система времени выполнения использует диалоги внутри, программы все равно должны записываться для ввода/вывода в монадическом стиле.