LINQ and GeoCode, Part 2

I feel it's appropriate to start this post off this way:

Actually, you CAN translate [the Haversine Equation into a] client side function; as long as you can describe it as an Expression... The problem isn't how complicated (although I note it could be ugly in this case), it's the fact that you weren't using Expressions... I'm still a sucker for any technical challenge. I hope you enjoy crow -- Michael

The background here has to do with my original post on LINQ and Geocoding. I translated a C# method into a Lambda for fun in order to see how far I could push LinqToSql - and indeed I broke it. Michael Giagnocavo was quick to point out that it was possible to do it (albeit perhaps ugly - his words) - you just needed to create it as an Expression first. This is a clever approach, since when you right a query this way:

    var result = from hotels in db.Hotels
                 where hotels.ID>100
                 select hotels;

LinqToSql creates an Expression for you based on your shorthand. When it sees a call to another function (even if it's a Lambda like mine was), it fails with a nasty "Can't translate to SQL" error. I had figured that this was as far as I could push LinqToSql - turns out I was wrong! One Order of Crow, Please. Medium Rare... So let's review the Haversine Lambda. It's a bit complicated but we'll need it to understand what's going on:

        const Double EARTH_RADIUS_IN_MILES = 3956.0;
        Func<double, double, double, double, double> CalcDistance = (lat1, lon1, lat2, lon2) =>
        EARTH_RADIUS_IN_MILES * 2 *
        (
            Math.Asin(
                Math.Min(1,
                    Math.Sqrt(
                        (
                            Math.Pow(Math.Sin((DiffRadian(lat1, lat2)) / 2.0), 2.0) +
                            Math.Cos(ToRadian(lat1)) * Math.Cos(ToRadian(lat2)) *
                            Math.Pow(Math.Sin((DiffRadian(lon1, lon2)) / 2.0), 2.0)
                        )
                   )
               )
           )
         )
        ;

This function basically calculates the distance (in miles) between two points on a sphere (the Earth), along a Great Circle (the longest way around a sphere between the two points). The answer, according to Michael, was to essentially build the expression for LinqToSql and then pass it in. At first I was intrigued - thinking that this was a nice way around the problem. But the more I looked into it, the more I didn't believe it would work because we still have this gnarly Lambda that needs to be translated to SQL - why would it matter if I set up the Expression, or if LinqToSql did it for me? It's still passed in as a Lambda isn't it? Doesn't it still need to be translated to SQL? The secret, it turns out (as Michael had tried to explain many times), is declaring the Lambda as an Expression<T> where T is your Lambda delegate (aka "Func< >"):

static Expression<Func<double, double, double, double, double>> CalcDistance = (lat1, lon1, lat2, lon2)...

When you do this, the compiler doesn't rework the Lambda into IL, which it would normally do when declaring a Func< >:

[CompilerGenerated]
private static double <.ctor>b__0(double lat1, double lon1, double lat2, double lon2)
{
    return (7912 * Math.Asin(Math.Min(1, Math.Sqrt(Math.Pow(Math.Sin(DiffRadian(lat1, lat2) / 2), 2)

     + ((Math.Cos(ToRadian(lat1)) *

       Math.Cos(ToRadian(lat2))) *

       Math.Pow(Math.Sin(DiffRadian(lon1, lon2) / 2), 2))))));
}

Instead, it builds an ExpressionTree out of it:

Expression<Func<Hotel, bool>> pred = Expression.Lambda<Func<Hotel, bool>>(Expression.LessThan

   (Expression.Invoke(      
      dist, new Expression[] { ourLat, ourLong, hotelLat, hotelLon }),    
     Expression.Constant(100)),    new ParameterExpression[] { hotelParam });

Well get down and call me Charlotte! [looks for the waiter... is my crow ready yet?] So now we have a tree of parsable expressions, not a nasty Lambda that will make our SQL parser puke, and we can build the Expression for LINQ nicely. I'll have to admit this is ugly stuff (and it's about 1000 times slower at 1 full second than SQL Server sproc/function, which is immediate) and I wouldn't do it this way (neither would Michael, but his point was that you could do it if you needed). So without further ado, here's the code (redone by Michael, comments by me):

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using E = System.Linq.Expressions.Expression;
using System.Linq.Expressions;
namespace ComplexLinq {
    class Program {

        //earth's radius, in miles
        const double R = 6371;
        //radian converter
        const double RAD = Math.PI / 180;
        //our Haversine Lambda
        static Expression<Func<double, double, double, double, double>> dist = (lat1, lon1, lat2, lon2) =>
        R * 2 *
        (
            Math.Asin(
                Math.Min(1,
                    Math.Sqrt(
                        (
                            Math.Pow(Math.Sin(((lat1 * RAD - lat2 * RAD)) / 2.0), 2.0) +
                            Math.Cos(lat1 * RAD) * Math.Cos(lat2 * RAD) *
                            Math.Pow(Math.Sin(((lon1 * RAD - lon2 * RAD)) / 2.0), 2.0)
                        )
                   )
               )
           )
        );

        static void Main(string[] args) {
            //LinqToSql Context
            Geo.DataContext db = new Geo.DataContext();

            //Somewhere in San Diego
            double myLat=32.76105;
            double myLong = -116.9981; 

            //set up the LINQ Expression - in this case tell it were working with
            //a Hotel
            var hotelParam = E.Parameter(typeof(Geo.Data.Hotel), "h"); 

            //Tell it there's a thing called the "HotelID" since we're going to lose
            //some introspection by "circumnavigating" the SQL parser
            var hotelID = E.Property(hotelParam, "HotelID");

            //tell it about the field called "Longitude"
            var hotelLon = E.Property(hotelParam, "Longitude");

            //tell it about the field called "Latitude"
            var hotelLat = E.Property(hotelParam, "Latitude"); 

            //add a ConstantExpression for our source Longitude
            var ourLong = E.Constant(myLong);

            //add a ConstantExpression for our source Latitude
            var ourLat = E.Constant(myLat); 

            //This is an "InvokationExpression" - it means "fire when called"
            var call = E.Invoke(dist, ourLat, ourLong, hotelLat, hotelLon); 

            //add in a BinaryExpression for LessThan 
            var gComp = E.LessThan(call, E.Constant(100d));

            //build the final lambda
            var pred = E.Lambda<Func<Geo.Data.Hotel, bool>>(gComp, hotelParam);

            //run it
            var result = db.Hotels.Where(pred);

            foreach (var h in result)
            {
                Console.WriteLine(h.Name);
            }
            Console.ReadLine();
        }

} Epilogue As a final note - it took Michael and I a bit to get to this point :). I eat my hat on occasion, but usually stand up when I think I'm right. Usually the only thing that will convince me is to see some working code, not theory. In our case, we sent some emails back and forth and I understand his reticence - we both have jobs and work to do. The theory was flying all over the place until finally, this morning, he sent me the code and I promptly shut my mouth and graciously accepted defeat (I still have resurrection sickness but I have some beer-crafting to do until it wears off). My point here is that theory is fine and wonderful, so are suppositions and "best practices". But if you take the time to "call someone out" - namely ME, please do send the code up front :). It will save some long emails...