Sunday, August 29, 2010

Binary Tree in F#

Tree is a basic data structure used almost everywhere in a programming language. The following is the my implementation of a binary tree.

type Element = int
type TreeType =
    | EmptyTree
    | Tree of TreeType * Element * TreeType

let rec iterate tree emptyF commonF=
    match tree with
        | EmptyTree -> emptyF
        | Tree(leftTree, node, rightTree) ->
            let l = iterate leftTree emptyF commonF
            let r = iterate rightTree emptyF commonF
            commonF l node r

let emptyF = "Empty"
let commonF l n r = System.String.Format("({0} {1} {2})", l, n, r)

let t = Tree (Tree (EmptyTree, 2, EmptyTree), 1 ,EmptyTree)
printfn "%A" (iterate t emptyF commonF)

the emptyF is a function to process the empty node. I already read in a F# book about "everything in F# is a function", the emptyF is good sample. I was originally thinking this is a string value, but actually it is a function returns a constant value.

The latest F# best practice suggests to use C# like function definition if this API will be invoked by a C# programmer. But I do not have this requirement for now.

No comments: