Composite pattern & continuation

Category:
Design patterns
Description: Composite pattern with continuation implementation to get the sum of all tree nodes. For more information, please go to http://en.wikipedia.org/wiki/Composite_pattern
Code:
type TreeStructure<'a> = 
| Node of 'a * TreeStructure<'a> * TreeStructure<'a>
| Leaf

let OtherCompositePatternSample5() =
let tree = Node(4, Node(2, Node(1, Leaf, Leaf), Node(3, Leaf, Leaf)),
Node(6, Node(5, Leaf, Leaf), Node(7, Leaf, Leaf)))
let FoldTree nodeF leafV t =
let rec Loop t cont =
match t with
| Node(x,left,right) -> Loop left (fun lacc ->
Loop right (fun racc ->
cont (nodeF x lacc racc)))
| Leaf -> cont leafV
Loop t (fun x -> x)

let SumTree = FoldTree (fun x l r -> x + l + r) 0
let InOrder = FoldTree (fun x l r -> l @ [x] @ r) []
let Height = FoldTree (fun _ l r -> 1 + max l r) 0
printfn "sum = %d" (SumTree(tree))
printfn "inorder = %A" (InOrder(tree))
printfn "height = %d" (Height(tree))

Execution Result:
sum = 28
inorder = [1; 2; 3; 4; 5; 6; 7]
height = 3

Last edited Sep 14, 2011 at 3:25 AM by ttliu2000, version 1

Comments

No comments yet.