Category Archives: Functional Programming

Functional Spreadsheet in F#

For anyone interested in how to solve a real problem using F#, I suggest reading this post on Developer Fusion. It is an implementation of the core functionality of a spreadsheet. It includes a full parsing and expression evaluation engine, plus databinding and display (silverlight… eww, but it’s mainly so you can try it in your browser). Reading it and looking at the use of Active Patters, Pattern Matching and Discriminated Unions really drives home how language features can lead to clear and concise implementations of algorithms that are often awkward to implement in true OO fashion.

The full code snippet is available here, and can be run inside your browser here.

Recommended.

Tagged , ,

10 One Liners to Impress Your Friends

As a bit of a programming language geek I find that comparing programming languages is a worthwhile exercise mainly because of the different techniques and styles that you are exposed to.
Learning multiple programming languages is one of the best things you can do to gain intuition about the most expressive way to write your code in any language.
No matter how much of an expert you are in a given language, learning a new one is often a humbling and educational experience and one that we should all try to do every so often to keep ourselves sharp.

I’ve seen several articles going around showcasing ‘one-liners’ (single lines of code) in different languages to perform a set of 10 simple tasks.
The first one I saw was done in Scala, and quickly spawned a number of imitations in other languages:

They are worth a look if only for a nice take on FizzBuzz – the Jeff Atwood smoke-test of programmer competency:

Enumerable.Range(1, 15).Select((i)=>i + (i%3==0?"fizz":"") + (i%5==0?"buzz":""));

C# is getting much more expressive with LINQ extension methods and lambda expressions but I think F# still has the edge with some of the inbuilt list processing functions.
Take partitioning a list into two lists based on a predicate in C#:

var passed = new List<int>();
var failed = new List<int>();
(from bucket in new[] { passed, failed } from i in new[] { 49, 58, 76, 82, 88, 90 } select new { bucket, i }).ToList().ForEach((tuple) => tuple.bucket.AddRange(Enumerable.Repeat(tuple, 1).Where((tup) => (tup.bucket == passed && tup.i > 60) || (tup.bucket == failed && tup.i <= 60)).Select((tup) => tup.i)));

Now in F#:

[49; 58; 76; 82; 88; 90] |> List.partition (fun i -> i > 60);;

If you look at the links above and see which language is most expressive for solving each problem you can really start to understand how languages can affect productivity.
Just being Turing Complete isn’t enough these days, and thank god for that

Tagged , , , ,

Y-Combinator in Objective-C

A GitHub user named Joshua Ballenco recently posted a project called y.h.
It’s an implementation of the Y-Combinator which is used in functional programming to achieve recursion using anonymous functions.
Apple is lucky to have talented people trying to make their language nicer to use.
Apple did well adding Blocks(closures) to Objective-C which slightly modernises the language. Unfortunately even with (because of?) Cocoa it’s not very expressive…

I mean look at this:

RecurBlock factorial = YComb((NSNumber *) ^(NSNumber *val) {
if([val compare: [NSNumber numberWithInt: 0]] == NSOrderedSame) {
return [NSNumber numberWithInt:1];
} else {
NSNumber *next_val = this_block([NSNumber numberWithInt:([val intValue] - 1)]);
return [NSNumber numberWithInt:([val intValue] * [next_val intValue])];
}
});

Could well be the least expressive implementation of a recursive factorial ever.
I’m not sure I know what to say…

Maybe MacRuby will save us all!

Tagged , , ,

Method Chaining in C# or “This is not a post about Monads (yet!)”

Looking at the previous post people unfamiliar with F# might have noticed the copious use of

|>

the ‘pipe’ operator.

Essentially, it allows you to chain methods in a more readable way by giving you a binary operator where the left side is a value v and the right side is a function f, the result of the operator is simply f(v);

This can be nice for expressing operations involving lists and the like, but its usefulness extends to pretty much anytime you have to do Something(ToThis(BecauseOfThis(x)));

I thought about how useful it would be to implement the pipeline operator in C# to give the ability to express those operations cleanly.

A simple implementation could be an extension method like this:

public static U AndThen<T,U>(this T val, Func<T, U> f) { return f(val); }

Which would let you write things like this:

var dateInt = "2009/11/03"
. AndThen(x => x.Replace("/","")
. AndThen(x => Convert.ToInt32(x));

Not bad – but what if the Convert.ToInt32 throws an exception?

In normal C# you would have to write a bunch of nested if statements, each time checking for nulls or exceptions, and handle them with several else blocks.
This problem (and how to handle it) is well-understood in functional programming and people have developed a very elegant solution.
I won’t go into what a Monad is in this post (another time!), but what if we had a wrapper class that could turn any class into one that optionally had a value. Kind of like nullable types in .NET (except they can only be used with structs and value types, which motivates this post).

What if you could have something like List? to represent a value that may or may not contain a list of ints?
Let’s call this class Maybe (this implementation is courtesy of this blogger who did a great post on Monads in C# here)

	public class Maybe<T>
	{
	    public readonly static Maybe<T> Nothing = new Maybe<T>();
		
	    public T Value { get; private set; }
		
	    public bool HasValue { get; private set; }
		
	    Maybe()
	    {
	        HasValue = false;
	    }
		
	    public Maybe(T value)
	    {
	        Value = value;
	        HasValue = true;
	    }
	}	

If we add some methods to Maybe , maybe becomes a Monad, but we will talk about what that means in a later post.

With this Maybe class in hand, we can start to define an interface for method chaining that can handle problems that occur during invoking one method in the chain. If one of them has an issue, the result of the entire expression will be Maybe.Nothing.

We can set it up so that if a method lower down the chain gets passed a Nothing, it knows not to do anything but simply pass along the nothing.

We have now encapsulated the control flow of continuously testing for nulls.
I have a quick implementation up here on GitHub that I will likely develop further because there is lots more to explore in this space.

So we can handle exceptions and nulls silently:

			var val = "1234a ".If()
			.And(x => x.Trim())
			.And(x => Convert.ToInt32(x)); //throws exception
			Assert.IsFalse(val.HasValue); //true

			var val = "1234 ".If()
			.And(x => (string)null) //returns null
			.And(x => Convert.ToInt32(x));
			Assert.IsFalse(blah.HasValue); //true

Haskell being a pure functional language represents Exceptions this way, but we live in the .NET world and even in F# we might want side effects or be interacting with libraries that do.
So we can provide functions that are invoked when the value changes from Something to Nothing:

			string errorLog = String.Empty;
			var val = "1234a ".If()
			.And(x => x.Trim())
			.And(x => Convert.ToInt32(x), (x,e)=> errorLog = "couldn't convert integer" + e.ToString());
			Assert.IsFalse(String.IsNullOrEmpty(errorLog));

We also might want to provide a general failure side effect (for logging, say):

			string errorLog = String.Empty;
			var val = "1234a ".If()
			.And(x => x.Trim())
			.And(x => Convert.ToInt32(x))
			.FailWith(()=> errorLog = "operation failed");
			Assert.IsFalse(String.IsNullOrEmpty(errorLog));

This library is useful for method chaining and handling exceptions and other cases, but if you wanted to put in transparent logging or something similar you would still be forced to put it explicitly in the error continuation functions.
This is something that could be handled monadically but I haven’t thought enough about how to integrate that yet with a fluent interface in C#.

In F# you could use computation expressions (Monads!) and so encase all your statements in, say, log {}, as long as you implemented the monadic axioms for log, but syntactically that would end up pretty ugly in C#.

The source for this library is available on GitHub in a collection of functional utility classes I’ve been playing with here.

Check out the unit test project for more examples if you’re interested.

Tagged , , , , , , ,

Closest Pair of Points Problem in F#

A common problem when working with spatial data is the closest-pair-of-points problem.
Wikipedia defines the problem as: given n points in a metric space, find a pair of points with the smallest distance between them.

In a GIS for example, the 2-dimensional (planar) case is of great interest.
A naive solution is to just check each point against all other points and keep track of the shortest distance found so far.
We could call this the ‘brute-force’ solution and this is of course O(n2).
Here’s a pseudocode implementation courtesy of Wikipedia:

minDist = infinity
for each p in P:
for each q in P:
if p ≠ q and dist(p, q) < minDist:
minDist = dist(p, q)
closestPair = (p, q)
return closestPair

It may surprise you to find out that we can do a lot better than this!
There is a divide and conquer strategy that recursively splits the space and solves the sub-problems first.
Take the 2D case for illustration purposes: If we split the plane along a vertical line, find the closest pair on each side of the vertical line, then the only problem left to solve is to find if there is a closer pair where the first item of the pair is on one side of our dividing line, and the second is on the other side.

At this point we are basically where we started – if we examine all the points on the left hand side and all the points on the right we are back at O(n2).
The Wikipedia page has a nice explanation, but the core observation that lets us improve the complexity of the algorithm here is called the ‘sparse-box observation’.
Basically, we only need to check the points from each partition that are close to the dividing line! How close? well, the minimum distance between pairs on either side (because if a point is right on the dividing line, the other point can be that far away and still end up in the pair with the shortest distance).

With this observation in hand, we know that the pair we are looking for is either:

  1. The pair with the shortest distance on the left hand side
  2. The pair with the shortest distance on the right hand side
  3. The pair with the shortest distance where one member of the pair is on the right and one member is on the left

Check those distances and we’re done!

The running time of this algorithm is O(n log n).

You can probably imagine that this algorithm can be extended to higher dimensions and you would be right, we could split along a hyperplane instead of a line and go from there. I may tackle that in a future blog post.

I was surprised to see that there was no F# or Haskell solution on Rosetta Code.

Eran Leiserowitz has been doing a great series on computational geometry in Haskell and covered this problem back in November.
Inspired by the Haskell, I thought I’d try my hand at an F# implementation.

open System

let dist (x1,y1) (x2,y2) = 
 Math.Sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2))

let closestBf points =
 let n = Seq.length points
 let list = points |> Seq.toList
 seq { for i in 0..n-2 do
         for j in i+1..n-1 do
           yield list.[i], list.[j] }
 |> Seq.minBy (fun (a, b) -> dist a b)
 

let rec closestInternal points = 
 match points with
 | _ when points |> Seq.length < 4 -> closestBf points
 | _ -> 
 //partition points about a vertical line
 let sorted = points |> Seq.sortBy(fun (x,y) -> x)
 let left = sorted |> Seq.take((points |> Seq.length)/2)
 let right = sorted |> Seq.skip((points |> Seq.length)/2)
 
 //recurse each side of the vertical line
 let lMin = closestInternal left
 let rMin = closestInternal right
 
 //find minimum distance between closest pairs on each side of the line
 let lDist =
  match lMin with
  | (a,b) -> dist a b
 
 let rDist = 
  match rMin with
  | (a,b) -> dist a b
  
 let minDist = Math.Min(lDist,rDist)
 let dividingX = left |> Seq.toList |> List.rev |> List.head |> fst
 
 //find close points on the right to the dividing line
 let closePoints = 
  right 
  |> Seq.takeWhile(fun (x,y) -> x - dividingX < minDist) 
  |> Seq.sortBy(fun (x,y) -> y)
  
 //take the close points and merge them with the close points to the dividing line on the left hand side
 let pairs = 
  left 
  |> Seq.skipWhile(fun (x,y) -> dividingX - x > minDist) 
  |> Seq.collect(fun (x,y) -> 
   closePoints 
   |> Seq.skipWhile(fun (x1,y1) -> y1 < y - minDist) 
   |> Seq.takeWhile(fun (x2,y2) -> y2 < y + minDist) 
   |> Seq.map(fun a -> ((x,y),a))) 
  |> Seq.toList
 
 //return the closest pair of points from the three groups
 pairs |> List.append [lMin;rMin] |> List.sortBy(fun (a,b) -> dist a b) |> List.head

And.. it works (I think!):

let list = [(2.0,2.0);(0.0,0.0);(2.0,1.0);(5.0,5.0);(9.0,9.0);(10.0,10.0);(8.0,8.0);(4.5,6.0)]
let closest = closestInternal list


val closest : (float * float) * (float * float) = ((2.0, 2.0), (2.0, 1.0))

It’s up on GitHub here, and at FSharp Snippets (which is ridiculously awesome and told me that the F# compiler produced errors when I first pasted in my snippet!) here.

Tagged , , , ,
Follow

Get every new post delivered to your Inbox.

Join 180 other followers