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?

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.

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();
        }

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.

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

Genetic Algorithm with F# - Fitness

Fitness is the most important part of the GA, it applies the pressure to individual and guide the population's evolutionary direction. I always image I could apply different fitness function during the different evolution stages. Now I can use the following function to do so:

let maxFitness population fitnessF =
    let best = Seq.maxBy (fun (c:ChromosomeType)->c.Fitness(fitnessF)) population
    best.Fitness(fitnessF)

I pass in the fitness function fitnessF every time.  Although the F# can know the type most of the time, but sometimes you have to tell a function what the parameter type is. In the function above, I use the maximum value as optimum, while some people prefer the minimum. If you like minimum better, just change the Seq.maxBy to Seq.minBy

Genetic Algorithm with F# - Population

When I design the population, I suddenly feel that maybe I do not need a type (or class). What is a population? It is a set of chromosomes. Population's property is the aggregation of some chromosome properties. It is like a human society. The individual is a physical identity; however, the society is only something in our mind, it is not a physical identity. I'd like to try to break the Object Oriented design this time to try something new. I have free-floating functions everywhere, which I do not need to tie them to a population or a chromosome. When I need them, I can readily grab a function and set of chromosomes. My gut feels that the population class is a barrier. Maybe I am wrong, but it does not hurt if I try.


let Population randomF populationSize chromosomeSize =  
    [for i in 1..populationSize do yield (new ChromosomeType(f=randomF,size=chromosomeSize))]

the randomF is a function to generate the initial loci in each value on the chromosome.

Genetic Algorithm with F# - Chromosome

Genetic Algorithm (GA) is my hobby. Let us define the chromosome structure first using F#. As a long time imperative programmer, I am still comfortable to use class.

First I define some random functions, it drives the GA's stochastic searching process. I would like to vision these function as a sequence of numbers rather than a single function. These random numbers is the driving force behind some chromosome-structure identifies on their way find the solution. We call these chromosome-structures population.

    let random = new System.Random((int)System.DateTime.Now.Ticks)
    let randomF() = random.Next()
    let randomFloatF() = random.NextDouble()

Now let us define the chromosome type in GA.

type ChromosomeType(f, size, ?converters) = 
    let initialF = f
    let mutable genos = [for i in 1..size do yield f()]
    let mutable genoPhenoConverters = converters
    member this.Clone() =
        let newValue =
            match (converters) with
                | Some(converters) -> new ChromosomeType(initialF, size, converters)
                | None -> new ChromosomeType(initialF, size)
        newValue.Genos &lt;- this.Genos
        newValue
    member this.Fitness(fitnessFunction) = this.Pheno |> fitnessFunction
    member this.Genos
        with get() = genos
        and set(value) = genos &lt;- value
    member this.Pheno
        with get() =
            match genoPhenoConverters with
                | Some(genoPhenoConverters) -> List.zip genoPhenoConverters genos |> List.map (fun (f,value) -> f value)                  
                | None -> this.Genos
    member this.Mutate(?mutationF) =
        let location = random.Next(Seq.length this.Genos)
        let F =
            match mutationF with
                | Some(mutationF) -> mutationF
                | None -> f
        let transform i v =
            match i with
                | _ when i=location -> F()
                | _ -> v
        this.Genos &lt;- List.mapi transform this.Genos
   


Most of the GA implementation only has one chromosome representation, my implementation has two

1. geno types are values, usually this is an integer array
2. pheno types are values computed from geno types.

I want to design the structure flexible enough so that I can put new mutation function any time I like. The good part about this structure is that you do not have to specify the type, again, the human language does not have type, neither does my program.

Composite a function list in F#

If I want to move away from imperative programming language, let us say it is C#, I have to find the equivalence in F#. I begin with getting rid of For-loop. 


I already know I can use Seq.sum, Seq.map, etc to replace most of the for-loop in my program. How about I need apply transform functions to a single data? Can I chain these functions? 


Fortunately the answer is yes. Let us say you have a list of functions f0, f1...fn to apply to a data. In a good math format: f0(f1(...fn(data))). I take functions as an input parameter and compositeFunction will give me the f0(f1..fn())).


    let compositeFunctions functions = Seq.fold (>>) (fun c->c) functions


you chain the functions by >> and (fun c->c) as starting point. 


The data will go into (fun c->c) first, which does nothing. Then the data go through each function in the function list.  

Euler Project Problem 1 with F#

Maybe no better place like Euler project problems suitable for starting my F# journey.


Although have been programming a computer more than a decade, I still find present something involve a loop a little bit of strange. Why I should say for (i = 0; i<100; i++) do something?! The difference between an imperative programming language and my human language decrease my productivity. I want something is more similiar to my human language to present my idea and  am eager to find a more natural way to write a program. At least F# solves the problem on how to present processing a data set.


Euler project problem 1 is to find the sum of all multiples of a 3 or 5 below 1000. I do not want to involve any for-loop or temporary variable in this case. Computer should be smart enough to translate my idea into a program. If there is a temporary variable needed for plumbing purpose, compiler should generate it for me, what I need is a sum of some numbers.


First of all, let us start to present a data set.


       { 1..999 } is the data set below 1000.


the problem only needs the number which is mulitple of 3 or 5, which means I need to filter it to get a sub-set. Let us do a definition of a number is multiple of 3 or 5.

    let isMultiple3Or5 i = i%3=0 || i%5=0

the good part about this definition is that you do not have to specify i  is what type, which is a big relief to my lazy brain. Data type is not part of my human language.

Now I got a data set and the fitering function, let F# to do the plumbing for me:
I use |> to input a data as a parameter into a function, the data is either I defined or some result from a function.

      { 1...999 } |> Seq.filter isMultiple3Or5 |> Seq.sum



{ 1...999 } as input into the Seq.filter function with isMultiple3Or5 as the filtering criteria. When the data comes out of the Seq.filter, only number which is multiple of 3 or 5 is left. The last step is to sum the new data set by applying Seq.sum. 

That's the way I like to think and talk to a computer, how about you?

the following is the full program:
let isMultiple3Or5 i = i%3=0 || i%5=0
let sum = {1..999} |> Seq.filter isMultiple3Or5 |> Seq.sum
printfn "%A" sum

Let us start from Functional Programming

F# is the language I was using since it was still in Microsoft Research. Not having used it that often, but I am still surprised to see that functional programming is so powerful. Every programmer today knows some well-known names, such as C++, Java; I'll start some posts trying to solve the same programming problem from a different angle.