Set break point in a F# function

Not quite sure if this is a big deal, but I always frustrated about how to set a break point in a F# or C# LINQ expression. The mouse click does not always work, but today, but today the keyboard saved me. So

1. move mouse to the function definition
2. press "F9"

put a smile on my face..  :-)

Type infer in LINQ

If you really want to use LINQ in F#, sometimes you have to specify the type:

counts is a Dictionary
counts
        .OrderByDescending(fun x -> x.Value)
        .Take(8)
        .Select(fun x -> x.Key)   //change this line to the line below will make you compile
        .ToList()

.Select(fun (x:KeyValuePair<_,_>) -> x.Key).  

Delegate wrap a function pointer

though C# does not support, but delegate does wrap a function pointer underlying. In CLR, it is calli.

Keep this in mind..

function with LINQ

Today I work on a problem to find if a line is intersected with a circle.

so f1 is y = ax + b and f2 is x^2 + y^2 - r^2 = 0

It is true you can use for-loop to solve this problem, but since I hate for-loop, i will use LINQ.

the input to f1 is { x }, if the line is intersected with a circle means there is (a,b) where f2(a,b) <=0. OK, the data input is {x}, and it is transformed by f1 into some { (x,y) } tuple sequence. If there is a tuple in the sequence makes f2 <=0, we can draw the conclusion that the line is intersected with a circle.

The pseudo-code is like:

{ x } |> seq.map f1 |> seq.exists f2(x,y) <=0

Let me give detailed code tomorrow

Use sequence to solve the problem

When I went through a problem which requires to find the maximum of difference between two elements. The 2nd element's index must greater than the 1st element. So the way to solve the problem is two steps:

1. generate the sequence
2. filter the element which meet the requirement.

Before we start, somebody might want to ask, what is the performance of the code if we generate a whole list and then filter it. Do not worry, the sequence is not holding any memory or resource. It is just a lazy evaluation, so it will just return one element at one time.

Now we can concentrate on how to solve the sequence problem. We need to find a function to generate
    output = sequence of (element0, element1)
from
    input  = sequence of element

when we get the output, we need to find the element where (element1-element0) is the maximum.

the sequence is IEnumerable < (element, element) > by using yield return statement

for ( i = 0 ; i < input.Length; i++)
    for (j=i; j < input.Length; j++)
        yield return ( input[ j ], input[ i ] );

After we have this output sequence, we try to get the maximum by using output.Max(n => n.element1 - element.0)

The way I like functional programming is it more like human's thinking. The closer we think like human (or in a mathematical way), the less chance we generate an error. If we can represent a program in a mathematical way, it'll be much easier to verify it as well. In this solution, I still got some FOR loop, in this solution, let me come back later to get rid of this FOR.

Today seems a good time to get rid of FOR.

the idea is simple: we need two sequence, one is [1..count], the other has to use the element from first sequence as a parameter.

Enumerable.Range(0, count).SelectMany(i => Enumerable.Range(i, count - i).Select(j => new Tuple(i, j)));

functional programming to find sequential group

It is Friday night and maybe some blog can help me relax a little bit.

If I got a input sequence like { 1, 2, 3, 6, 7, 8, 11, 12, 13, 145 },  how can you group them into some group where each group only contain continuous numbers. 

Please do not use for-loop, try to think the input like a single unit, a output from a function. Here is the solution:

 
var groups = input.Zip(Enumerable.Range(1, input.Length), (i, n) => new { i, GroupNumber=n-i }).GroupBy(m => m.GroupNumber, m => m.i);

how does think work? 

It use another continuous output as mirror to help group the input.

I found the way to write a good LINQ query or thinking in functional way is to compare the input and output and trying to find the different. You always think the input as a whole entity. After applying some functions, can easily prove the whole program is correct or not. that's the beauty of functional. I do not know a way to make a FOR loop into a nice math formula, maybe that's why I am always afraid of FOR loop.

The above sample give me a new way to design functional program by introducing another sequence or entity. I love functional!

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.

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.