A foldBack function for Tree in F#

Question

I have a Tree type:

type Tree<'value> =
    | Node of value: 'value * children: ConsList<Tree<'value>>
    | Leaf of value: 'value

And a fold function for it:

let rec fold folder acc tree =
    let f = fold folder

    match tree with
    | Leaf value -> folder acc value
    | Node(value, children) -> ConsList.fold f (folder acc value) children

ConsList in case you need it:

type ConsList<'value> =
    | Cons of head: 'value * tail: ConsList<'value>
    | Empty

let rec fold folder acc lst =
    let f = fold folder

    match lst with
    | Empty -> acc
    | Cons (hd, tl) -> f (folder acc hd) tl

I need a foldBack function, meaning the function passes through the nodes from left to right from top to bottom, starting from the root.

I ended up on this:

let rec foldBack folder acc tree =
    let f = fold folder

    match tree with
    | Leaf value -> f acc value
    | Node(value, children) -> f value (f acc *children*)

Children with ** type is expected to be Tree<'a> but has type ConsList<Tree<Tree<'a>>>

Answer 1

For back folds it is common to have accumulator as a function which receives intermediate folded value of sub-branch and returns new folded value with respect to the current element. Thus iterating through the tree normally from top to bottom you literally construct the computation which when receives the terminal elements will compute the bottom to top fold. You can look for continuation passing style topic more yourself. This approach is also used to optimize for tail-call recursion because function you accumulating is the chain of function objects which doesn't affect stack.

Here is what I've done so far (I replaced ConsList with normal List type, because otherwise it would require to create the foldBack for it as well, which you can try yourself)

    type ConsList<'t> = 't list
    type Tree<'value> =
        | Node of value: 'value * children: ConsList<Tree<'value>>
        | Leaf of value: 'value
    
    let foldBack seed folder (tree: 't Tree) =

        let rec fold acc tree =
            match tree with
            | Leaf value -> 
                let acc' inner = folder (acc inner) value
                acc'
            | Node (value, children) -> 
                let acc' inner =  List.foldBack (fold acc) children inner
                let acc'' inner = folder (acc' inner) value
                acc''

        fold id tree seed

    let treeSample = 
        Node ("node1", [
                Leaf "subnode1";
                Node ("node1.1", [
                    Leaf "subnode1.1";
                        Node("node1.2", [
                            Leaf "leaf1.2"
                        ])
                    ])
            ])

    treeSample|>foldBack ">>seed<<" (fun value acc -> $"{value} -> {acc}" )

val it: string = ">>seed<< -> leaf1.2 -> node1.2 -> subnode1.1 -> node1.1 -> subnode1 -> node1"