.NET at 9.400 ft above sea level

F# 1.9.4.19 runs out of the box with Mono in Linux

2008-07-15T04:25:39Z

Don Syme just announced a minor update to the F# environment, minor may be but of great interest to a certain community: it so happens that at some point F# stopped working properly in Linux, a workaround was published (and it actually works, but you've got to follow the instructions carefully). Well, not anymore, 1.9.4.19 works out of the box with Mono in Linux, you just have to download it, unzip it, and then happily type "mono fsi.exe":

So now I've got one less pretext for not writing that book "Learning to program the functional way in an open source environment using a cool Microsoft technology" that will make me famous...

Cloning objects in .NET

2008-05-18T06:27:38Z

In an interesting project where I'm giving a hand, we need to clone objects of a number of different types, perhaps surprisingly the CLR doesn't offer a general cloning method, of course you could use MemberwiseClone() but this is a protected method, so it can be invoked only from inside the class of the object being cloned, which makes it difficult to use it in a general method, besides, MemberWiseClone() does just a shallow copy and what we really need is a deep copy.

There is a good reason for not having such a general method: object cloning is one of those problems which have a simple solution for simple scenarios but that resist a satisfactory solution for all the scenarios, for example the objects may have references to other objects and even to themselves be it directly or after a long chain, for example a customer has invoices that have payments that refer to the customer, a general cloning algorithm for a web several times more complex than that is anything but trivial. But the need of moving objects (and their web) is inescapable in distributed environments, because you have to move the invoices and the customers from the business layer to the presentation layer, so there are indeed mechanisms, albeit with some limitations, for serializing and deserializing object graphs, with the help of these mechanisms we can try and build a general object cloner:

    1 
    2     public static T BinaryClone<T>(this T originalObject)
    3     {
    4         using (var stream = new System.IO.MemoryStream())
    5         {
    6             var binaryFormatter = new System.Runtime.Serialization.Formatters.Binary.BinaryFormatter();
    7             binaryFormatter.Serialize(stream, originalObject);
    8             stream.Position = 0;
    9             return (T)binaryFormatter.Deserialize(stream);
   10         }
   11     }
   12 

We just convert, using as intermediary a memory stream, our object to a bit string and then we synthesize a *new object* from that bit string. The use of BinaryClone() flows nicely:

    1 
    2     var clone = person.BinaryClone();
    3 

Easy to write, but we have to be careful of the performance and the corner cases. I run a few *very informal* performance tests with this object:

    1 
    2     var person = new Person
    3     {
    4         Id = 101,
    5         Name = "Sánchez, Sebastián",
    6         Salary = 590.20m,
    7         BirthDate = new DateTime(2000, 6, 15),
    8         Address = new Address { Number = "N24-78", Street = "Pasaje Córdova" }
    9     };
   10 

And I found that doing a hundred thousand clones takes some nine thousand milliseconds, that is each cloning takes less than one ten-thousandth of a second, which is adequate to our needs. BinaryFormatter has been with us since .NET Framework 1.0 so I'm not like saying anything even remotely new or unknown, but tomorrow (or the day after, or the day after...) I'll talk about a small refinement to BinaryClone().

A cool way to find out whether a number is palindromic

2008-05-06T06:40:08Z

In this blog entry I proposed a solution to Problem 4 at Project Euler, a crucial element of the problem is to find out whether a number is a palindrome (909 is, 809 isn't), a bit out of laziness and a bit in order to reuse existing methods, I decided to verify the palindrome by converting the number into a char array and then comparing this array with its mirror version, it works but it's not really that mathematical... Dustin Campbell proposed a solution kind of similar to mine (alas, more elegant and, above that, in F#) and using the same trick of converting the number to chars, as he didn't like this part of the solution, in this new blog entry he proposes the detection of a palindrome by mirroring the number one digit at a time. A translation of his F# code to C# 3.0 could be:

    1     Func<int, int, int> TailReverseNumber = null;
    2     TailReverseNumber = (n, res) => n == 0 ? res : TailReverseNumber(n / 10, 10 * res + n % 10);
    3 
    4     Func<int, bool> IsPalindrome = n => n == TailReverseNumber(n, 0);

TailReverseNumber takes a number n and "mirrors" it, one digit at a time, for example: TailReverseNumber(237, 0) -> TailReverseNumber(23, 7) -> TailReverseNumber(2, 73) -> TailReverseNumber(0, 732), the big trick is that res works as an accumulator that is multiplied by 10, therefore moving its value to the left, and putting in the "hole" that appears at the right the least significant digit of n. As it names implies, TailReverseNumber() uses tail recursion, so that no extra call stack space is used to save any intermediate results, which makes the process pretty efficient. Actually, in my PC it's four times faster than the initial solution. More efficient and more elegant, a smart guy Dustin.

New version of F# just released

2008-05-03T06:26:07Z

In its way from research language to commercial language, Don Syme just announced that, silently, on May the 1st version 1.9.4.15 of F# was released.

This new version incorporates a number of specific enhancements (F# is now basically in stabilization mode, so we really shouldn't expect significative changes to the language). By the way, the example in the picture shows my idea for solving Problema 2 of Project Euler: find the sum of all the even-valued terms in the Fibonacci sequence which do not exceed four million. For an explanation of how it works, I suggest you this Dustin Campbell blog, which proposes a solution similar to mine with a couple of elegant touches and, above all, with a detailed and engaging explanation.

Which is the ten thousand first prime?

2008-05-02T05:09:56Z

Prime numbers have a good deal of practical applications (for example in cryptography) but let's face it, even if they would have none, they would still be the favorite toy of mathematicians. In Problem 7 of Project Euler, we are asked to find the 10001st element of the famous list, my approach was this:

Define the *infinite* sequence of the prime numbers
From this sequence, throw away the first 10000 items and then take the first of the remaining

Creating an infinite sequence in C# is easy (since version 2) thanks to IEnumerables and, above all, the yield statement:

    1 IEnumerable<int> Primes()
    2 {
    3     yield return 2;
    4 
    5     var primesSoFar = new List<int>();
    6     primesSoFar.Add(2);
    7 
    8     Func<int, bool> IsPrime = n => primesSoFar.TakeWhile(p => p <= (int)Math.Sqrt(n)).FirstOrDefault(p => n % p == 0) == 0;
    9 
   10     for (int i = 3; true; i += 2)
   11     {
   12         if (IsPrime(i))
   13         {
   14             yield return i;
   15             primesSoFar.Add(i);
   16         }
   17     }
   18 }

The yield at line 3 returns the first item of the sequence: the always excepcional 2 (the only even prime). Then at line 5 we create a list where we will be saving the generated primes as we progress in the sequence (this way we will gain speed at the cost of memory). The IsPrime(n) function defined at line 9, proposes a method -pretty crude actually- of verifying whether a number is prime: we take all primes generated so far which are lower or equal than the square root of n, and we look for the first among them that divides n evenly, if such a divisor exists then n is not a prime, that is: if none of the primes already generated is an exact divisor of n then FirstOrDefault() returns a 0, signaling the fact that n is indeed a prime. Finally at line 10 starts the loop that, every time the Prime() invoker asks for an item, it progresses thru 3, 5, 7, 9, 11, 13, ... stopping and returning, thru yield, when it finds a new prime.

With this sequence in our hands, step 2 of my plan is utterly simple:

return Primes().Skip(nth - 1).First();

We take the Primes() sequence, ignore the first nth - 1 (in our case nth = 100001) and then take the first of the remaining. This little code returns the answer in far less than a second.

The square of the sum vs. the sum of the squares

2008-04-28T02:56:32Z

The sixth Project Euler problem poses an exercise that, to me, offers no major hurdles:

What is the difference between the sum of the squares and the square of the sums [of a sequence of natural numbers]?

The functional C# solution is fairly easy to write and read:

    1     public int SquareSumsLessSumSquares(IEnumerable<int> sequence)
    2     {
    3         var sum = sequence.Sum();
    4         var sumSquares = sequence.Select(i => i * i).Sum();
    5         return sum * sum - sumSquares;
    6     }

We get any sequence of integers (list, array, etc.) and we find the sum of its elements at line 3. The Select() in line 4 generates a new sequence with the square of each item from the original sequence and then we add them up. From there, getting the answer to Problem 6 is easy. Actually, the specific value that the problem asks for is to find out this difference for the first 100 natural numbers, so the corresponding call is:

    var result006 = SquareSumsLessSumSquares(Enumerable.Range(1, 100));

Now, given that the sequence we are focused on is 1, 2, 3, ..., 100, we can leverage a couple of math formulas:

Isn't the Wikipedia something? With this information in our hands we can re-write our solution this way:

    1     public int SquareSumsLessSumSquaresFirstNumbers(int n)
    2     {
    3         var sum = n * (n + 1) / 2;
    4         var sumSquares = n * (n + 1) * (2 * n + 1) / 6;
    5         return sum * sum - sumSquares;
    6     }

Clearly this latter way of solving the problem uses far less memory and CPU time. My first solution follows what is called a "brute force" approach, contemption intended. It works, for sure, but there are more elegant and efficient ways of solving the problem. The moral of this story is that a little research can take us a long way towards fresh solutions, probably better than our first approach. How frequently have you seen brute force solutions in production environments?

Recursive lambdas and sequence aggregations

2008-04-24T05:22:45Z

The fifth problem at Project Euler proposes this nostalgic primary school exercise: find the smallest quantity that is evenly divisible by some numbers, the least common multiple of 1, 2, 3, ..., 20 to be precise. To begin with, let's remember the old arithmetic formula:

Where gcd is the greatest common divisor of a and b. It's also useful to remember that the lcm is associative, that is lcm(1,2,3) is the same as lcm(lcm(1,2), 3), in other words, we can calculate the lcm of 1 and 2, then the lcm of this result and 3, then the lcm of this result and 4, and so on. In functional C#, these ideas can be expressed like so:

    1     Func<int, int, int> gcd = null;
    2     gcd = (x, y) => x % y == 0 ? y : gcd(y, x % y);
    3 
    4     return Enumerable.Range(1, 20).Aggregate(1, (x,y) => x * (y / gcd(x, y)));

Line 2 finds the gcd of x and y like this: if the remainder of dividing x by y is zero, then y is the gcd, if not, we must find the gcd of y and such remainder. Note that gcd is defined recursively. The only interesting point here is that in order to define a recursive lambda expression, it is mandatory to first declare the expression variable (which we do in line 1), and only after this the compiler allows us to define a lambda expression in terms of itself. Odd, granted, but easy to get used to.

Line 4 takes the sequence 1, 2, ..., 20 and accumulates the lcm as the sequence is traversed, that is: it starts calculating lcm(1, 1) (let's call this accum1), then it calculates lcm(accum1, 2) (let's call this accum2), then it calculates lcm(accum2, 3), ..., and finishes with lcm(accum19, 20) which is precisely lcm(1, 2, ..., 20). The Aggregate() function is frequently used for chores like adding each term of a sequence, or multiplying them all, in our case we are using Aggregate() to get the succesive lcm's, which answers the question of Project Euler in two and a half lines of code, cool, eh?

Nested sequences and palindrome numbers

2008-04-22T06:41:44Z

Problem 4 of Project Euler poses and impractical albeit intriguing problem: given all three digit numbers (100, 101, 102, ..., 998, 999), find the largest product of 2 of those numbers, where the product is a palindrome. For example, 580.085 is the product of two three-digit numbers (995 x 583) but it isn't the largest of such products. One possible functional C# solution is:

    1     Func<int,bool> IsPalindrome = n => { var nchar = n.ToString().ToCharArray(); return nchar.SequenceEqual(nchar.Reverse()); };
    2 
    3     return Enumerable.Range(100, 900)
    4         .SelectMany(i => Enumerable.Range(i, 900 - (i - 100)).Select(j => i * j))
    5         .Where (p => IsPalindrome(p))
    6         .Max();

To begin with, let's focus on the interesting part: at line 3, Enumerable.Range() generates the sequence 100, 101, ..., 998, 999; SelectMany() at line 4 does several things, first for every number i from the previous line it generates the sequence i, i + 1, i + 2, ..., 998, 999, and then the inner Select() generates the products {100 x 100, 100 x 101, ..., 100 x 999}, {101 x 101, 101 x 102, ..., 101 x 999 }, ... As you can see, there are 999 sequences generated (are all the same size?) finally SelectMany() kindly "flattens" those 999 sequences in one large sequence containing each and every product; line 5 then is easy, the Where() just keeps those products that are palindromes; the Max() in line 6 isn't worth any explanation.

Back to line 1, I took the lazy path to check whether a number is a palindrome: I just converted it to a string and then to a char array, finally I checked whether that array is equal, item by item, to its reversed version (and all that work just to leverage IEnumerable.Reverse() ;-)

Finding the largest prime factor of a number

2008-04-19T05:40:00Z

This is another classic problem at Project Euler that can be solved with the old trick of top down programming, like so:

     PrimeFactors(number).DefaultIfEmpty(number).Max();

It's a nice solution, supposing PrimeFactors() actually returns all prime factors of any given number. But before getting there, it's a good idea to discuss what DefaultIfEmpty() is doing there. The thing is that somebody could make this innocent call: PrimeFactors(1), which of course returns an empty collection, which in turn makes PrimeFactors(1).Max() throw an exception (trying to get the maximum out of nothing, eh?) DefaultIfEmpty(x) to the rescue: when DefaultIfEmpty(x) is applied to a "reasonable" collection it returns it untouched, but when it's applied to an empty collection it returns a new collection with just un item: x. So, in our case, PrimeFactors(1).DefaultIfEmpty(1).Max() is just a looooong alias for 1. DefaultIfEmpty() is very useful for those special cases with empty collections.

With that behind, let's see how we get all the prime factors of a number:

    1     IEnumerable<ulong> PrimeFactors(ulong number)
    2     {
    3         Func<ulong, ulong> FindDivisor = n => n == 1UL ? 1UL : CandidateFactors(n).First(c => n % c == 0);
    4 
    5         var factors = new HashSet<ulong>();
    6         while (number > 1UL)
    7         {
    8             ulong divisor = FindDivisor(number);
    9             factors.Add(divisor);
   10             number /= divisor;
   11         }
   12 
   13         return factors;
   14     }

At line 3 we define a function (we are using lambdas just for fun) that finds a divisor for a number, for example FindDivisor(45) returns 3 and FindDivisor(49) returns 7. The workhorse is the while loop starting on line 6, it starts with a number, let's say 45, find the divisor 3, saves it in factors and goes on with 15 (45 / 3), now it finds a divisor for 15, in this case 3 again, saves it in factors and goes on with the 5 (15 / 3), and so on and so on until all is left is a 1. Meanwhile factors has been accumulating 3, 5, etc.: the prime factors of the original number. An interesting detail is that factors is a set, so it doesn't have any duplicates.

Finally let's check the CandidateFactors() definition:

    1     IEnumerable<ulong> CandidateFactors(ulong n)
    2     {
    3         yield return 2UL;
    4         for (ulong candidate = 3UL; candidate <= n; candidate += 2UL)
    5             yield return candidate;
    6     }

As you can see, this function simply produces the sequence 2, 3, 5, 7, 9, ..., n which are the possible divisors of n. You can think of a more clever implementation, one that produces a less indiscriminate list of candidates, but let's leave that for another day.

And in this way, this mixture of LINQ (DefaultIsEmpty(), Max(), First()), lambdas (FindDivisor), iterators (yield) and good old imperative programming, leads us to a compact and effective solution to an old problem. Do you happen to have a more elegant solution?

Project Euler and infinite sequences in C#

2008-04-17T08:10:25Z

The second problem at Project Euler proposes:

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

Find the sum of all the even-valued terms in the sequence which do not exceed four million.

One way of solving this problem is by defining an endless sequence in C#. Something along these lines:

    IEnumerable<int> FibonacciSequence()
    {
        int n1 = 0;
        int n2 = 1;
 
        while (true)
        {
            int n3 = n1 + n2;
            yield return n3;
            n1 = n2;
            n2 = n3;
        }
    }

The FibonacciSequence() function returns the next value in the sequence everytime its execution hits the yield statement, and conveniently enough, n3 gets the values 1, 2, 3, 5, 8, ... in each next round of the loop. It's notable that the loop never finishes by itself, this responsability actually belongs to the code invoking FibonacciSequence(). So in fact we are seeing a way of representing an infinite set (all Fibonacci numbers) in C#. In our case we need all elements no bigger than 4'000.000, so we can write something like this:

FibonacciSequence().TakeWhile(n => n <= 4000000).Where(n => n % 2 == 0).Sum()

The TakeWhile() method stops asking for more terms as soon as an item bigger than four millions is produced, afterwards the Where() method leaves us with a sequence containing only the even terms, and these terms are finally added up by Sum().

Project Euler and functional C#

2008-04-16T06:59:19Z

I think I already talked (a long time ago) about Project Euler: a set of problems, mainly math oriented, keen to be solved with a computer program. To be sure, it's not particularly deep math, but the problems posed go fairly quickly from really easy, to hmm, to challenging. In this sense, they are good programming calisthenics, and may also be a good way of learning a new language. For example, Chris Smith has solved some Project Euler problems using F#, I find the idea intriguing, so I'll try to do the same thing, only that I'll be using C#, but not your plain old C# mind you, as I'll do my best to use in as much as possible the functional facilities of C# 3.0. Let's see for example Problem 1:

Add all the natural numbers below one thousand that are multiples of 3 or 5.

Ok, ok, the problem is ~~silly~~ trivial, but wait until you get to Problem 10 ;-). One C# 3.0 functional solution is:

    Enumerable.Range(1, 999).Where(n => n % 3 == 0 || n % 5 == 0).Sum()

Range() generates the sequence from 1 to 999, and then Where() filters it leaving just the numbers multiples of 3 or 5, finally Sum() adds up these numbers. Easy, isn't it? And without loops or ifs.

Obviously, not all problems lend so naturally to be solved in a functional way, and we'll find out step by step how useful is the functional paradigm in Project Euler.

Eight Silverlight training sessions

2008-01-07T05:20:21Z

A little bit of cross-posting but I find this interesting enough as not to risk you miss it...

Silverlight 1.0 FireStarter is a one day event, targeting developers and designers, that teaches the why's and how's of Silverlight 1.0, a total of eight very interesting sessions:

An Introduction to Silverlight
Getting Started Programming Silverlight
Workflow of Silverlight with Expression and Visual Studio
Silverlight XAML
A Development Story
Media, Markers and More
Popfly and Silverlight
Silverlight in the Future

Now, the really nice thing is that you can see and download the videos of each presentation. Ah, you can even download the source code. Now, all I need is 8 free hours...

Tuples: an F# lightweight data structure

2007-12-05T05:24:01Z

Maybe the best thing to do is to start by showing a few examples of tuples:

let amigo = ("Sebastián", 7)
let pair1 = (3, 2)
let pair2 = (2, 5)
let student = "Santiago", "Monterrey", 2007, true

The first tuple ("Sebastián", 7) groups two values: a string and an integer, allowing us to handle them as just one thing, this "thing" has the type string * int, that is, it belongs to the set of all the combinations of strings and integers, in this sense ("Sebastián", 7) has the same type of ("Alejandra", 19). By the way, note how we separate the different elements of the tuple with commas.

Tuples pair1 and pair2 are of type (make a wild guess...) int * int. Strictly speaking, "let pair1 = (3, 2)" defines a function pair1 that always returns the same tuple (3, 2), that is, it's a constant function that takes 0 parameters.

Finally, the student tuple is of type string * string * int * bool, the fact that I have omitted the parenthesis is not a mistake, tuples actually don't need them and many F# programmers don't put them (even though, I personally prefer to write them down, to remind myself that what I am seeing is something to be treated as a whole).

With these tuples in our hands, we can define some functions:

let addPairs (x1,y1) (x2, y2) = x1 + x2, y1 + y2
 
let primero (p, q) = p
 
let getYear (name, city, year, status) = year
 
let getYearFunny (_, _, year, _) = year

addPairs is a function that receives two tuples and returns another (to be precise, its type is int * int -> int * int -> int * int). Just to get used to it, I omitted the parenthesis in the function body (but I insist: I don't think it's a good idea).

The function primero is even more interesting: its type is... 'a * 'b -> 'a, which means that it receives a tuple containing some stuff and some other stuff and returns something of the same type of the first stuff. Maybe we expected the type to be something like int * int -> int, but that would have unnecessarily limited the usability of the function. For example, we can now say "primero amigo" and get the string "Santiago" or "primero pair1" and get the integer 3. If you think about it, the use of 'a and 'b is very similar to the use of generics in C# or VB.NET. It's utterly important to note that primero does *not* receive two parameters p and q but just one parameter, namely a two-value tuple, and then the function body tells that what must be returned is the first of those two values, this is a simple example of F# pattern matching. By the way, it's really not necessary to write the primero function, because F# already provides us with fst and snd.

A somewhat more complex example of pattern matching is getYear, which gets a tuple of type 'a * 'b * 'c * 'd and returns a 'c. "getYear student" of course returns 2007 (what is returned by getYear ("William", "Jones", 1706, 3.1416)? Is this even possible?). It's interesting to note that even though in getYear definition we name the four elements of the tuple, we use just one of them, which takes us to the definition of getYearFunny: the "_" symbol (underscore) basically means "an element whose value I don't care about", and so getYearFunny ignores the first, second, and fourth values in the tuple. This is our first encounter with this "_" guy and we'll find out that it appears frequently and that it's very useful when doing pattern matching.

Finally, let's mention a few more characteristics and uses of tuples:

A tuple have a fixed number of elements: be them two, three or thirty, once set you can't add or remove elements from a tuple
The elements in a tuple doesn't have a name, you access them by their position in the tuple with the help of pattern matching
It's almost redundant to say, but a tuple may contain other tuples, e.g. what's the value of fst (snd ("Santiago" (9, 10))) ? Do we need all the parenthesis?
A tuple is a handy way of making a function return multiple values (as the original getYear does) or to pass multiple values to a function that expects only one parameter

Tuples are a basic and simple component of F#, built to represent a fixed-size sequential set of values.

F# doesn't need parenthesis in functions, or does it?

2007-12-03T02:09:18Z

In a previous posting I mentioned that when you define a function in F# you don't need parenthesis surrounding the parameters, or commas separating them. So, this simple definitions are all valid:

let negate a = -a
 
let add a b = a + b
 
let multiply a b = a * b

When you compile them, you get this messages:

negate is a function that takes an integer and returns an integer, add takes two integers and return another, etc.

Now we can type "add 3 4" and we get a 7, but things get interesting if we try to negate the "add 3 4":

Why? To solve this mystery we have to understand that function application (i.e. invocation or calling) is an operation as well as +, *, or -. As other operations, application has a precedence (which operation is called first when you've got a mixture) and associativity (if you have "a + b + c", does this mean "(a + b) + c" or "a + (b + c)"). In F# function application has the highest precedence and it is left associative, so that

negate add 3 4

is interpreted as "(negate add) 3 4" and not as "negate (add 3 4)". It pops to the eye that "(negate add)" can't be right, but this is not because you can't pass a function as parameter in F# (which is not only possible but common and pretty useful) but because negate expects an integer as parameter and add is a function, not a number. Maybe the compiler message could be more explicit, but I hope the real source of the problem is more clear now. So, in order for F# to evaluate the expression in the expected order we should write:

negate (add 3 4)

And now, F# first adds 3 and 4, giving 7, and then negates the result giving -7. There are several other scenarios where for getting F# to do the evaluation in the adequate order we must use parenthesis, but remember you will be using them not because invocation requires them but because of precedence and associativity. After this discussion, I think it will be easier to understand the following results:

Maybe the only unexpected expression is the last "(-1)", once again the parenthesis are there because "-" is an operator and without them, the expression would be interpreted as "(multiply 3 -) 1", and the compiler will shout because multiply expects two numbers and "-" is a function, not a number. This could be surprising at first (I bumped onto this very same issue with Haskell several years ago) but once you know why, it's not really a problem.

Word 2007 and Microsoft Math

2007-12-02T19:22:00Z

Reading Alfred Thompson blog, who focus on computer science teaching at K-12 schools (what we call in Ecuador basic high school), I found this nice entry: Microsoft released a few days ago the Word 2007 Math Add-in. After installing and playing with it for just 2 minutes, I was able to create this document:

As you can see, the add-in lets you put formulas inside the text (including fractions, exponentials, sigmas, integrals, etc.), create graphs from an equation (I just typed in y = ...), and even solve those equations. Ah, this is the kind of stuff I would've loved to have at high school or college.

Speaking of which, the add-in seems to be based (I'm just especulating here) on Microsoft Math, an unexpensive stand alone product I wasn't aware of, that could be a nice present for a high school niece in love with physics or math.