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?
What about this F# solution:
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:
- 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
- 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
- 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?