Monday, September 19, 2011

F# with less bug and C# structure mapping

When I program with F#, I find less bugs are yielded. I can confirm this astonishing result with some other individuals or companies. I want to know find out why and here is something I've got on the top of my mind:

1. mutable variable is not allowed. Less mutable variable means less state and lower possibility to generate bug.
2. concise code. this is pretty straightforward. The probability is proportional  to the length of code.
3. mind set change. I do not intend to speak for other person. For me, when I changed my mind set from C++ machine-like thinking to more math-like thinking. I find it is natural to solve a program with less glitch. When I not forced to think like a computer, I feel a big relief and my brain becomes more efficient. 

Let me mapping the basic C# flow control structure to F#.

FOR loop

for (int i=0; i<100; i++) ...

can be written as

[0..99] |> (fun i -> ... )

this approach can be interpreted as loop on the list [0..99]. Another way to interpreted this is the result is a transform of element in [0..99]. This transform is performed by a function applied to the element in [0..99].

Please note: this approach create a list in the memory, if this is too much memory cost, then you can use seq instead of list.

FOR Loop with IF inside

for (int i=0; i<100; i++)
    if (i % 2 == 0) ....

notice the above sample does not have ELSE.

[0..99] |> Seq.filter (fun i->i %2 = 0) |> (fun i -> ....)

the list [0..99] is filtered to make sure only the valid input is going to be processed.

we usually make a lot of operations in a FOR loop to improve performance. With parallel in mind, maybe we want to change this behavior. For example, we perform functionA on even number and functionB on odd number. Instead of doing:

//C# pseudo code
for i =0 to 99 do
    if i %2 = 0 then functionA()
    else functionB()

We can do
[0..99] |> Seq.filter (fun n -> n%2=0) |> (fun i -> functionA())
[0..99] |> Seq.filter (fun n -> n%2<> 0) |> (fun i -> functionB())

And put these two statements onto two processors. Which one is faster, it might depends on the implementation. But I prefer the F# version. Immutable data and parallel are friend. Most of our existing algorithm is based on single process. That's why I like F# more.

WHILE loop

During the flight from Seattle to Louisvelle, I was thinking about the WHILE loop. FOR loop has more well defined boundary, but WHILE loop is behave otherwise. Is there a way to transfer WHILE loop to F#? I prefer to use Seq's infinite seq feature. Seq.initInfinite gives a infinite seq as the input into your function. Its your function's job to generate a value which can be track by Seq.takwhile function, so the loop won't go into infinite loop. For me I pay more attention to how to terminate the loop from the function and usually got a math formula written down. This formula gives me more confidence not going to an infinite loop.

Last Chapter
Today is the last night at the nice town Louisville, KY. I love this place better than Seattle. Enough, back to work! Let me finish this post with a sort algorithm implementation.

If we use parallel to solve a sorting problem, what could be the solution? An element's index in a sorted list is the number of element smaller (or bigger) than this element. If we have multiple processor, can we just process compute the index from existing array. Because the existing array is immutable, so all the process can be paralleled. Let us assume the processor number is large enough, we can readily get O(n).

I start to think about my breakfast. do not really want these algorithms to interrupt.. :-)

No comments: