haskell - 除了 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 的东西，我们可能会做很多事情。

例如，如果我们只想打印到标准输出，我们可能会说：

type PrintOnlyIO = String

main :: PrintOnlyIO
main = "Hello world!"

然后有一个 RTS（运行时系统）来评估字符串并打印它。这让我们可以编写任何 I/O 完全由打印到标准输出的 Haskell 程序。

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

type InteractIO = String -> String

main :: InteractIO
main = map toUpper

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

这要好得多，因为它可以让我们编写交互式程序。但与我们想要做的所有 IO 相比，它仍然非常有限，而且也很容易出错（如果我们不小心尝试将 stdin 读得太远，程序将一直阻塞，直到用户输入更多内容）。

我们希望能够做的不仅仅是读取标准输入和写入标准输出。下面是 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 sand的值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

关键是，我们不是在 main 开始时将响应的“惰性列表”作为一个大参数，而是发出一次接受一个参数的单独请求。

我们的程序现在只是一个普通的数据类型——很像一个链表，只是你不能正常遍历它：当 RTS 解释main时，有时它会遇到一个值，比如GetLine它包含一个函数；然后它必须使用 RTS 魔法从标准输入获取一个字符串，并将该字符串传递给函数，然后才能继续。练习：写interpret :: ContIO -> IO ()。

请注意，这些实现都不涉及“世界传递”。“世界传递”并不是 Haskell 中 I/O 的真正工作方式。GHC中类型的实际实现IO涉及一个称为 的内部类型 RealWorld，但这只是一个实现细节。

实际的 HaskellIO添加了一个类型参数，因此我们可以编写“产生”任意值的动作——所以它看起来更像data IO a = Done a | PutStr String (IO a) | GetLine (String -> IO a) | .... 这给了我们更多的灵活性，因为我们可以创建IO产生任意值的“动作”。

（正如 Russell O'Connor指出的那样，这种类型只是一个免费的 monad。我们可以Monad很容易地为它编写一个实例。）

---

那么，monads 是从哪里来的呢？事实证明，我们不需要MonadI/O，也不需要Monad状态，那我们为什么还需要它呢？答案是我们没有。类型 class 没有什么神奇之处Monad。

然而，当我们使用IOand State（以及列表和函数以及 Maybe和解析器和持续传递样式和 ...）足够长的时间时，我们最终会发现它们在某些方面的行为非常相似。我们可能会编写一个打印列表中每个字符串的函数，以及一个在列表中运行每个有状态计算并通过线程处理状态的函数，它们看起来非常相似。

因为我们不喜欢写很多看起来相似的代码，所以我们想要一种方法来抽象它；Monad事实证明这是一个很好的抽象，因为它让我们抽象出许多看起来非常不同的类型，但仍然提供了很多有用的功能（包括 中的所有内容Control.Monad）。

给定bindIO :: IO a -> (a -> IO b) -> IO band returnIO :: a -> IO a，我们可以在 Haskell 中编写任何IO程序而无需考虑 monad。但是我们最终可能会复制很多函数Control.Monad，比如mapMandforever和whenand (>=>)。

通过实现通用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

看看Haskell 的历史：在课堂上懒惰。它描述了在 monad 被发明之前在 Haskell 中进行 I/O 的两种不同方法：延续和流。

Answer 5

有一种称为功能响应式编程的方法，它将时变值和/或事件流表示为一流的抽象。我最近想到的一个例子是Elm（它是用 Haskell 编写的，语法类似于 Haskell）。

Answer 6

我很好奇 - 可以用纯函数式语言（理论上还是现实）处理 I/O 或状态的其他方式？

我只是补充一下这里已经提到的内容（注意：其中一些方法似乎没有，所以有一些“即兴名称”）。

具有免费描述或实现的方法：

• “正交指令” - 请参阅Maarten Fokkinga 和 Jan Kuper的另一种 I/O 方法。

• Pseudodata - 请参阅F. Warren Burton在函数式编程语言中具有引用透明度的非确定性。Dave Harrison在他的论文 《函数式实时编程：Ruth 及其语义学》中使用该方法来实现时钟，并在Lennart Augustsson、Mikael Rittri 和 Dan Synek的函数式珍珠论生成唯一名称中提供了名称；Hackage中也有一些库实现。

• 见证人- 见Tachio Terauchi 和 Alex Aiken 的见证副作用。

• 观察员- 请参阅Vipin Swarup、Uday S. Reddy 和 Evan Ireland的应用语言作业。

其他方法 - 仅供参考：

• 系统令牌：

  L.奥古斯特森。使用系统令牌的功能性 I/O。PMG 备忘录 72，查尔姆斯理工大学计算机科学系，S-412 96 Göteborg，1989 年。

• “效果树”：

  Rebelsky SA (1992) I/O 树和交互式惰性函数式编程。在：Bruynooghe M., Wirsing M. (eds) 编程语言实现和逻辑编程。PLILP 1992。计算机科学讲义，第 631 卷。Springer，柏林，海德堡。