在 F# 中使用免费的 monad 是否意味着更长的启动时间和有限的指令？

Question

我正在阅读 Mark Seemann 的 this excellent article。

在其中，他简单演示了如何使用免费的 monad 来模拟使用纯函数的交互。

我对它的理解足以编写这样的程序，并且我可以欣赏这种方法的优点。不过有一段代码让我想知道其中的含义。

let rec bind f = function
    | Free instruction -> instruction |> mapI (bind f) |> Free
    | Pure x -> f x

函数是递归的。

鉴于这不是尾递归，这是否意味着我包含的指令数量受堆栈限制space，因为每次我添加指令时，它都必须打开整个指令才能添加是吗？
与上述类似，这是否意味着启动时间更长，因为每条新指令都必须进一步向下添加？它可能可以忽略不计，但这不是问题的重点；我试图理解理论，而不是实践。
如果上述问题的答案是 'Yes'，是否可以按照以下方式进行替代实施（按照您想要的顺序列出指令，然后以相反的顺序处理列表，以便每个指令被添加到程序的顶部，而不是深入底部）更好吗？

我可能（可能）错过了一些基本的东西，这意味着递归永远不必走得太远，请告诉我。

Answer 1

我认为前两个问题的答案是 "it depends" - 有一些与自由 monad 相关的开销，你当然可以运行进入堆栈溢出，但你总是可以使用一个实现避免了这种情况，如果你正在做 I/O，那么开销可能不会太糟糕。

我认为自由 monad 的更大问题在于它们过于复杂的抽象。它们可以让您解决一个问题（抽象出您如何运行通过大量迭代编写代码），但代价是您使代码变得非常复杂。大多数时候，我认为你可以只保留 "functional core" 作为一个很好的可测试的纯部分和 "imperative wrapper" 围绕它，这很简单，你不需要测试它和抽象它。

自由单子是对此进行建模的非常通用的方式，您可以使用更具体的表示。对于阅读和写作，你可以这样做：

type Instruction = 
  | WriteLine of string
  | ReadLine of (string -> Instruction list)

如您所见，这不仅仅是一个简单的列表 - ReadLine 很棘手，因为它需要一个函数，当使用来自控制台的字符串调用时，该函数会产生更多指令（可能，或者可能不会，取决于这个字符串):

let program = 
  [ yield WriteLine "Enter your name:"
    yield ReadLine (fun name ->
      [ if name <> "" then
          yield WriteLine ("Hello " + name) ] ) ]

这表示 "Hello " 但仅当您输入非空名称时，它显示说明如何取决于您阅读的名称。运行程序的代码如下所示：

let rec runProgram program = 
  match program with 
  | [] -> ()
  | WriteLine s :: rest ->
      Console.WriteLine s
      runProgram rest
  | ReadLine f :: rest ->
      let input = Console.ReadLine()
      runProgram (f input @ rest)

前两种情况很好并且完全尾递归。最后一种情况在runProgram中是尾递归，但在调用f时就不是尾递归了。这样应该没问题，因为f只生成指令，不会调用runProgram。它还使用慢速列表追加 @，但您可以通过使用更好的数据结构来解决这个问题（如果它实际上是一个问题）。

自由 monad 基本上是对此的抽象 - 但我个人认为他们走得太远了一步，如果我真的需要这个，那么像上面这样的东西 - 带有具体说明 - 是更好的解决方案，因为它更简单。

在 F# 中使用免费的 monad 是否意味着更长的启动时间和有限的指令？

Does using a free monad in F# imply a higher startup time and limited instructions?

monads

recursion

f#

abstract-syntax-tree