Developing a mobile application these days is an arduous task.  You need to have a mobile app to get your business noticed and to gain market share with your audience, however which platform do you choose?  Apple?  Android?  Windows Phone?

Cost of developing a mobile app is one of the biggest hurdles besides the choice of platform.  To get an application developed natively in two of the three major mobile operating systems immediately doubles the cost of development.

Each mobile operating system is designed around development in a specific programming language and development environment.

3 different operating systems, 3 separate languages and development environments, and counting.  To be able to cater to all of these operating systems natively, mobile app developers need to have someone able to be an expert in each of these programming languages and also be an expert in the nuances of how each mobile operating system works.  Task lifecycles, multi-threading, memory limitations, garbage collection, etc.

Thus to have 1 app developed in its native language and environment will take 3 times as long. Thus tripling the cost of development.

Cost of Maintenance

Any code written for any one of these is incompatible with the other and needs to be completely rewritten in the native language and development environment so that it’ll work for the target platform.

Because of that there will be subtle differences in the code base for each platform, so any future modifications to the app will require 3 separate changes, one for each language and platform, thus also tripling the long term cost of maintenance.

There is a solution to this dilemma, it’s not a silver bullet, however for most applications cross platform development may be a viable alternative.

Cross Platform Development

One solution to bring costs down is cross-platform development.  Until such time as everyone settles on a specific platform for all mobile phones and tablet devices this will continue to be a huge time and cost saver for people interested in getting a mobile app developed for multiple platforms.

There’s essentially 2 approaches that cross-platform framework developers have taken to solve this particular problem.

  • Web app wrapped as a native app, such as Adobe PhoneGap/Cordova
  • Cross platform tool that creates native apps, such as Xamarin Studio

Mature Frameworks

Both Xamarin and PhoneGap are fairly mature cross-platform development frameworks. Xamarin – Mono project has been worked on and actively developed against since 2001. PhoneGap is less mature than Mono being first developed in 2009, however the concepts behind HTML5 and JavaScript have been around much longer.

High Profile Xamarin Apps

http://xamarin.com/apps


High Profile PhoneGap Apps

http://phonegap.com/app/feature/

PhoneGap

The purpose of PhoneGap is to allow HTML-based web applications to be deployed and installed as native applications. PhoneGap web applications are wrapped in a native application shell, and can be installed via the native app stores for multiple platforms.


Hybrid App

PhoneGap is really a hybrid development platform, neither being truly native, nor purely web-based.  All layout and rendering is done via the Web View.

PhoneGap strives to provide a common API set which is typically unavailable to web applications, such as basic camera access, device contacts, and sensors not already exposed in the browser.

phonegap-architecture-by-ibm-29-july-2011-modules-instead-plug-ins.jpg

To develop PhoneGap applications, developers will create HTML, CSS, and JavaScript files in a local directory, much like developing a static website.  Extending the capabilities of PhoneGap is via the use of plugins for each supported platform.  Plugins are written in each platforms native language and development environment.

If there isn’t a plugin that does what you’d like to do with your device already, you’ll need to revert back to writing native code for each supported platform.  As of writing there are a huge number of open sourced plugins available from the phonegap.com website ranging from Near Field Communication to Instagram and Facebook integration.

https://build.phonegap.com/plugins


Advantages of PhoneGap

  • Supports 7 Platforms (Apple, Android, Windows, Blackberry, Symbian, Bada, webOS)
  • Single Standards compliant UI language (HTML5, CSS, Javascript)
  • OpenSource (Extending and developing plugins or modifying is easy and accessible)
  • Support Packages Available for Developers
  • Developed by Nirobe (ex Novell developers and purchased and supported by Adobe).
  • Free (Open Source)

Xamarin

Xamarin has brought to market its own IDE and snap-in for Visual Studio. The underlying premise of Mono is to create disparate mobile applications using C# while maintaining native UI development strategies.

Essentially this means that you’ll need to have a developer familiar with the User Interface for each platform, which is not ideal however the compromise that they’ve decided to go down has to do with Native look and feel and responsiveness.

Unlike PhoneGap, writing native UI does not have the same limitations placed on it that Web Applications do for real time performance and UI updates.  Xamarin studio has abstracted tools for creating the Native UI for each of the target platforms so developers do not need to buy or open separate IDE’s


Xamarin Architecture

cross_platform_apps_architecture2.png

In addition to creating a visual design platform to develop native applications, they have integrated testing suites, incorporated native library support and a Nuget style component store. Recently they provided iOS visual design through their IDE freeing the developer from requiring to open XCode.

Xamarin has provided a rich Android visual design experience based from work done previously by the eclipse project.  The major advantage and what is truly amazing is the ability to use LINQ to work with collections as well as create custom delegates and events that free developers from objective-C and Java limitations.

Many libraries (not all) work perfectly in all three environments.

There are several advantages of using Xamarin  including

  • Near native performance
  • 100% platform API coverage
  • C# goodness – LINQ, async\await, TPL
  • Code reuse (average 75% code sharing)
  • Testability
  • Shared code between client and server
  • Support
  • Scan your code for conformance scan.xamarin.com

Comparison – Xamarin vs PhoneGap vs Native

Looking at the above table it’s fairly clear that the winner is cross-platform development when compared to native development.  However what’s less clear is the distinction between Xamarin and PhoneGap.

Being able to choose between these two platforms will depend on the particular application that is being developed.


Reasons to choose PhoneGap over Xamarin

  • Application lends itself natively to being a web-app (Reduce UI cost)
  • Cheaper to develop UI per platform
  • Plugins already available for needed features or plugin development is minimal

Reasons to choose Xamarin over PhoneGap

  • Legacy C# application code (code sharing)
  • Requires Native Performance for the UI
  • No need for plugin development for On Device Processing
  • Cross UI development with MVVM cross (allows for common UI code to be shared)

That’s not really a large list, I’ve used both of these products and in my humble opinion, these two products are very comparable.  Xamarin lends itself more towards cross platform development between C# applications and shared code for projects.  Whereas PhoneGap lends itself to be more suitable for “web apps” on mobile with some device capabilities (camera, sms, phone, etc).

No Clear Winner for Small Projects – Xamarin vs PhoneGap

There’s no clear winner in capability between PhoneGap and Xamarin (each of them are both extensible) and each development platform has its advantages and disadvantages for a specific App (cost of development being the most pertinent).  Each platform will need to be evaluated over the lifetime of the App to determine which version will provide the best cost savings for development going forwards.  This is especially true for small projects or projects that little business logic outside of what is available to PhoneGaps’ existing Plugin Library, then these two frameworks fight on equal footing. However…


Xamarin – The Clear winner for Larger / More Complex Projects

I will say for larger projects Xamarin has a clear advantage over PhoneGap.  Harnessing the power of C# and wrapping all native iOS and Android Libraries gives Xamarin ability to scale horizontally (in team size) due to a common language being used, and Vertically by harnessing Strong Typing means that over the course of your project lifetime developers can quickly and easily make changes and improvements to your application.  Additionally there are a multitude of pre-existing libraries which are available to help boot-strap any project which with a little work can be refactored to use the PCL core libraries required to get these working under Mono.Android / Mono.Touch.


References

http://www.eastbanctech.com/10-reasons-for-choosing-xamarin-cross-platform-mobile-development/

http://www.theregister.co.uk/Print/2013/02/25/cross_platform_abstraction/

http://blog.mercdev.com/cross-platform-frameworks/

http://www.eastbanctech.com/10-reasons-for-choosing-xamarin-cross-platform-mobile-development/

http://xamarin.com/

http://phonegap.com/

This tutorial is going to assume that you already have the latest version of Umbraco CMS setup and installed. If not feel free to download and setup the latest version from umbraco.com/download, and the best part is that it’s free and open source.

If you’re unfamiliar with Umbraco CMS and are following along with this tutorial for the first time you can you read their easy-to-follow installation instructions directly from their website.

As part of this tutorial I’ve downloaded and setup a new blog using the blog umbraco skins package, feel free to setup and install any one of these for your first site.  I’m going to modify this slightly for my default domain later on.



To demonstrate a multi-site configuration with umbraco, I’m going to use the following website domains on my local machine.

  1. blog.mammothmedia.com.au
  2. business.mammothmedia.com.au

I’m not going to go into details on how to do this since there are plenty of instructions available on the web.  You’ll also need to setup IIS to point the new domains to your Umbraco installation, note that this is to the SAME umbraco installation.  Umbraco can handle multiple hostnames, we’re going to show you how.

Create some templates

The first item on the agenda is to create some alternative templates so we can tell the difference between our two sites.

I’ve created some new templates called Business, and renamed the default templates to Blog.  This way I can tell the two apart when I setup the content later.


Add new allowed templates to the current document types

Since I’m going to be re-using the same document types for my 2 examples, we’ll need to add the new templates to the allowed structure of the existing document types.

I prefixed my new templates with Business in front so I can tell which ones are going to use the business template.

Create some content

We’re going to separate our content in the Content tree by domain name.


If we right click on the new root domain folder and select “Culture and Hostnames” from the menu


From there we add the associated domain name to the content and we’re done from the Umbraco side.


You’ll have to do this explicitly for each domain.

Set the template for your documents

Business is going to be using the non-default templates which also uses a different style sheet.  So I’ll need to set the template in the documents properties.


Make sure that you do the same for any document which has a different template.

Also don’t forget to save.

Test it out

The final step is to test it out.  If I point my browser to blog.mammothmedia.com.au and I get the following website.


And for business.mammothmedia.com.au


There you have it

Multi-site support with umbraco by example.

Quite often there are a number of heavy items that are loaded on a web page which is located below the fold. These items such as flash movies located at the bottom of a page, or in some instances facebook activity feeds which are located below the fold, simply add to a pages load and response time.

This is especially true for website landing pages where users more often than not are only interested in clicking through to some feature article located above the fold.

Here is a “mini” javascript library which will allow you to lazy load these items below the fold when a user first scrolls down the page. I’ve tested it in IE7, IE8, IE9, FF, Chrome, Safari, Opera etc.

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
var Utilities = {
    RegisteredScrollFuncs: [],
    Timeout: 100,    
    GetScrollPosition: function() {
        var position = [0, 0];
        if (typeof window.pageYOffset != 'undefined') {
            position = [
                window.pageXOffset,
                window.pageYOffset
            ];
        }
        else if (typeof document.documentElement.scrollTop
            != 'undefined' && document.documentElement.scrollTop > 0) {
            position = [
                document.documentElement.scrollLeft,
                document.documentElement.scrollTop
            ];
        }
        else if (typeof document.body.scrollTop != 'undefined') {
            position = [
                document.body.scrollLeft,
                document.body.scrollTop
            ];
        }
        return position;
    },
    RegisterScrollListener: function(func) {
        this.RegisteredScrollFuncs.push(func);
 
        if(this.RegisteredScrollFuncs.length == 1)
            this.PollRegisteredListeners();
    },
    PollRegisteredListeners: function(e) {
 
        if (Utilities.GetScrollPosition()[1] > 0 && Utilities.RegisteredScrollFuncs.length > 0) {
            for (var i = 0; i < Utilities.RegisteredScrollFuncs.length; i++) {
                Utilities.RegisteredScrollFuncs[i]();
            }
            Utilities.RegisteredScrollFuncs = [];            
        }
        else {
            window.setTimeout(Utilities.PollRegisteredListeners, Utilities.Timeout);            
        }   
    },
    LoadFacebookActivity: function(d, s, id) {
        var js, fjs = d.getElementsByTagName(s)[0];
        if (d.getElementById(id)) return;
        js = d.createElement(s); js.id = id;
        js.src = "//connect.facebook.net/en_US/all.js#xfbml=1&appId=122480627837535";
        fjs.parentNode.insertBefore(js, fjs);
    }
}

The code above is actually very simple.

Stepping through the code

  1. RegisterScrollListener accepts a function as an argument and adds that function to an array.
  2. On the very first item which is added to the array it then kicks off the timer to poll the scroll bar position every 100ms.
  3. Once the scroll bar has moved, it will then run through the array of functions calling each one in turn.

And there we have it, a lazy polling solution that will allow us to perform any action that we desire when the user scrolls down the page.

Usage:

To use the library is very simple, there is no need to add anything to an onload method. Merely call

Utilities.RegisterScrollListener(callback);

where callback is a pre-defined function you want to occur once the user has scrolled down the page.

In this instance we’re going to load the facebook activity widget.

1
2
3
4
5
6
7
8
9
10
<div id="onfacebook" class="onfacebook"></div>      
    <script type="text/javascript">
        var onfacebook = '<h2>Your site on <b>Facebook</b></h2>'
                + '<div class="fb-like-box" data-href="http://www.facebook.com/YourSite" data-width="312" data-show-faces="true" data-stream="true" data-header="false"></div>';
 
            Utilities.RegisterScrollListener(function() {
                Utilities.LoadFacebookActivity(document, 'script', 'facebook-jssdk');
                document.getElementById("onfacebook").innerHTML = onfacebook;
            });            
    </script>

So there you have it, let me know if you find this useful.

What is software craftsmanship?

In a previous blog post I attempted to define some of the fundamental concepts of what it is that I do on a daily basis. In the process of defining said foundations, I stumbled and stubbed my toe on another concept. Hidden inside the other, not unlike the layers of a matryoshka doll. The concept of software craftsmanship.

Software craftsmanship is a bottom up approach to software development by emphasizing the coding skills of the developers themselves. Traditionally software engineering practictioners were encouraged to see themselves as part of a well defined statistical analysis and mathematical rigor of an engineer with the benefits of introducing professionalism, predictability, precision, and mitigated risk.

The reason that this approach is fundamentally flawed is unquestionable. Software engineering as a field of study is far too immature and is constantly in a state of flux.

For civil engineering there exists well defined and well understood ways for constructing bridges and buildings that is safe for people to use and inhabit. A person who designs a bridge can be certain that the people constructing that bridge know how to read the blueprint, and what all the symbols and formulae mean.

No such generally accepted blueprints exist for software engineering. Everything can be done in a multitude of ways with different methods and ideology at its core.

Not unlike the guild traditions of medieval europe software development is a craft that has developed a body of wisdom, most of which isn’t taught at universities nor in certification classes. Most developers arrive at these tricks of the trade by independent experimentation, or more recently from learning from their peers and mentors.

Tools of the Software Craftsman

Learning how to use the tools of the trade is a core concept for producing quality code. Here is a list of some of the tools used to increase the quality, extendability, reliability of code.

  1. Use a version control system, like subversion, mercurial or git
    Source control is like a time machine for your code, you can always go back in time.
  2. Use a continuous integration tool like cruise control
    Continuous integration implements a continuous process of applying quality control to daily or nightly builds.
  3. Have a centralized bug tracking system like RT or BugTrac
    This is essential to maintaining software.
  4. For web development, use an automated build and deploy script
    If you don’t have an automated build and deploy script you may have problems
  5. Design software to be easily tested (Test Driven Development)
    Loose coupling promotes software that is more modular, and is easier to extend and maintain.
  6. Refactor early, refactor often
    Just as you would maintain a 747, fix the root of the problem when it needs it.
  7. Be pragmatic with project management
    Good, fast, cheap, pick TWO.
  8. Be aware of technical debt
    Technical debt is a balancing act, be sure to pay off your debts before they crush you.
  9. DRY – Dont repeat yourself
    Knowledge must have a single, unambiguous, authoritative representation within a system.
  10. YAGNI – You Aint Gonna Need It
    Implement features when you actually need them, not when you forsee you need them.
  11. Fix broken windows
    Fix broken design and poor code whenever you see them.
  12. Reduce cyclomatic complexity
    Reducing nested brackets will reduce cyclomatic complexity and increase readability and maintainability.
  13. Estimate before you start
    This will help you to spot potential problems up front
  14. Iterate your project schedule with code
    Use experience gained with the project to redefine the project time scales.
  15. Use an ubiquitous language
    Design and code in a common language that your users understand.
  16. Use exceptions for exceptional circumstances
    Handle anticipated problems in code. Reserve exceptions for exceptional things.
  17. Refactor to patterns
    See Gang of Four Design Patterns at the bottom of this essay.

Read the rest of this entry »

MapReduce is one of “those” buzz words that is going around at the moment. Mostly in part due to Google using it so successfully for their distributed indexing algorithms.

So what is MapReduce?

According to Wikipedia [http://en.wikipedia.org/wiki/MapReduce]

So MapReduce is an amalgamation of two higher order functions taken from functional programming.

Map and Reduce :. MapReduce.

Google took the concepts of Map and Reduce and designed a distributed computing framework around those two concepts. As it’s almost infinitely horizontally scalable, it lends itself to distributed computing quite easily.

So lets break up MapReduce into its 2 main components.
Read the rest of this entry »

What is software engineering?

If you’re in the industry or looking to get into the industry you’ll find yourself a little confused as to some of the labels and roles given to computer programmers.

  • Programmer
  • Developer
  • Analyst
  • Architect
  • Engineer

The first two terms are freely interchangeable, the dictionary term for a programmer is one who programs, the term for developer is one who develops. So is there a difference in the terms or the roles? No effectively these two terms are identical and is merely a preference in terminology. Even microsoft uses these terms interchangeably for their internal developers.

An analyst might not actually write code, in a lot of instances this will be a business analyst, someone who understands the business and also understands how to translate the business needs into terms that can be digested by a team of programmers or engineers. An analysts primary function is to write the specification or requirements documents required for a new project.

A software architect, is very much like the traditional architect. They are responsible for building the framework and designing the tools that the team will be using to develop the project. Software architects are senior level developers who have had years of experience in developing software and can quickly turn a functional specification into a framework which is maintainable and future proof. A software architect can also be responsible for mentoring the rest of the development team in how to use the framework.

An engineer is none of the above and could be any of the above. A software engineer is someone that subscribes to an engineering discipline.

Definition of software engineering

Software engineering is the “systematic approach to the analysis, design, assessment, implementation, test, maintenance and reengineering of software, that is, the application of engineering to software” [1]

Universities can’t teach you software engineering.

University

This is a crucial distinction to make because after 3-4 years of going to university to earn your degree and learning how to program computers in various languages. Designing relational database models, writing functional and requirements specifications, you are not actually qualified to start writing production quality code. Not without someone to mentor you. Or for that matter you are definitely not experienced enough to architect a solution for a company.

Read the rest of this entry »

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?

About Justin

justin

Justin is a .NET Team Lead for Mammoth 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 and 3D Printers.

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

  • Justin: Hi Alex, Thanks for the tip, I'll have to check out Xamarin Forms. I've been using MVVMCross a [...]
  • Alex Danvy: Hi, I would add 2 points : - Xamarin Forms allows to create shared code for (simple) UI. SHaring m [...]
  • Justin: Trog: This is off-topic to the point of the article. I'm using the term "software engineering" here [...]
  • trog: It should be noted that some fields will not hire a "software engineer" unless they are an actual, a [...]
  • Tonja: Nice work dude. [...]