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

addition

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'
Raw view Test code New version

More information

Link:http://fssnip.net/3F
Posted:13 years ago
Author:Carsten König
Tags: tail recursion , continuations , tree