26 people like it.

# sum the nodes in a (not-binary) tree using continuations

you can easily find how to use continuations to iterate over a binary tree but what if the count of children for each node is not known at design time? It's not so obvious how to do this in order to get a tail-recursive method. This short snippet shows how to do this to sum the values of every leaf. The second part demonstrates a general approach for other operations than addition.

## definition of the tree

 ```1: 2: 3: ``` ``````type MultiTree<'a> = | Leaf of 'a | Node of MultiTree<'a> list ``````

 ```1: 2: 3: 4: 5: 6: 7: 8: 9: ``` ``````let sumMultiTree tree = let rec sumTree node cont = match node with | Leaf i -> cont i | Node chs -> match chs with | [] -> cont 0 | n::ns' -> sumTree n (fun e -> sumTree (Node ns') (fun e' -> cont (e + e'))) sumTree tree (fun r -> r) ``````

## general operation

 ``` 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: ``` ``````let opMultiTree f neutral tree = let rec opTree node cont = match node with | Leaf a -> cont a | Node chs -> match chs with | [] -> cont neutral | n::ns' -> opTree n (fun e -> opTree (Node ns') (fun e' -> cont (f e e'))) opTree tree (fun r -> r) let sumMultiTree' = opMultiTree (+) 0 ``````
union case MultiTree.Leaf: 'a -> MultiTree<'a>
union case MultiTree.Node: MultiTree<'a> list -> MultiTree<'a>
type MultiTree<'a> =
| Leaf of 'a
| Node of MultiTree<'a> list

Full name: Script.MultiTree<_>
type 'T list = List<'T>

Full name: Microsoft.FSharp.Collections.list<_>
val sumMultiTree : tree:MultiTree<int> -> int

Full name: Script.sumMultiTree
val tree : MultiTree<int>
val sumTree : (MultiTree<int> -> (int -> 'a) -> 'a)
val node : MultiTree<int>
val cont : (int -> 'a)
val i : int
val chs : MultiTree<int> list
val n : MultiTree<int>
val ns' : MultiTree<int> list
val e : int
val e' : int
val r : int
val opMultiTree : f:('a -> 'a -> 'a) -> neutral:'a -> tree:MultiTree<'a> -> 'a

Full name: Script.opMultiTree
val f : ('a -> 'a -> 'a)
val neutral : 'a
val tree : MultiTree<'a>
val opTree : (MultiTree<'a> -> ('a -> 'b) -> 'b)
val node : MultiTree<'a>
val cont : ('a -> 'b)
val a : 'a
val chs : MultiTree<'a> list
val n : MultiTree<'a>
val ns' : MultiTree<'a> list
val e : 'a
val e' : 'a
val r : 'a
val sumMultiTree' : (MultiTree<int> -> int)

Full name: Script.sumMultiTree'