## Point distance, imperative vs. functional style

Let’s consider a silly simple algebra problem: given a specific point and a set of several other points, find the closest point in the set to the given point. One C# solution is:

1     static class PointMath

2     {

3         static double Distance(Point p1, Point p2)

4         {

5             double xDist = p1.X - p2.X;

6             double yDist = p1.Y - p2.Y;

7             return Math.Sqrt(xDist * xDist + yDist * yDist);

8         }

9

10         public static Point ClosestPoint(Point p, IList<Point> points)

11         {

12             double shortestDistance = Double.PositiveInfinity;

13             Point closestPoint = null;

14

15             foreach (var point in points)

16             {

17                 double distance = Distance(p, point);

18                 if (distance < shortestDistance)

19                 {

20                     shortestDistance = distance;

21                     closestPoint = point;

22                 }

23             }

24

25             return closestPoint;

26         }

27     }

The Distance() function finds the distance between two points with good ol’ Pythagoras, the ClosestPoint() function does the classic loop: traverse the points list and calculate every distance, if you find a smaller one, keep it and the also keep the current point, at the end return the last point you kept. Easy, but with declarations, curly braces and whatnot, the solution takes 27 lines, OK, 14 lines if we ignore the blank lines and the curly-braces-only lines. And we didn’t even show the Point class definition… Can we do any better?

1 let distance (x1, y1) (x2, y2) : double =

2   let xDistance = x1 - x2

3   let yDistance = y1 - y2

4   sqrt (xDistance * xDistance + yDistance * yDistance)

5

6 let closestPoint toPoint fromPoints = List.min_by (distance toPoint) fromPoints

The distance function is almost a clone of its C# cousin, the sexy one is the closestPoint function: just one line! Let’s try to dissect it a little bit:

1. The List.min_by function expects two parameters: the last one is the list from where the minimum will be picked, the first one is the function that will be used to compare the items
2. As I said, distance expects two parameters, but we are providing just one (toPoint), what are we accomplishing with this? Well, to begin with, the type of the distance function is (my apologies for the relaxed syntax) Point x Point –> double (i.e. distance takes two points and returns one double). If we fix one of those parameters (for example saying distance (0.5, 0.5) ), what we are actually doing is to define a new function of type Point –> double, this new function only knows how to calculate distances to the point (0.5, 0.5). In our case, in line 6 we have created a function that knows how to calculate the distances to toPoint
3. So, List_min_by finds the point in fromPoint closest to toPoint, calculate every distance to toPoint and keeping the fromPoints member with the shortest distance

I can hear some of you complaining about the fact that closestPoint may have taken just one line of code, but it took seven lines of explanation, but this is mainly because we are not used to the language, once you have familiarity with F#, the meaning of line 6 comes quite naturally. Any small imperative problem that you would like to see solved in a functional style?

Published Thursday, September 18, 2008 10:58 PM by Edgar Sánchez

#### # re: Point distance, imperative vs. functional style

Friday, September 19, 2008 6:44 AM by andyclap

But you've missed out the implementation of min_by in your F# count of lines... considering the C# code is mostly a special case min_by implementation, the comparison is a little unfair. It's like saying language X is better because it has a larger library of functions...

What however is worth emphasising is that using functional programming can reduce the complexity of your programs:

In C#3 you could implement a min_by extender on an enumerable that takes a lamda of item => comparable.

As with the sample F#, the code that subsequently uses this min_by doesn't need to worry about the implementation of the min-finding algorithm. All three concerns (distance, min-finding and getting the closes point) are nicely separated and the code is simply better.

#### # re: Point distance, imperative vs. functional style

Friday, September 19, 2008 7:36 AM by PSteele

You could do a one-line LINQ query to find the closest point:

var closest = (from p in points orderby Distance(ourPoint, p) ascending select p).Take(1);

#### # re: Point distance, imperative vs. functional style

Friday, September 19, 2008 7:54 AM by Edgar Sánchez

@andyclap,

Yes, you could give a functional-style solution to the problem in C# 3.0 and then it would be almost as simple and elegant as the F# one (and in a more familiar syntax!). I was trying to make a point for the functional paradigm more than for any specific language, and in that sense I think we both agree.

#### # re: Point distance, imperative vs. functional style

Friday, September 19, 2008 7:57 AM by Edgar Sánchez

@PSteele,

Nice solution! (although I personally prefer the lambda notation to the SQL-like notation of LINQ). The one thing that is bugging me is the "orderby ... ascending", I think it's too much processing work for just getting the min value... I'll think about a lighter alternative...

#### # re: Point distance, imperative vs. functional style

Friday, September 19, 2008 1:21 PM by Jeremy Gray

@PSteele, Edgar, and Rik - LINQ has a Min function, so you can get it down to an even shorter one-liner without the need for the orderby/ascending/take.

#### # re: Point distance, imperative vs. functional style

Friday, September 19, 2008 4:15 PM by Rik Hemsley

Jeremy, please show us how. I'm always interested in more elegant solutions.

#### # re: Point distance, imperative vs. functional style

Saturday, September 20, 2008 12:10 PM by Rik Hemsley

Aggregate with an anonymous type is a nice way of doing it, Jeff. If for some reason I didn't have the time/inclination to write a helper like MinBy, I would probably go for that solution.

Thanks for pointing out the iterator problem with my MinBy. As soon as it passed the tests I forgot about it. - I must remember to fix it before I use it for anything else!

#### # re: Point distance, imperative vs. functional style

Saturday, November 1, 2008 3:37 AM by Jorge

I love that VS theme, is there any way I could get it?

#### # re: Point distance, imperative vs. functional style

Monday, November 3, 2008 1:19 AM by Jorge

Nevermind, found it in your Spanish blog. Great blog by the way.

#### # re: Point distance, imperative vs. functional style

Monday, November 17, 2008 10:07 AM by Jay D

I think the main point here is that you have curried functions in F#, which makes it more powerful

#### # re: Point distance, imperative vs. functional style

Sunday, April 19, 2009 8:55 AM by Kornel

What about the closest pair of points (in a set of points)? Would you be able to implement a O(nlogn) solution in F#? That would be really interesting :)

#### # re: Point distance, imperative vs. functional style

Tuesday, January 5, 2010 11:24 AM by banger

You should include the length of code used to implement min_by as well. It is pretty unfair to include library constructs in one but build the other from scratch (I've also re-wrote min, because you don't use it in C#).

let min_by f ls =

let min a b = if a < b then a else b in

let rec min_by cmin = function

| [] -> min

| x::xs -> min_by (min (f x) cmin) xs

in

match ls with

| [] -> failwith "Empty list"

| x::xs -> min_by (f x) xs

Now don't get me wrong, this is pretty short, and really doesn't affect your results, but it's dishonest not to include it.

#### # re: Point distance, imperative vs. functional style

Friday, January 22, 2010 9:35 PM by AngreeDealer

Don't stop posting such stories. I love to read stories like this. By the way add more pics :)

#### # re: Point distance, imperative vs. functional style

Thursday, February 11, 2010 12:52 PM by MarkRight

Nice post you got here. I'd like to read a bit more about that theme. Thnx for giving this material.

#### # re: Point distance, imperative vs. functional style

Sunday, January 29, 2012 12:46 AM by ReageasencyuI

Если потерять чувство юмора, что останется?

<a href=http://xn--c1aeb8eua.xn--p1ai/>сказка постановка юмор</a>