Pages

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?

Sunday, August 29, 2010

General Tree in F#

In the previous post, we have a binary tree representation. The following is a general way to represent the tree.


type CommonTreeType =
    | EmptyTreeNode
    | CommonTreeNode of Element * CommonTreeType list


let rec iterateCommonTree tree emptyF commonF =
    match tree with
        | EmptyTreeNode -> emptyF
        | CommonTreeNode(n, children) ->
            let childResult = children |> Seq.map (fun tree->iterateCommonTree tree emptyF commonF)
            commonF n childResult

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.

Thursday, August 19, 2010

Use Style to keep the WPF tree's selection state

< TreeView.Resources >
< Style TargetType="{x:Type TreeViewItem}" >
                     < Setter Property="IsExpanded" Value="{Binding IsExpanded, Mode=TwoWay}"/ >
                     < Setter Property="IsSelected" Value="{Binding IsSelected, Mode=TwoWay}"/ >
                  < /Style>
< / TreeView.Resources >

also need to put event handler:


private void OnTreeViewItemExpanded(object sender, RoutedEventArgs e)
        {
            TreeViewItem tvi = e.OriginalSource as TreeViewItem;
            tvi.IsSelected = true;
            if (tvi.IsExpanded)
                tvi.Focus();
        }

Saturday, August 14, 2010

Functional programming in C#

I got an interview question from my colleague on day about how to convert a 1D array to 2D array. It is simple, but I want to make the implementation more functional. I do not know why, but just does not like For loop since I started to use F#.


var arr = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
var result1 = new int[3, 3];
var list = arr.Select< int, Action< int[,] > >((number, index) => (arr0) => arr0[index % 3, (int)(index / 3)] = number);
 foreach (var item in list)
          item.Invoke(result1);

From the LINQ select, I got a list of operation (or lambda) to each element in the array. I find this way is more interesting if we have multi-core system. I build up the function once and each time the operation can be parallel as well.

Get Words in a text using functional way

how to get the word in a text string? The following is the LINQ resolution. Maybe it is scary, but I like this way to think about the problem.

string txt = "abc efg ghi\t abc\n\n123\t efg 345\n";

var result = txt.Split(new char[] { '\r', '\n' }, StringSplitOptions.RemoveEmptyEntries)
                            .SelectMany((str, lineNumber) => str.Select((ch, i) => new { Ch = ch, Index = i })
                                                                .Where(item => Char.IsWhiteSpace(item.Ch) || item.Index==0)
                                                                .Select(item => new { Index = item.Index, CharList = str.Skip(item.Index==0 ? 0 : item.Index + 1).TakeWhile(ch => !Char.IsWhiteSpace(ch)).ToArray() })
                                                                .Select(item => new { Line=lineNumber, Offset = item.Index==0 ? 0 : item.Index+1, Word = new String(item.CharList) })
                                                                .Where(item => !String.IsNullOrWhiteSpace(item.Word)));

the idea is simple:

for each line, we do the following process:


  • index each character
  • find all index whose character is whitespace, this index indicates the start character of a word
  • using this index to take the character till meet another whitespace
This approach  might be the most efficient way to process this problem, but it is a good exercise to use LINQ.

Wednesday, August 11, 2010

New way to compute - Accelerator and GPGPU

Microsoft Research release the GPGPU library for .NET user. You can use it and increase your program's performance. The good part is that it is good for C# and F#.

The home page is:
http://research.microsoft.com/en-us/projects/accelerator/

There is a wiki page about it.
http://blogs.msdn.com/b/satnam_singh/default.aspx?wa=wsignin1.0