有可能使用延续传递样式将此递归函数转换为尾递归吗？

Question

我最近写了一个ETL，它运行得很好。我想提醒自己如何使用免费monad，所以想转换我的ETL。注意：我的目的不是为了写一个更好的ETL，而是为了重新熟悉自由monad。在重新学习免费monad如何工作时，我对这个问题的主题进行了跟踪。

所以几个月前我问了一个related question。有人评论说我的递归函数可以使用延续传递样式进行尾递归。我无法弄清楚该怎么做。

一些示例代码：

type In1 = int
type In2 = int
type Out1 = int
type Out2 = int

type FaceInstruction<'a> =
| Member1 of (In1 * (Out1 -> 'a))
| Member2 of (In2 * (Out2 -> 'a))

let private mapI f = function
    | Member1 (x, next) -> Member1 (x, next >> f)
    | Member2 (x, next) -> Member2 (x, next >> f)

type FaceProgram<'a> =
| Free of FaceInstruction<FaceProgram<'a>>
| Pure of 'a

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

我试图使尾递归的功能是qazxsw poi

我的尝试看起来像

bind

我开始认为，事实上，不可能使这个尾部递归。类型

let rec bind2 (f: 'a -> FaceProgram<'b>) k  z : FaceProgram<'b> = 
    match z with
    |Pure x -> x |> f |> k
    |Free x -> bind2 ???

已经包含了一个延续，并且函数FaceInstruction<'a>修改了这个延续，所以现在尝试添加另一个延续mapI是我现在可以处理的两个延续之一！

Answer 1

实际上k实际上并不是一个递归函数，因为在堆栈中，在任何给定时间都不会有多次调用bind。

原因是因为bind和bind都没有叫mapI。注意它们如何在不深入堆栈的情况下立即退出。 bind称bind，但mapI根本不称任何功能（除了构造函数的mapI或Member1）。他们所做的是使用Member2和bind构建一个新的Free monad实例。 next必须被声明为bind，因为它需要自我引用将自己作为参数传递给rec。

它是需要作为尾递归实现的解释器，这应该不会太困难。