As already shown, monads and their incarnation in practical programming languages such as LINQ are simply a generalization of relational algebra by imagining the interface that relational algebra implements. The concepts and ideas behind LINQ should therefore be deeply familiar to both database people and programmers.

theory into Practice

Unlike Haskell, which has incorporated monads and monad comprehensions in a principled way, the C# type system is not expressive enough for the mathematical signatures of the monad operators. Instead, the translation of query comprehensions is defined in a purely pattern-based way. In a first pass, the compiler blindly desugars comprehensions, using a set of fixed rules, into regular C# method calls and then relies on standard type-based overload resolution to bind query operators to their actual implementations.

For example, the method Foo Select(Bar source, Func<Baz, Qux> selector), which does not involve any collection types, will be bound as the result of translating the comprehension

 

var foo = from baz in bar select qux

into the desugared expression

var foo = bar.Select(baz⇒qux)

 

This technique is used extensively in the example presented next.

Another difference between LINQ and its monadic basis is a much larger class of query operators including grouping and aggregation, which is more SQL-like. Interestingly, the inclusion of comprehensions in C#, which was inspired by monad and list comprehensions in Haskell, has recursively inspired Haskell to add support for grouping and aggregation to its comprehensions.

custom Query Providers
The Yahoo weather service (http://de-
veloper.yahoo.com/weather/) allows
weather forecast queries for a given lo-
cation, using either metric or imperial
units for the temperature. This simple
service is a good way to illustrate a non-
standard implementation of the LINQ
query operators that is completely spe-
cialized for this particular target and
that will allow only strongly typed que-
ries of the form

var request = Yahoo.WeatherService(). Where(forecast⇒ forecast.City == city). Where(forecast⇒forecast. Temperature.In.units); var response = await request;

 

or equivalently using query comprehensions

 

var request = from forecast in Yahoo.WeatherService() where forecast.City == city where forecastTemperature.In.units select forecast; var response = await request;

 

The implementation of the operators extracts the city and temperature unit from the query and uses them to create a REST call (http://weather.yahooa- pis.com/forecastrss?w=woeid&u=unit) to the Yahoo service as a result of using the await keyword to explicitly coerce the request into a response.

The technical trick in this style of custom LINQ provider is to project the capabilities of the target query language—in this case the Yahoo weather service that requires (a) a city and (b) a unit—into a type-level state machine that guides users in “fluent” style (and supported by IntelliSense) through the possible choices they can make (Figure 4).

At each transition in the state machine we collect the various parts of interest of the query—in this case, the particular city and the temperature unit. In principle, the city doesn’t really need to come first, but it might be more natural for the graph to allow either type of where clause to be specified first, but with the restriction that both where clauses are required. I leave the lifting of this restriction in the state machine as an exercise for the reader.

Note that none of the types Weath-
er, WeatherInCity, or WeatherIn-
CityInUnits implements any of the
standard collection interfaces. Instead
they represent the stages in the compu-
tation of a request that will be submit-
ted to the Yahoo Web service, for which
you do not need to define an explicit
container type. What also surprises
many people is that neither of the two
Where methods actually computes a
Boolean predicate. Even stranger is
that each of the three occurrences of
the range variable forecast in the
query has a different type.

WeatherInCity Where(Weather source, Func<CityPicker,string> city)

{ return new WeatherInCity{ City = city(new CityPicker()) };

}

 

The “predicate” in the Where method is a function that takes a value of type CityPicker, which has a single property that returns the phantom class City that exists only to facilitate IntelliSense and whose equality check immediately returns the string passed to the equality operator:

 

class CityPicker { City City; }
class City
{
static string operator == (City c,
string s) { return s; }
}

 

As a result of this, calling Yahoo. Weather().Where(forecast⇒ forecast==“Seattle”) really is just a convoluted way of creating a new WeatherInCity{ City = “Seattle” } instance using a Where method that does not take a Boolean predicate and an equality operator that returns a string.

You can use the same trickery in WeatherInCityInUnits

Where(Func<UnitPicker,Unit> predicate), so that calling Where(forecast⇒forecast.Tem- perature.In.Celsius) on the result of the previous filter creates an instance of new WeatherInCityInUnits{ City=“Seattle”, Unit = Unit. Celsius }. The techniques used here are not only useful for defining custom implementations of the LINQ operators, but also can be leveraged for building fluent interfaces in general.