tail recursive map over simple rosetree

user_2088029 0
Viewed 118

I'm struggling with mapping non trivial function to be tail recursive.

take even the simple rosetree

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

with map

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

(let alone bind)

making this tail recursive seems quite painful, I've looked at examples in things like FSharpx, but they arent tail recursive. I have found this

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

but the leap from the final example based on continuities seems quite bespoke to their example (of max), I can't seem to get my head around it.

is there an example implementation of this pretty canonical example somewhere?

so the simple bit would be something like this

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

but I'm missing the hard bit with branch

tail-recursion f#
1 Answers

If you use the suggestion from your link the implementation is as follows:

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

As you've noticed the case for the leaf is straightforward: apply F, wrap it back into a Leaf and apply the continuation.

As for the Branch, we generate a number of partial functions that map the children in the branch. We leverage Continuation.sequence which executes these partial functions for us. We then take the result, wrap it in a Branch and apply the (final) continuation.

A basic test:

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

printfn "%A" t4

yields

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

On a side note what are you trying to do? run Montecarlo simulations with thousands of scenarios? I have yet to run into a stack overflow error even with your original implementation.

user_78462760
Related