是否可以使用连续传递样式将此递归函数转换为尾递归？

Question

我最近写了一个ETL，效果很好。我想提醒自己如何使用免费的 monad，所以我想这样转换我的 ETL。注意：我在这里的目的不是写一个更好的 ETL，而是让我自己重新熟悉免费的 monad。在重新学习自由 monad 如何工作时，我被这个问题的主题所吸引。

所以几个月前我问了一个。有人评论说我的递归函数可以使用连续传递样式进行尾递归。我不知道该怎么做。

一些示例代码：

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

我试图使尾递归的函数是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 修改了那个延续，所以现在尝试添加另一个延续 k 是我现在无法处理的两个延续之一！

Answer 1

实际上 bind 实际上并不是一个递归函数，因为在堆栈中，在任何给定时间对 bind 的调用永远不会超过一次。

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

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

是否可以使用连续传递样式将此递归函数转换为尾递归？

Is is possible to convert this recursive function to tail-recursive using continuation passing style?

recursion

f#

monads

tail-recursion