代码之家 › 专栏 › 技术社区 › Chechy Levas

在F#中使用免费单子是否意味着启动时间更长,指令有限?

abstract-syntax-tree monads f# recursion

Chechy Levas · 技术社区 · 6 年前

我在读书 this excellent article 马克·希曼著。

在这篇文章中,他给出了一个简单的演示,说明如何使用自由单子来模拟使用纯函数的交互。

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

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

该函数是递归的。

考虑到这不是尾部递归,这是否意味着我包含的指令数量受到堆栈空间的限制,因为每次我添加指令时,它都必须展开整个内容才能添加它?
与上述类似,这是否意味着启动时间更长,因为每一条新指令都必须进一步向下添加?这也许可以忽略不计,但这不是问题的重点;我想理解的是理论,而不是实用性。
如果以上问题的答案是“是”,那么按照以下方式(按照您想要的顺序列出指令列表,然后按照相反的顺序处理列表,以便将每条指令添加到程序的顶部,而不是底部)的替代实现是否更可取?

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

1 回复 | 直到 6 年前

Tomas Petricek 6 年前

我认为前两个问题的答案是“视情况而定”——自由单子会带来一些开销,当然也会遇到堆栈溢出,但您可以始终使用一个避免这种情况的实现,如果您正在进行I/O,那么开销可能不会太大。

我认为自由单子更大的问题是它们太复杂了。它们可以让你解决一个问题(抽象出你如何使用大量的it操作运行代码),但代价是你让代码变得非常复杂。大多数时候,我认为你可以保留一个“功能内核”作为一个很好的可测试的纯部分和围绕它的“命令包装器”,它足够简单,你不需要对它进行测试和抽象。

自由单子是非常通用的建模方法,你可以使用更具体的表示。对于阅读和写作,你可以做:

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)

前两种情况很好,完全是尾部递归的。最后一个例子是tail recursive in runProgram ,但调用时不是尾部递归 f .这应该没问题,因为 F 只生成指令,不调用 运行程序 .它还使用慢速列表追加 @ ,但您可以通过使用更好的数据结构来解决这个问题(如果事实证明这是一个问题)。

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