Sunday, December 12, 2010

F# project and AssemblyInfo

put the following code into your project and make this file's extension from .fs to .fsx.

.fs won't build, but .fsx will build.

open System.Reflection;
open System.Runtime.CompilerServices;
open System.Runtime.InteropServices;

// General Information about an assembly is controlled through the following
// set of attributes. Change these attribute values to modify the information
// associated with an assembly.
[ < assembly: AssemblyTitle("BB from © AA") > ]
[ < assembly: AssemblyDescription("BB") > ]
[ < assembly: AssemblyConfiguration("") > ]
[ < assembly: AssemblyCompany("AA") > ]
[ < assembly: AssemblyProduct("BB") > ]
[ < assembly: AssemblyCopyright("© AA. All rights reserved.") > ]
//[ < assembly: AssemblyTrademark("") > ]
[ < assembly: AssemblyCulture("") > ]

// Setting ComVisible to false makes the types in this assembly not visible
// to COM components.  If you need to access a type in this assembly from
// COM, set the ComVisible attribute to true on that type.
[ < assembly: ComVisible(false) > ]

// The following GUID is for the ID of the typelib if this project is exposed to COM
[ < assembly: Guid("c95f0dd1-9182-4d48-8bc2-b6cc2bca17bc5") > ]

// Version information for an assembly consists of the following four values:
//      Major Version
//      Minor Version
//      Build Number
//      Revision
// You can specify all the values or you can default the Build and Revision Numbers
// by using the ‘*’ as shown below:
// [assembly: AssemblyVersion("1.0.*")]
[ < assembly: AssemblyVersion("1.0.1010.0032") > ]
[ < assembly: AssemblyFileVersion("1.0.1010.0032") > ]

I have to say I was wrong, you can still use it as a .fs file. But .fsi file should still work. 

Sunday, November 28, 2010

Default Company name for Visual Studio 2010 project

you have to change:

  • HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows NT\CurrentVersion\RegisteredOrganization (for 32-bit version)
  • HKEY_LOCAL_MACHINE\SOFTWARE\Wow6432Node\Microsoft\Windows NT\CurrentVersion\RegisteredOrganization (for Windows 7 64-bit)
I tested it on Win7 version.

Monday, November 8, 2010

F# continuation

Another sample of F# continuation passing style (CPS).

let F01 list =
            let rec FF list cont =
                match list with
                    | [] -> cont(0)
                    | h::t -> FF t (fun x -> cont(h+x))
            FF list (fun x-> x)

Friday, November 5, 2010

F# interop with C#

In F# file:

namespace AA

    [ < system.runtime.compilerservices.extension > ]
    module BB =
        [< system.runtime.compilerservices.extension > 
        let F(i:System.Int32, first:char, last:char) = {first .. last}

        let F2(a,b) = 12

In C#, you can call:

            int a = 3;
            var list = a.F('a', 'z');
            var b = BB.F2(a, 0.5);

Thursday, November 4, 2010

Serialization when using Base class

XmlInclude is the key, it should put on the base class and make the serialization of Automobile feasible.

public class Automobile
    public string Name;
    public int Year;

public class Car : Automobile
    public int NumerOfDoors;

public class Truck : Automobile
    public bool LongBed;

Monday, November 1, 2010

Recursion in F# Yacc

Just do not know why, keep forget the recursion for fsyacc.

| Expr { [$1] }
| List ',' Expr { $3::$1 }

Sunday, October 24, 2010

Tail Recursive Call != Recursive function call

These days I always think about the F# continuation and about the people blame recursive call. Is that true all the recursive call will generate the stack overflow? The answer is NO. The stack-overflow only happens when the parent call is waiting for the return value from the child invoke. If the recursive function does not return anything, there is no stack-overflow at all.

You have to use 64-bit compiler to make this happen; 32-bit does not work.

Wednesday, October 20, 2010

Pre-Order/In-Order/Post-Order tree transversal

when we use the CSP to transverse a tree, I got confused due to the how to implement the pre-order/in-order/post-order transversal.

when i look at previous post, i realize the keypoint is in the highlighted section.

type Tree = 
    E | T of Tree * value * Tree

let rec f2 tree cont =
    match tree with
        | EmptyTree -> cont([])
        | Tree(l, n, r) ->
            f2 l (fun lSum ->
                    f2 r (fun rSum->cont(lSum@[n]@rSum)))

currently it is in-order. You can change it to [n]@lSum@rSum and this will be pre-order.

Sunday, October 17, 2010

Performance - Using Interface

When I asked around, people are always using average to measure if function A is faster than function B. They ran the A and B 100 times and get the average execution time. But it is interesting that nobody really care about if their numbers were telling the truth or not. From the test data, I found the first time execution is much slower (or larger) than those succeeding ones.

  1. A=10309 B=689
  2. A=83 B=84
  3. A=79 B=84
  4. A=72 B=91
  5. A=76 B=83
  6. A=78 B=85
  7. A=89 B=83
  8. A=74 B=95
  9. A=75 B=87
  10. A=75 B=89
My functions are listed following:

        public static void A()
            List a = Enumerable.Range(1, 1000).ToList();
            var r = 0;
            var count = a.Count;
            for (int i = 0; i < count; i++)
                r += a[i];

        public static void B()
            IList a = Enumerable.Range(1, 1000).ToList();
            var r = 0;
            var count = a.Count;
            for (int i = 0; i < a.Count; i++)
                r -= a[i];

It seems that List object is kept and reused in A and B. I was expecting the interface one is slower, but the result show the opposite.

Thursday, October 7, 2010

Load data template in Silverlight 4

load a data template in Silverlight is painful job. You can always get some error like: The element is already a child of an element [line 0: position 0].

Please do not forget to add your library as the namespace and your assembly, even though your control is in the same assembly.

var template = (DataTemplate)XamlReader.Load(String.Format(@"xmlns:SilverlightControlLibrary=""clr-namespace:SilverlightControlLibrary;assembly=MyAssembly""> ", i++));

Sunday, October 3, 2010

0x88000FA8 error

I have encountered several times 0x88000FA8 error in my WP7 application. There is an exception object, but the visual studio just shows the "Evaluation time out" instead of any useful information.

After spending couple of hours on this stupid problem, now I realize that this is because the infinite event loop. For example, you update a control's layout in this control's LayoutUpdated event handler function, the layout updated event will keep firing and finally give this error.

LINQ's performance

The reason I love LINQ is that it can make me think in a  mathematical way. For some reason, I always doubt the FOR loop and IF condition makes a program buggy. I do not have the number to say most of the bug is from FOR loop or IF condition, but at least a world only with sequential statement seems easier for my brain.

For the performance point of view, LINQ is not perfect. When compare LINQ with simple for loop, the loser is always LINQ. Maybe the problem is too simple?

        public static void A()
            var a = Enumerable.Range(1, 1000);
            var b = Enumerable.Range(1, 1000);
            var r = 0;
            var count = a.Count();
            for (int i = 0; i < count; i++)
                r += (a.ElementAt(i) + b.ElementAt(i));

        public static void B()
            var a = Enumerable.Range(1, 1000);
            var b = Enumerable.Range(1, 1000);
            var r = a.Zip(b, (x, y) => x + y).Sum();

A=50109 B=10628

I got two IEnumerable. The for loop is slower than LINQ and not that easy to understand (at least for me). ElementAt()  is the culprit which makes the A 5 times slower than B. I can convert it to a List and without ElementAt(), A is still still faster than B, but it needs more memory to hold the List.

Do I have a conclusion? Unfortunately, NO. For a quick prototype, LINQ is perfect, but for performance critical hot path, I guess a FOR loop is still the inevitable.

String performance II

the previous post discussed the String.Format and concat. It seems that concat is the most efficient way to add strings together. Now I have the following two functions:

        public static void A()
            var s = "1" + "," + "2" + "," + "3" + "," + "4";

        public static void B()
            var s = String.Join(",", "1", "2", "3", "4");

A wins: A=16 B=310

But when we have to pass to non-string type, the winner is differnet:

        public static void A()
            var s = 1.ToString() + "," + 2.ToString() + "," + 3.ToString() + "," + 4.ToString();

        public static void B()
            var s = String.Join(",", 1, 2, 3, 4);

A=1664 B=496

String.Format performance

C# string performance is a tricky problem. I have two functions which generate the same result. Personally I prefer the second one because it is just an elegant representation format. Well, you have to pay for the elegance.

A's performance is much faster than B's.

         public static void A()
            var s = "abc" + "bcd" + "1" + "2" + "3";

        public static void B()
            var s = String.Format("{0}{1}{2}{3}{4}", "abc", "bcd", "1", "2", "3");

the following is the elapsed ticks for function A and B. If I run 100 iterations, A wins 99 times.

A=14 B=344

Let me try something different, maybe my favorite format has some advantages. Most of time, we do not use String.Format to construct a string, we pass in some non-string type.

        public static void A()
            var s = "abc" + "bcd" + 1.ToString() + 2.ToString() + 3.ToString() + 4.ToString() + 5.ToString();

        public static void B()
            var s = String.Format("{0}{1}{2}{3}{4}{5}{6}", "abc", "bcd", 1, 2, 3, 4, 5);

I am so happy that when this time, the String.Format catches up.

A=1609 B=585

I dig into the IL code and find that:

Function A will calls into "77 : Call System.String System.String.Concat(System.String[])".
While B will invoke: "75 : Call System.String System.String.Format(System.String, System.Object[])"

the different is not from these two functions, the difference is because A has to call ToString() several times and convert the result into a string array. A only need to pass the object reference to the Format.

Wednesday, September 22, 2010

C# Performance II

I like LINQ and functional programming very much. How about its performance?

this post is to check performance to check if a collection or list contain any element:

        public static IEnumerable l = Enumerable.Range(0, 10);

        public static void A()
            var b = new List(l).Count == 0;

        public static void B()
            var b = l.Count();

My first impression is the new + .Count could be slower than, but actually it is very fast.

  • A uses 7 ticks
  • B uses 1921 ticks
But thing got to change after increase the size of this list from 10 to 1000000
  • A uses 55858 ticks
  • B uses 26076 ticks
Let us not use Count, we use Any.

  • A uses 55012 ticks
  • B uses 3142 ticks
The conclusion will be:

for a small size collection, convert it to a List and check Count is faster. Otherwise, use Any() will be the best choice.

Monday, September 20, 2010

C# Performance

When C comes out, there must be some chaos about its performance is not as good as assembly language. I will start some posts to discuss the performance of C#, trying to help improve the performance of .NET language.

  1. var str = "";
  2. var str0 = String.Empty;
we can easily find out that str = str0; but which way is faster? 

the following is the disassembly from the first statement:
    Stloc_0 local_0

the following is the one from the second statement:
    Ldsfld System.String.Empty
    Stloc_1 local_1

It does not tell much, but when we actually run it using StopWatch, we can find the String.Empty is 5-6 times faster than empty string. I would not say the different is so huge because maybe it is my computer's configuration, but definitely the second statement is faster.

WP7 Lost Connection error

I am disappointed by the Windows Phone 7 emulator. Why? It just pops out "lost connection" error and I have to spend a day to figure out what is wrong.  I have a class which implements the INotifyCollectionChanged interface. In the item I was trying to hold a reference to its parent which is a INotifyCollectionChanged structure. Do not ask me why, this make the emulator crash. How to fix it? change its type to object. I guess some boxing is happening behind.

Hopefully the phone is as good as media said before.

Friday, September 17, 2010

Working on a .NET emulation enigne

How hard to do a software evaluation engine for .NET runtime. I spent 3 weeks. The CCI helps me a lot, although currently it does not read .NET opcode.

Monday, September 6, 2010

Euler Project Problem 81 with F#

module Problem81

let readfile fileName =
    let lines = System.IO.File.ReadAllLines(fileName)
    let data =
        let splitter = [|','|]
        |> (fun line -> line.Split(splitter) |> (fun element->float(element)))

let m = Matrix.ofSeq (readfile @".\matrix.txt")

let cols = m.NumCols - 1
let rows = m.NumRows - 1

let tempMatrix = Matrix.create (cols+1) (rows+1) -1.

let rec f x y =
    let v = tempMatrix.[x,y]
    if (v <> -1.) then
        let getResult =
            let d = m.[x,y]
            match x,y with
                | (a,b) when a=cols && b=rows -> d
                | (a,_) when a=cols -> d + f x (y+1)
                | (_,b) when b=rows -> d + f (x+1) y
                | _ ->
                    let right = f (x+1) y
                    let down = f x (y+1)
                    d + (min right down)
        tempMatrix.[x,y] <- float(getResult)

let solve = f 0 0

printfn "%A" solve

Sunday, September 5, 2010

Simulation on Euler Project 205

When I was trying to solve Euler Project 205 using F#, I was thrilled to find an opportunity to use GPGPU to solve this problem. The correct solution for this problem is to use statistic method, but I would like to simulate the process and see what I can get. Again, I do not intend to solve this problem by this approach, just to learn GPGPU.

Simulating this process is simple, I make a 9*1000 size matrix A with random number from 1 to 4. Similarly, matrix B is 6 * 1000 with element ranged from 1 to 6. The Accelerator v2 from Microsoft Research provides a good managed platform for GPGPU. The following is the code:

let dxTarget = new Microsoft.ParallelArrays.DX9Target()

let getWin index (gridSize:int) =
    let shape = [| gridSize; gridSize; |]
    let resultShape = [|gridSize|]
    let zero, one = new FPA(0.0f, resultShape), new FPA(1.0f, resultShape)

    let generatePrymaid i j = float32(random.Next(1,4))
    let generateDice i j = float32(random.Next(1,6))

    let px = new FPA(Array2D.init 9 gridSize generatePrymaid)
    let py = new FPA(Array2D.init 6 gridSize generateDice)
    let pxSum = PA.Sum(px, 0)
    let pySum = PA.Sum(py, 0)
    let cond = FPA.op_GreaterThan(pxSum, pySum)
    let gpu = PA.Sum(PA.Cond(cond, one, zero), 0)  
    let a = dxTarget.ToArray1D(gpu)
    let result = Seq.head a
    tempResult <- tempResult + int64(result)
    if (index%500=0) then
        let total = int64(index) * int64(gridSize) + totalTest
        printfn "Time = %A; Result = %A" index (float(tempResult) / float(total))
        appendToFile file (System.String.Format("{0}\t{1}", tempResult, total))

let compute n = Seq.init n (fun i->getWin i gridSize) |> Seq.sum

let n = 250000;
let mutable start = System.DateTime.Now;
printfn "%A" ((compute n) / float32(gridSize*n))
printfn "%A" (System.DateTime.Now - start);

The result is interesting:

  1. on my powerful desktop: the GPU version is slower than CPU version.
  2. on my laptop, the GPU version is 2 time faster than CPU version. The CPU fan is quiet when I do the computation.

Thursday, September 2, 2010

QuickSort in F# using Continuation Passing Style (CPS)

The recursive implementation is a good approach for QuickSort algorithm; however, this implementation can lead to "stackOverflow" exception. We will use tail recursive to get rid of this flaw.

let rec qs list cont =
    match list with
        | [] -> cont([])
        | [a] -> cont([a])
        | head::tail ->
            let lessList = tail |> List.filter (fun i-> i<=head)
            let moreList = tail |> List.filter (fun i-> i>head)
            qs lessList (fun lessListPara -> 
                qs moreList (fun moreListPara -> cont(lessListPara@[head]@moreListPara)))

let list = [7;2;6;8;4]
let result = qs list (fun a -> a)

Wednesday, September 1, 2010

Recursive call into Tree structure

let rec f2 tree cont =
    match tree with
        | EmptyTree -> cont([])
        | Tree(l, n, r) ->
            f2 l (fun lSum ->
                    f2 r (fun rSum->cont(lSum@[n]@rSum)))

Use continuation to implement the tree recursive function. This way is a better approach because it won't generate "stack over flow" exception.

Remember when you debug this in Visual Studio, remember to check the "Generate tail calls" at "build" tab when you open the project property.

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

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)

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:

There is a wiki page about it.

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

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

Tuesday, August 10, 2010

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.

Monday, August 9, 2010

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
    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) -> genoPhenoConverters genos |> (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.

Sunday, August 8, 2010

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,, 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 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
"%A" sum

Saturday, August 7, 2010

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.