是否可以使用连续传递样式将此递归函数转换为尾递归? [英] Is is possible to convert this recursive function to tail-recursive using continuation passing style?

问题描述

我最近写了一个ETL，它工作正常. 我想提醒自己如何使用免费的monad，因此想转换我的ETL. 注意:我的目的不是写更好的ETL，而是让自己重新熟悉免费的monad.在重新学习免费monad的工作原理时，我一直跟踪这个问题的主题.

I have recently written an ETL, which works just fine. I would like to remind myself how to use free monads, so would like to convert my ETL as such. Note: my intention here is not to write a better ETL, but to re-familiarize myself with free monads. In re-learing how free monads work, I got side tracked with the topic of this question.

所以我问了

So I asked a related question some months ago. Someone commented that my recursive function could be made tail-recursive using continuation passing style. I can't figure out how to do it.

一些示例代码:

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

The function I am trying to make tail recusrive is 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是我现在无法处理的两个延续之一！

I am starting to think that, in fact, it is not possible to make this tail recursive. The type FaceInstruction<'a> already includes a continuation, and the function mapI modifies that continuation, so now trying to add another continuation k is one of two more continuations than I can handle right now!

推荐答案

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

In reality bind is not actually a recursive function in the sense that in the stack there is never going to be more than one call to bind at any given time.

原因是因为bind和mapI都不调用bind.请注意，它们如何立即退出而不深入堆栈. bind调用mapI，但是mapI根本不调用任何函数(除了作为构造函数的Member1或Member2之外).他们要做的是使用bind和next组成一个新的Free monad实例.必须将bind声明为rec，因为它需要自我引用才能将自身作为参数传递给mapI.

The reason is because neither bind nor mapI call bind. Notice how they both exit immediately without going deeper into the stack. bind calls mapI but mapI does not call any function at all (apart from Member1 or Member2 which are constructor functions). What they do is compose a new Free monad instance using bind and next. bind has to be declared as rec because it needs a self-reference to pass itself as a parameter to mapI.

需要将解释器实现为尾递归，这应该不太困难.

It is the interpreter that needs to be implemented as tail recursive, which should not be too difficult.

这篇关于是否可以使用连续传递样式将此递归函数转换为尾递归?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！