简单玫瑰树上的尾递归映射

Question

我正在努力将非平凡函数映射为尾递归。

即使是简单的玫瑰树

type Tree<'a> = 
    | Leaf of 'a
    | Branch of List<Tree<'a>>

有地图

let rec map : ('a -> 'b) -> Tree<'a> -> Tree<'b> = 
    fun f -> 
        function
        | Leaf a -> 
            f a 
            |> Leaf
        | Branch xs ->
            xs 
            |> List.map (map f) 
            |> Branch

（更不用说绑定了）

使这个尾递归看起来很痛苦，我看过 FSharpx 之类的例子，但它们不是尾递归的。我找到了这个

https://www.gresearch.co.uk/article/advanced-recursion-techniques-in-f/

但是基于连续性的最终示例的飞跃似乎完全针对他们的示例（最大），我似乎无法理解它。

是否有这个非常规范的示例的示例实现？

所以简单的一点就是这样

let map2 : ('a -> 'b) -> Tree<'a> -> Tree<'b> =
    fun f ta ->
        let rec innerMap : Tree<'a> -> (Tree<'b> -> Tree<'b>) -> Tree<'b> =
            fun ta cont ->
                match ta with
                | Leaf a ->
                    f a |> Leaf |> cont
        innerMap ta id

但我错过了分支的难点

Answer 1

如果您使用 link 中的建议，实施如下：

let rec mapB : ('a -> 'b) ->  Tree<'a> -> (Tree<'b>-> Tree<'b>) -> Tree<'b> = 
    fun f ta k -> 

        match ta with
        | Leaf a -> k (Leaf (f a))
        | Branch ys ->
                       let continuations = ys |> List.map (mapB f)
                       let final (list:List<Tree<'b>>) = k (Branch list)
                       Continuation.sequence continuations final

如您所见，叶子的情况很简单：应用 F，将其包装回叶子并应用延续。

对于Branch，我们生成了一些偏函数来映射分支中的children。我们利用 Continuation.sequence 为我们执行这些部分功能。然后我们获取结果，将其包装在一个分支中并应用（最终）延续。

基本测试：

let t = Branch ([Leaf 3; Leaf 4;Leaf 5;Branch([Leaf 6])])
let t4 = mapB (fun x->x+1) t id

printfn "%A" t4

产量

Branch [Leaf 4; Leaf 5; Leaf 6; Branch [Leaf 7]]

顺便说一句，你想做什么？运行具有数千种场景的蒙特卡洛模拟？我还没有运行进入堆栈溢出错误，即使你的原始实现也是如此。

简单玫瑰树上的尾递归映射

tail recursive map over simple rosetree

f#

tail-recursion