26 people like it.
Like the snippet!

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