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

Question

我正在阅读Mark Seemann的这篇优秀文章.

在其中,他简单地演示了如何使用自由monad来使用纯函数来模拟交互.

我理解它足以能够编写这样的程序,我可以理解这种方法的优点.虽然有一点代码,但我想知道它的含义.

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

该函数是递归的.

1. 鉴于这不是尾递归,这是否意味着我包含的指令数量受到堆栈空间的限制,因为每次我添加一条指令时,它必须打开整个东西才能添加它？
2. 与上述类似,这是否意味着更高的启动时间,因为每个新指令都需要进一步下载才能添加？它可能是微不足道的,但这不是问题的重点; 我试图理解这个理论,而不是实用性.
3. 如果上述问题的答案为"是",那么是否会有另一种实现方式(按照您希望的顺序列出指令列表,然后按相反的顺序处理列表,使每条指令都添加到顶部你的程序,而不是深入底部)更可取吗？

我可能(可能)错过了一些基本的东西,这意味着递归永远不会走得太远,请让我知道.

Answer 1

我认为前两个问题的答案是"它取决于" - 有一些与免费monad相关的开销,你当然可以遇到堆栈溢出,但你总是可以使用一个避免这种情况的实现,如果你正在做我/哦,那么开销可能也不算太差.

我认为免费monad的更大问题是它们只是太复杂的抽象.它们可以让您解决一个问题(抽象如何使用大量迭代运行代码),但代价是您使代码变得非常复杂.大多数时候,我认为你可以保持一个"功能核心"作为一个很好的可测试的纯粹部分和围绕它的"命令性包装",这很简单,你不需要测试它并抽象它.

免费monad是非常通用的建模方法,你可以使用更具体的表示.对于阅读和写作,你可以这样做:

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基本上是对此的抽象 - 但我个人认为他们走得太远,如果我真的需要这个,那么上面的东西 - 具体说明 - 是更好的解决方案,因为它更简单.