The following is based on the

Haversine formula task on Rossetta Code. The

Haversine formula is used to find the distance between two points on a sphere using latitudes and longitudes. Let's start with the imperative code; Below are the C and Java versions of the code.

**Code:**

//C version

#include <stdio.h>

#include <stdlib.h>

#include <math.h>

#define R 6371

#define TO_RAD (3.1415926536 / 180)

double dist(double th1, double ph1, double th2, double ph2)

{

double dx, dy, dz;

ph1 -= ph2;

ph1 *= TO_RAD, th1 *= TO_RAD, th2 *= TO_RAD;

dz = sin(th1) - sin(th2);

dx = cos(ph1) * cos(th1) - cos(th2);

dy = sin(ph1) * cos(th1);

return asin(sqrt(dx * dx + dy * dy + dz * dz) / 2) * 2 * R;

}

int main()

{

double d = dist(36.12, -86.67, 33.94, -118.4);

/* Americans don't know kilometers */

printf("dist: %.1f km (%.1f mi.)\n", d, d / 1.609344);

return 0;

}

//Java

public class Haversine {

public static final double R = 6372.8; // In kilometers

public static double haversine(double lat1, double lon1, double lat2, double lon2) {

double dLat = Math.toRadians(lat2 - lat1);

double dLon = Math.toRadians(lon2 - lon1);

lat1 = Math.toRadians(lat1);

lat2 = Math.toRadians(lat2);

double a = Math.sin(dLat / 2) * Math.sin(dLat / 2) + Math.sin(dLon / 2) * Math.sin(dLon / 2) * Math.cos(lat1) * Math.cos(lat2);

double c = 2 * Math.asin(Math.sqrt(a));

return R * c;

}

public static void main(String[] args) {

System.out.println(haversine(36.12, -86.67, 33.94, -118.40));

}

}

If you haven't already, you should probably spend a minute looking at the formula on Wikipedia. It is pretty clear that the C and Java authors chose quite different approaches to implementing the details of the formula. If you removed the meta-info, many developers might not recognize that the functions perform the same calculation. However, I don't want to focus on the micro-details of the implementations. In both cases, the task is accomplished by a single function which converts individual parameters from degrees to radians. Both versions are pretty straight-forward implementations that I suspect a first year CS student could follow without much difficulty.

Let's take a look at the Haskell implementation.

**Code:**

--Haskell implementation

import Text.Printf

-- The haversine of an angle.

hsin t = let u = sin (t/2) in u*u

-- The distance between two points, given by latitude and longtitude, on a

-- circle. The points are specified in radians.

distRad radius (lat1, lng1) (lat2, lng2) =

let hlat = hsin (lat2 - lat1)

hlng = hsin (lng2 - lng1)

root = sqrt (hlat + cos lat1 * cos lat2 * hlng)

in 2 * radius * asin (min 1.0 root)

-- The distance between two points, given by latitude and longtitude, on a

-- circle. The points are specified in degrees.

distDeg radius p1 p2 = distRad radius (deg2rad p1) (deg2rad p2)

where deg2rad (t, u) = (d2r t, d2r u)

d2r t = t * pi / 180

-- The approximate distance, in kilometers, between two points on Earth. The

-- latitude and longtitude are assumed to be in degrees.

earthDist = distDeg 6372.8

main = do

let bna = (36.12, -86.67)

lax = (33.94, -118.40)

dst = earthDist bna lax :: Double

printf "The distance between BNA and LAX is about %0.f km.\n" dst

This author has implemented the task using more of a functional programming style. Even if you're unable to follow the actual details, you can clearly see the task broken into several functions: hsin, distRad, distDeg and deg2rad. Personally, I think this approach to implementing the task is much clearer. The bottom-up design approach has resulted in smaller, more orthogonal, functions that can easily be reused in other programming tasks.

Below, I've translated both the C and Haskell versions to Common Lisp. My hope is that seeing the different approaches side-by-side will help demonstrate the differences. Please note that I've made some minor changes that reflect 'Lisp style'.

**Code:**

;;A fairly straight-forward C to CL translation

;;instead of dx*dx, I squared using the expt function

(let ((R 6371)

(TO_RAD (/ pi 180)))

(defun dist (th1 ph1 th2 ph2)

(setf ph1 (* (- ph1 ph2) TO_RAD)

th1 (* th1 TO_RAD)

th2 (* th2 TO_RAD))

(let ((dx (- (* (cos ph1) (cos th1)) (cos th2)))

(dy (* (sin ph1) (cos th1)))

(dz (- (sin th1) (sin th2))))

(* 2 R (asin (/ (sqrt (+ (expt dx 2) (expt dy 2) (expt dz 2))) 2))))))

;;A functional programming version of the program based on the Haskell code

(let ((earth-radius 6372.8)

(rad-conv (/ pi 180)))

(defun deg->rad (x) (* x rad-conv))

(defun haversine (x) (expt (sin (/ x 2)) 2))

(defun dist-rad (lat1 lng1 lat2 lng2)

(let* ((hlat (haversine (- lat2 lat1)))

(hlng (haversine (- lng2 lng1)))

(root (sqrt (+ hlat (* (cos lat1) (cos lat2) hlng)))))

(* 2 earth-radius (asin root))))

(defun dist-deg (lat1 lng1 lat2 lng2)

(apply #'dist-rad (mapcar #'deg->rad (list lat1 lng1 lat2 lng2)))))

CL-USER> (format t "The distance between BNA and LAX is about ~$ km.~%" (dist-deg 36.12 -86.67 33.94 -118.40))

The distance between BNA and LAX is about 2887.26 km.

Personally, I think that the functional programming approach is much better. Now, I do believe that the C version, for example, could be implemented in this style, but I don't think it would be as easy to follow the code. Perhaps someone else might want to try implementing it in this manner. I might spend some time tomorrow writing functional programming implementations in C# and Java using higher-order functions. Just for kicks, I might also implement the task in R.

For anyone wondering about the dist-deg function, I convert the args from degrees to radians using the mapcar functions, which returns a list, then use the apply function to call the dist-rad function. This is pretty straight-forward programming in Lisp, but I suspect it might not be something that a first year CS student would follow (outside of a top school).