简单rosetree上的尾部递归映射

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/

但是，从基于连续性的最后一个示例开始的飞跃似乎相当符合他们的示例（max），我似乎无法理解它。

在某个地方是否有这个非常规范的示例的示例实现？

那么简单的部分应该是这样的

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

但我错过了branch的艰难时刻

Answer 1

如果您使用链接中的建议，则实现如下：

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，将其包装回叶子并应用延续。

对于分支，我们生成了许多部分函数，用于映射分支中的子级。我们利用连续性。为我们执行这些部分函数的序列。然后，我们获取结果，将其包装在分支中，并应用（最终）延拓。

基本测试：

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]]

顺便说一下，您想做什么？使用数千个场景运行Montecarlo模拟？即使使用您的原始实现，我也还没有遇到堆栈溢出错误。