除了Monads之外,还有哪些其他方式可以用纯函数语言处理？

Question

所以我开始围绕Monads(在Haskell中使用).我很好奇IO或状态可以用纯函数语言处理的其他方式(理论上或现实中).例如,有一种名为"mercury"的逻辑语言使用"效果打字".在诸如haskell之类的程序中,效果打字工作会如何？其他系统如何运作？

Answer 1

这里涉及几个不同的问题.

首先,IO和State非常不同的事情.State你自己很容易做到:只需要为每个函数传递一个额外的参数,并返回一个额外的结果,你就拥有了一个"有状态函数"; 例如,a -> b变成 a -> s -> (b,s).

这里没有任何神奇之处:Control.Monad.State提供一个包装器,使得处理方式的"状态动作" s -> (a,s)以及一堆辅助函数,但就是这样.

就其本质而言,I/O必须在其实现中具有一些魔力.但是在Haskell中有很多表达I/O的方法,不涉及"monad"这个词.如果我们按原样拥有一个无IO的Haskell子集,并且我们想从头开始创建IO,而不了解monad,我们可能会做很多事情.

例如,如果我们要做的就是打印到stdout,我们可能会说:

type PrintOnlyIO = String

main :: PrintOnlyIO
main = "Hello world!"

然后有一个RTS(运行时系统)来评估字符串并打印它.这让我们可以编写任何Haskell程序,其I/O完全由打印到stdout.

然而,这不是很有用,因为我们想要交互性!因此,让我们发明一种允许它的新型IO.想到的最简单的事情是

type InteractIO = String -> String

main :: InteractIO
main = map toUpper

这种IO方法允许我们编写从stdin读取并写入stdout的任何代码(interact :: InteractIO -> IO () 顺便说一下,Prelude附带了一个执行此操作的函数).

这要好得多,因为它可以让我们编写交互式程序.但是与我们想要做的所有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's your name?"
  : GetLine
  : case resps1 of
        Success : Str name : resps2 ->
            PutStrLn ("hi " ++ name ++ "!")
          : Exit

当我们编写时main,我们得到一个惰性列表参数并返回一个惰性列表作为结果.我们返回的惰性列表具有PutStrLn s和GetLine; 在我们产生(请求)值之后,我们可以检查(响应)列表的下一个元素,并且RTS将安排它作为对我们请求的响应.

有一些方法可以更好地使用这种机制,但正如你可以想象的那样,这种方法很快就变得非常尴尬.此外,它的错误倾向与前一个相同.

这是另一种方法,它更不容易出错,并且在概念上非常接近Haskell IO的实际行为:

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

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

关键是,不是将响应的"懒惰列表"作为主要开头的一个大论点,而是一次接受一个参数的个别请求.

我们的程序现在只是一个常规数据类型 - 很像链接列表,除了你不能正常遍历它:当RTS解释时main,有时它会遇到一个值GetLine,其中包含一个函数; 然后它必须使用RTS魔法从stdin获取一个字符串,并将该字符串传递给该函数,然后才能继续.练习:写interpret :: ContIO -> IO ().

请注意,这些实现都不涉及"世界传递"."世界传递"并不是I/O在Haskell中的工作原理.IOGHC中类型的实际实现涉及一个名为的内部类型 RealWorld,但这只是一个实现细节.

实际的Haskell IO添加了一个类型参数,因此我们可以编写"生成"任意值的动作 - 因此看起来更像data IO a = Done a | PutStr String (IO a) | GetLine (String -> IO a) | ....这为我们提供了更大的灵活性,因为我们可以创建IO产生任意值的" 行动".

(正如Russell O'Connor所指出的,这种类型只是一个免费的monad.我们可以Monad轻松地为它编写一个实例.)

那么monad在哪里进入呢？事实证明我们不需要MonadI/O,而且我们不需要Monad状态,那么为什么我们需要它呢？答案是我们没有.类型类没有什么神奇之处Monad.

但是,当我们使用IO和State(以及列表和函数以及 Maybe解析器和延续传递样式和...)足够长时间时,我们最终会发现它们在某些方面表现得非常相似.我们可能会编写一个函数来打印列表中的每个字符串,以及一个在列表中运行每个有状态计算并将状态线程化的函数,它们看起来非常相似.

既然我们不喜欢编写很多类似的代码,我们想要一种抽象方法; Monad事实证明它是一个伟大的抽象,因为它让我们抽象出许多看起来非常不同的类型,但仍然提供了许多有用的功能(包括所有内容Control.Monad).

鉴于bindIO :: IO a -> (a -> IO b) -> IO b和returnIO :: a -> IO a,我们可以IO在Haskell中编写任何程序,而无需考虑monad.但是,我们很可能最终复制了很多功能Control.Monad,比如mapM和forever和when和(>=>).

通过实现通用MonadAPI,我们可以像使用解析器和列表一样使用完全相同的代码来处理IO操作.这才是我们Monad上课的唯一原因- 捕捉不同类型之间的相似之处.

Answer 2

另一个主要方法是唯一性输入,如Clean.简短的故事是状态句柄(包括现实世界)只能使用一次,而访问可变状态的函数会返回一个新句柄.这意味着第一次调用的输出是秒的输入,迫使顺序评估.

效果类型在Haskell 的Disciple Compiler中使用,但据我所知,在GHC中启用它需要大量的编译器工作.我将把细节的讨论留给那些比我更了解情况的人.

Answer 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)

当您允许两个流进行通信时,这会变得很有趣.然后你得到自动机类别Auto:

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))

Answer 4

看看哈斯克尔的历史:与班级一起懒惰.它描述了在发明monad之前在Haskell中执行I/O的两种不同方法:continuation和streams.