Tuesday, August 31, 2010

Seq.unfold and Tree

When I think about the Seq.unfold, I would like to vision it like an explosion. Seq.fold makes a seq to converge to a single value, while Seq.unfold make a single value to a sequence. It is like our universe exploded from a single point. We apply a function to a singe value and generate a sequence. After applying many other function, we transform this sequence to other format, they combine with each other and produce some results. Ok, enough for imagination. This post is to demonstrate Seq.unfold can be apply to a complex structure such as a tree.

We still use the tree definition in previous post:

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

let t = Tree (Tree(EmptyTree, 5, EmptyTree), 1 ,Tree(EmptyTree, 3, EmptyTree)) 

Now we define the function to explore this structure to a sequence.

let rec f context = 
    match context with
        | [] -> None
        | head::tail -> 
            match head with
                | EmptyTree -> f tail
                | Tree(l,n,r) -> Some(n, tail@[l;r])

let a = [t] |> Seq.unfold f

printfn "%A" a

I'd not say this approach a good functional way. Also, this is tree in order transverse, is there a way to do other two way to transverse a tree?

No comments: