Problems with the .NET 3.5 implementation

During implementation of the same algorithm from Haskell to (Functional) C#, I found that I hit quite a large snag with .NET (3.5) number types. A fibonacci sequence very quickly accumulates into integers larger than an Unsigned Long can contain, in which case you would have to move to using .NET 4.0 / F# BigInt to get the benefits of using their operators. The below code works very well within the problem domain, however you will need to refactor this to use BigInt if you wish to move into larger Fibonnaci sequences.

Project Euler – Problem 2

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, …
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Haskell

module Main where
main = do
  let fibs = map fst $ iterate(\(a,b) -> (b,a+b)) (1,2)
  print $ sum(takeWhile(< 4000000) (filter even fibs))
Function Description
\ The backslash in this context is representing that the following code is a lambda (λ)
iterate Creates an infinite list where the first item is calculated by applying the function on the secod argument, the second item by applying the function on the previous result and so on.
$ The ‘$’ operator is for substituting parenthesis. Anything appearing after it will take precedence over anything that comes before.
fst Returns the first item in a tuple eg. fst (1,2) returns 1
map Returns a list constructed by applying a function (the first argument) to all items in a list passed as the second argument
filter returns a list constructed from members of a list (the second argument) fulfilling a condition given by the first argument
even returns True if the integral is even, False otherwise.
takeWhile creates a list from another one, it inspects the original list and takes from it its elements to the moment when the condition fails, then it stops processing
sum computes a sum of all elements in the list

Armed with the knowledge of what each of the above functions do, we can now translate the above code. Like most functional programs we read the code right to left meaning that the code on the right is passed to the code to the left of the chain.

given a list of even fibonnaci numbers
whose number doesn’t exceed 4 million
return the sum

Which is almost identical to the c# implementation using a YCombinator.

C# Implementation using YCombinator

public void Main()
{
	var sum = Fibbonacci(1, 2, Int32.MaxValue)
				.TakeWhile(x => x < 4000000)
				.Where(x => x % 2 == 0)
				.Sum();
 
     Console.WriteLine(sum);              
     Console.ReadLine();
}
 
 private delegate Func<TA, TB, TC, TR> Recursive<TA, TB, TC, TR>(Recursive<TA, TB, TC, TR> r);
 
  // Y Combinator
  private static Func<TA, TB, TC, TR> Y<TA,TB,TC,TR>(Func<Func<TA,TB,TC,TR>, Func<TA,TB,TC,TR>> f)
  {
        Recursive<TA,TB,TC,TR> rec = r => (a, b, c) => f(r(r))(a, b, c);
        return rec(rec);
  }
 
  private readonly Func<long, long, long, IEnumerable<long>> Fibbonacci = Y<long, long, long, IEnumerable<long>>(
        f => (n, m, cap) => n + m > cap
              ? Enumerable.Empty<long>()
              : Enumerable.Repeat(n + m, 1).Concat(f(m, n + m, cap))
  );

This c# solution does have a few issues, as pointed out earlier, additionally it doesn’t produce a real fibonnaci sequence even though it returns the same answer it drops the first two elements of the sequence.

1
  return new List<long> {1,1}.Concat(Fibbonacci(1, 1, Int32.MaxValue))

Additionally you’ll notice that I’ve put in a check there so that we don’t cause stack overflow errors in adding numbers larger than Int.MaxValue. I believe refactoring to use BigInt should alleviate the need for this check.

If you’re wondering what is this YCombinator, see my previous post => Recursive lambda expressions in C# using YCombinator

Lambda calculus can be summed up doing very much with very little, sacrificing only readability.

Personally i’ve found the inability to peform recusion with a lambda expression to be a little pain in what should be an elegant solution. Lets take a factorial for instance, how to write that as a lambda expression? The fathers of lambda calculus who invented lambda expressions in the 1930’s came up with a solution.

What is a lambda expression

A lambda expression simply put is an anonymous function that contains expressions or statements, it can be used to create delegates or expression tree types. All lambda expressions use the lambda operator =>, which reads ‘goes to’.

1
x => x * 2;

Would read, x goes to x times 2.

Lambda recursion using self replication and self application

The basics of getting a lambda expression to recurse upon itself uses self application. Take a function, that accepts a function and applies that to itself.

1
f => f(f);

For this situation we can’t really give it a Func<> type, so we define a special delegate.

1
2
3
4
5
6
7
delegate T Recursive<T>(Recursive<T> self);
 
// We can now apply the self application
Recursive<int> lambda = f => f(f);
 
// What happens if we do this
lambda(lambda);  // Infinite recursion.

This while not practical is useful in knowing that we can get a lambda to call iteself. Now all we need to do is make it useful.

Currying
Lamdas give us great syntax for creating delegates or little functions you can assign to a variable.

1
2
Func<int, int, int> add = (x, y) => x + y;
int a = add(3,4);  // a = 7

You can use the lambda syntax to build an add function that within it returns a function that is waiting for the other side of the add expression

1
2
Func<int, Func<int, int>> curriedAdd = x => y => x + y;
int b = curriedAdd(2)(3); // b = 5

The result is the same, aside from the syntax.

We can now curry the curriedAdd function by supplying one argument and then use our new add6 function as many times as we like.

1
2
3
4
var add6 = curriedAdd(6);
 
int c = add6(3);  // c = 9
int d = add6(5); // d = 11

Thankfully you don’t have to define your curried function when you’ve got a ‘Curry’ function to create it for you. Take an example that adds 4 things together.

1
2
3
4
5
6
7
8
9
10
11
Func<int, int, int, int, int> addFourThings = (a, b, c, d) => a + b + c + d;
 
var curriedAddFourThings = Curry(addFourThings);
 
int result = curriedAddFourThings(1)(2)(3)(4); // result = 10
 
var addOne = curriedAddFourThings(1);
var addOneTwo = addOne(2);
var addOneTwoThree = addOneTwo(3);
 
int result2 = addOneTwoThree(4); // result 2 = 10

Here is the set of Curry function overloads

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public Func<T1, Func<T2, T3>> Curry<T1, T2, T3>(Func<T1, T2, T3> function)
{
    return a => b => function(a, b);
}
 
public Func<T1, Func<T2, Func<T3, T4>>> Curry<T1, T2, T3, T4>(Func<T1, T2, T3, T4> function)
{
    return a => b => c => function(a, b, c);
}
 
public Func<T1, Func<T2, Func<T3, Func<T4, T5>>>> Curry<T1, T2, T3, T4, T5>(Func<T1, T2, T3, T4, T5> function)
{
    return a => b => c => d => function(a, b, c, d);
}

You may noticed that we’re going to be using currying for the next section.

Y combinator

Haskell Curry and Alan Turing both came up with ways to write lambda expressions that has the same self application and replication as lambda specified above. Their version however also replicates something else, the application of a given function (these have come to be known as Y-Combinators).

A Y-Combinator can be described roughly as “Give me myself and a higher order function f, and i’ll return a function that is a fixed point of f

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Program
{
	static void Main()
	{		
		Console.WriteLine(fact(6));
		Console.ReadKey();
	}
 
	delegate Func<T1, T2> Recursive<T1, T2>(Recursive<T1, T2> r);
 
	// The Y Combinator
	static Func<T1, T2> Y<T1, T2>(Func<Func<T1, T2>, Func<T1, T2>> f)
	{
		Recursive<T1, T2> rec = r => a => f(r(r))(a);
		return rec(rec);
	}
 
	// The Fixed Point Generator
	static Func<long, long> fact = Y<long, long>(f => n => n > 1 ? n * f(n - 1) : 1);
}

Note that we are passing in the lambda expression into the Y Combinator

So what’s actually occurring above?

First Y is a lambda expression, so there’s nothing to evaluate or execute.

1
 Y = y => f => x => f(y(y)(f))(x)

Next we evaluate the fixed point function (which I’ve actually summarised into the return statement of the Y Combinator).

1
 F = Y(Y) = f => x => f(Y(Y))(f))(x)

The higher order function F is a lambda so nothing to evaluate:

1
 F = fac => x => x > 1 ? x * fac(x - 1) : 1

Finally it gets to the lambda expression and then recurses through itself, because it’s defined as taking itself and an argument and applying it.

Now that you’re armed with the Y-Combinator see if you can do Project Euler – Problem 2 using the Y-Combinator. I’ll be posting my answer shortly.

Learning a new programming language is perhaps one of the most rewarding experiences. You can learn about how another language performs a task, if it seems simpler how does this compare to your current language?

Problem 4 from Project Euler goes something like the folowing.

A palindromic number reads the same both ways.

The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

Find the largest palindrome made from the product of two 3-digit numbers.

Haskell

1
2
3
4
5
6
7
8
9
10
11
12
13
module Main where
 
main = putStrLn output
output = show result
 
largestpalindrome :: Int
largestpalindrome = maximum [ p | i <- [100..999],
                           j <- [i..999],
                           let p = i * j,
                           let t = show p,
                           t == reverse t]
 
result = largestpalindrome

I almost missed this part in the actual question “A palindromic number reads the same both ways”. So a number is a palindrome if its string representation is equal to its reversed string representation.

The solution in Haskell relies on Generators and List Comprehension. In this case we’re generating a list of numbers using sequences, and then filtering that list by the numbers which read the same back to front.

In the above case you can read the function as follows.

Select the largest number from
the product of 2 3 digit numbers
where string of the product is equal to the reverse of the string of product

Based on that algorithm, here’s the c# version using linq

C# using Linq

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
static void Main()
{		
	Console.WriteLine(
		string.Format("Largest Palindrome of the product of 3 digit numbers is: {0}", 
			Palindrome(ThreeDigitProducts()).Max())
		);
	Console.ReadKey();
}
 
private static IEnumerable<int> ThreeDigitProducts()
{
	return from i in Sequence(100, 999)
		 from j in Sequence(i, 999)
		 select i*j;				   				   
}
 
private static IEnumerable<int> Palindrome(IEnumerable<int> seedProducts)
{
	return from p in seedProducts
	       where p.ToString() == new string (p.ToString().Reverse().ToArray())
	       select p;
}
 
private static IEnumerable<int> Sequence(int from, int to)
{
	return Enumerable.Range(from, to).Where(x => x < to);
}

I have to say that I was quite surprised at how easy it was to generate near functional syntax in c# using linq.

Comments?

Learning haskell has its challenges. Most notably the terseness of the function composition, giving IMO a longer learning curve to master the syntax. This terseness is due to its roots in mathematics and academia, and so the functions read unsurprisingly like algebraic formulas.

I’ve been working my way through Project Euler to learn haskell in a more in-depth way than I would following a tutorial.

One of the biggest challenges I faced was to generate prime numbers in a reasonable response time, as can be found in Problem 3. Researching I found that prime numbers can be generated using the sieve of eratosthenes.

My first naieve approach to generating prime numbers.

1
2
3
primes :: [Integer]
primes =  sieve [2..]
  where sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p > 0]

The above code worked fine with the example provided by problem 3, however it took too long to evaluate. My second naive approach was to reduce the amount of checking by eliminating even numbers (no even number can be a prime).

What else can be done to speed up this function? In mathematics there’s a rule which states if a prime factor exists that is GREATER than the square root of the number, then there must be one LESS than the square root. So how does that work?

By testing all primes less than the square root of N, and found none is a factor of N. We can stop, because we know there can be no prime factor of N that is greater than the square root of N. Because, if there were, then there would also be a prime factor less than the square root of N, and we have already found out that there is none.

1
2
primes = 2: sieve [3,5..] where
  sieve (p:xs) = p : sieve [x | x <- xs, (x < p*p) || (x `mod` p > 0)]

Once again this took too long to evaluate, even with the square root short circuiting this only gave up to a 20% increase in speed.

So what can we do further?

I had to research this one, and found an answer on Haskell Wiki. We can add in a deferred filter. Note that I can’t take credit for the below code.

1
2
3
4
5
primes :: [Integer]
primes = 2: 3: sieve (tail primes) [5,7..]  
 
sieve (p:ps) xs = h ++ sieve ps [x | x <- t, rem x p /=0]
  where (h,~(_:t)) = span(< p*p) xs

span – given a predicate and a list, splits the list into two lists (returned as a tuple) such that elements in the first list are taken from the head of the list while the predicate is satisfied, and elements in the second list are the remaining elements from the list once the predicate is not satisfied.

tilde ~ – the tilde forces the compiler to not evaluate the value of the 2nd argument until it is actually used.

What is occurring above is using the span function to evaluate the square roots of h, however the tilde ~ forces the compiler to perform lazy evaluation on t until its value is actually required.

Netsuperbrain.com has a very good article on lazy pattern matching.

Effectively by combining a short circuit, and lazy pattern matching. We can now generate large quantities of prime numbers very very quickly.

I thought this would be worth writing up for a couple of reasons. Trying to research what the tilde operator actually does was quite frustrating, I knew that I had to stop haskell from evaluating the 2nd argument in the case of a match to the first. In addition the sieve of eratosthenes and researching the nature of prime number factors, also combined into learning more about the problem domain and so a more efficient program by an order of magnitude of about 20x.

Let me know if I’ve gotten anything wrong?

Learning haskell recently has really highlighted the power of the built in classes of haskell.

Compare a function in haskell to captialize the first letter in a sentence, vs c#.

Haskell

1
2
3
4
5
import Data.Char
 
sentenceCase :: [Char] -> [Char]
sentenceCase [] = []
sentenceCase (x:xs) = [toUpper x] ++ map toLower xs

I think to be fair I should explain what the above function does.

  1. The first line is the type definition, states that the function will accept a list of chars (a string) and return a list of chars.
  2. The second line is a pattern match, in that if an empty string is provided then it will return an empty string.
  3. The third line is also a pattern match, however will only be accepted if the first pattern is passed over
  4. So in this case it will be run when accepting a non-empty string as it’s input parameter.
Function Description
sentenceCase The name of the function
(x:xs) The brackets are grouping the notation x:xs together so it’s evaluated as a single argument.
x:xs Is actually a special list shorthand that says for list xs, let the value x be the first element and xs be the remainder. Additionally this could be expressed as a:b:c:xs, abc representing the first 3 elements of the list and xs representing the remainder.
[] The left and right square brackets represent a list, so in this case we’re creating a new list filled with 1 character which will be uppercase.
toUpper From the Data.Char library accepts a Char and returns an upper case Char
toLower From the Data.Char library accepts a Char and returns a lower case Char
map Is a built in library function which performs a function on each individual member of a list and returns a resulting list. ie map (\x -> x * 2) [1,2,3] will return a list with the function (x * 2) applied to each of its elements [2,4,6]
++ Concatenates two lists.

So in 1 line of code you could read the above function as taking a list of characters, return the first element as uppercase and the remainder as lowercase.

Vs C#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static string ToSentenceCase(this string original)
{
	return String.IsNullOrEmpty(original) 
		? original 
		: string.Format("{0}{1}", Head(original).ToUpper(), Tail(original).ToLower());
}
 
public static string Head(this string original)
{
	return String.IsNullOrEmpty(original) 
		? original 
		: original.First().ToString();
}
 
public static string Tail(this string original)
{
	return String.IsNullOrEmpty(original) 
		? original 
		: original.Substring(1, original.Length - 1);
}

To be fair, c# doesn’t have a Head or Tail method built in. However even using extension classes, the built in pattern matching from Haskell seems to be a far nicer solution language wise than c#.

Is there a way to refactor this c# code futher?

Including an embedded resource into your Nant script is not difficult at all.

Simply add a resources tag and include the Full Namespace. Note that you will also need to include /Path/To/Resource/File.resx in the include if you don’t have the resource file under the root folder of your library.

Here’s a working example.

1
2
3
4
5
6
7
8
9
10
11
12
<csc target="library" output="../bin/Domain.dll" doc="../bin/Domain.dll.xml" debug="${debug}" warnaserror="true">
     <sources>
	<include name="**.cs" />
     </sources>
     <references>
          <include name="System.Configuration.dll" />
          <!-- other includes removed for brevity -->
      </references>
      <resources prefix="Domain.Tests.Resource">
        <include name="Tests/Resource/TestFixtureResource.resx" />
      </resources>
</csc>

Someone once wrote: Build IT and they shall come.

We came, we saw, and we rejoiced. For it was Developer Developer Developer Sydney. And it was awesome!

One of the largest free developer turnouts that I have had the privilege to attend. Rumors on the day were that over 150 .NET developers over Sydney and Brisbane (and possibly other areas) converged on the Microsoft headquarters for free coffee and a lot of nerd talk.


Scott Hanselman speaking at DDDSydney. (Photo courtesy of rbanks)

Windows Phone 7

There are probably a lot of rumors that are going around about how Microsoft will be marketing the new windows phone 7. What I can tell most definitely is that the new phone is NOT a normal windows phone. Microsoft have woken up and smelled their own manure when it came to PDA’s and phones and decided to do it differently, and by differently I mean taking the best parts of apples iPhone and Googles Android and making a hybrid clone.

Read the rest of this entry »

Here’s a helper that will allow you to compare 2 objects using reflection.

Note: that this will also go through the objects base class and compare the base class fields and properties. I found it necessary to do this, however for speed you may want to add BindingFlags.DeclaredOnly to type.GetProperties() and type.GetFields() to limit the depth of the comparison.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public static class Helper<t>
{
	public static bool Compare(T x, T y)
	{
		var type = typeof(T);
		var properties = type.GetProperties();
		var fields = type.GetFields();			
 
		foreach (var p in properties)
		{
			var valueOfX = p.GetValue(x, null) as IComparable;
			if (valueOfX == null)
				continue;
			var valueOfY = p.GetValue(y, null);
			if (valueOfX .CompareTo(valueOfY) != 0)
				return false;
		}
 
		foreach (var f in fields)
		{
			var valueOfX = f.GetValue(x) as IComparable;
			if (valueOfX == null)
				continue;
			var valueOfY = f.GetValue(y);
			if (valueOfX.CompareTo(valueOfY) != 0)
				return false;
		}
 
		return true;
	}
}
</t>

Read the rest of this entry »

Every now and again it’s necessary to resolve a dependency at runtime. When this happens you don’t really have much of a choice but to insert mock objects into your test fixtures IoC container. The following patterns allow me to specify 1 abstract base class and have all dependent unit tests inherit these stubs thus satisfying their dependencies.

An example class that uses a service locator pattern. Note: This will also work for constructor based dependency injection as well.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public class CustomerLeaseTerm
{
    public virtual Lease Lease { get; set; }
    public virtual Invoice Invoice { get; set; }
    public virtual long AdditionalDataTransfer  { get; set; }
 
    // Lazy Load the Additional Data Transfer Broker using the Service Locator Pattern
    private IAdditionalDataTransferBroker _additionalDataTransferBroker = null;
    public virtual IAdditionalDataTransferBroker AdditionalDataTransferBroker
    {
        get { 
            return _additionalDataTransferBroker 
                ?? (_additionalDataTransferBroker = IoC.Resolve<iadditionaldatatransferbroker>()); 
         }
    }
 
    // Return a calculated cost at runtime using the Additional Data Transfer Broker
    public virtual decimal AdditionalDataTransferCost { 
      get 
      {
          return AdditionalDataTransferBroker
                   .GetByUnitsInGigabytes(AdditionalDataTransfer)
                   .EffectiveCost;
      }
    }  
 
   (...)
 
}
</iadditionaldatatransferbroker>

Read the rest of this entry »

If you don’t have an automated build and deploy script to deploy your latest web application to IIS7 you may have problems.

Here is a solution that uses Cygwin and SSH that can allow you to build your application once and deploy to as many windows servers as you’d like.

What you’ll need

Installing Cygwin on your Windows Server

Download Cygwin and and install the following packages:

  • wget
  • openssh
  • openssl
  • zip
  • unzip

Read the rest of this entry »

About Justin

justin

Justin is a Senior Software Engineer living in Brisbane. A Polyglot Developer proficient in multiple programming languages including [C#, C/C++, Java, Android, Ruby..]. He's currently taking an active interest in Teaching Kids to Code, Functional Programming, Robotics, 3D Printers, RC Quad-Copters and Augmented Reality.

About This Blog

Software Engineering is an art form, a tricky art form that takes as much raw talent as it does technical know how. I'll be posting articles on professional tips and tricks, dos and donts, and tutorials.

profile for Justin Shield on Stack Exchange, a network of free, community-driven Q&A sites

Photostream