Building LINQ Queries at Runtime in F#

In an article about building LINQ queries at runtime in C# 3.0 [1], I described how you can build a LINQ query dynamically, for example by combining a set of conditions using the 'or' operator in the where clause. I mentioned that the way I implemented it is largely influenced by the F# language, which provides very natural way for manipulations with code like this. In this article I will first shortly introduce FLINQ sample, which is an F# library implementing LINQ support and than I will implement the same examples I presented in the earlier article in F#.

F# Comprehensions and Quotations

First, it is interesting to note that in F#, the language integrated query (LINQ) is not directly supported in the F# language, but instead is supported as a library. The code that you can use for writing queries is written using comprehensions which is a very common language construct in functional languages. In F# you can use it for example for manipulating with list of numbers:

let evenSquares = 
 [ for n in [0 .. 10] 
   when n%2 = 0
   -> n*n ]
// evenSquares : int list 
//   [0; 4; 16; 25; 36; 64; 100]

Here, we use the comprehension to build a list of integers. When building the list, we first take all numbers between 0 and 10, filter only even integers (in the when clause, which does filtering) and than return a square of every number (in the -> section, which performs projection). We can see that this is very similar to a syntax used in C#, which has from .. in keywords to define the source of data, where to define filtering and finally, select to define projection. In F# however, the syntax is not tightly tied with the LINQ and can be used for different purposes as well.

As you probably know, the second important feature that enables LINQ are expression trees. In C# this means that the program can get a representation of an anonymous function and manipulate with it - for example translate it to SQL. The C# compiler determines whether an anonymous function should be compiled as a delegate or as an expression tree by the type of a variable. If you use Func<..>, the function is compiled as a delegate and if you use Expression<Func<...>>, you will get an expression tree.

On the other side, in F# this can be done explicitly by marking any block of code using quotation symbols. A code marked using these symbols will be compiled as an F# quotation, which is a representation of F# code, similar as the C# expression tree. The reason why F# doesn't use the same representation as C# is that in F# you can quote more complicated code and not just a simple expression. The following code gives a few examples in both F# and C# (when possible):

// 'add' as a function & an expression in C#
Func<int,int,int>             addF = (a,b) => a + b
Expression<Func<int,int,int>> addE = (a,b) => a + b

// 'add' as a function & a quotation in F#
let addF =   fun a b -> a + b
let addE = « fun a b -> a + b »

// More complex quotation in F#
let addAndPrint = 
  « fun a b -> 
      let sum = a + b
      printf "Sum = %d" sum »

Note that if you don't want to use Unicode symbols («, ») in your code you can use <@@ and @@> that serve exactly for the same purpose. I'll use the Unicode symbols, because I believe that it looks more readable and once you define a few macros in Visual Studio it is easy to write them. As we can see, thanks to the fact that in F# it is explicitly specified what code is a quotation and what is an ordinary code, you don't have to write the types, because the F# type inference algorithm is able to deduce the types for us. The type of addF is inferred as int -> int -> int (function taking two integers and returning an integer) and the type of addE is Expr<int -> int -> int>, which is a quotation of the function. The second difference is that in F# you can quote more complex code as demonstrated by the addAndPrint example. This isn't important for supporting FLINQ, but it is very useful - for example it allows translating F# code to JavaScript which is implemented in my project F# WebToolkit [2].

FLINQ Introduction

Let's now look how the two F# features that I mentioned can be combined together to build an F# language support for querying database. The FLINQ is distributed as an F# example and you can find it in the samples/fsharp/FLinq directory (in the F# installation folder). The version available with F# (currently the latest release) is compatible with VS 2008 beta 1, but I built a version compatible with beta 2 as well, which you can get below. If you open the dlinqsamples.fs file, you can see a lot of F# samples for querying the Northwind database, so let me explain a few of them:

// Just select all customers
let sample1() =
  SQL « { for c in (§db.Customers) -> c } »
  |> dump 

// Select all customers from UK
let sample2() =
  SQL « { for c in (§db.Customers) 
          when c.Country = "UK"
          -> c } »
  |> dump 
// Join products & categories using nested 'for'    
let sample3() =
  SQL « { for p in (§db.Products) 
          for c in (§db.Categories)
          when c.CategoryID = p.CategoryID
          -> (c.CategoryName, p.ProductName) } »     
  |> dump

As we can see in all three examples, FLINQ wraps the whole comprehension (that specifies what we want to select from a database) in a quotation, so the F# code can be translated to SQL and executed. The translation and execution is done by the SQL function, which actually uses LINQ from the .NET 3.5 internally. In all three examples we use a dump function (which is implemented in the FLINQ sample) to print the results, which are returned as a sequence of tuple containing a name of category and product names - the type of the result is seq<string * string>. We could as well use a for loop or for example Seq.iter function which executes a given function for every element in the sequence.

So far I didn't explain the § symbol - it can be used in a quotation to embed a value into the tree. This means that when you're building a query that uses some value that is entered by the user (for example a name of the country for filtering), you can embed the value into a query using this symbol, without this symbol, the quotation will contain just a reference to a variable name, which isn't what we want in this situation. So, in all three samples we use the § symbol for embedding the value representing a database table in the quotation, so the translator can use it for querying the database.

For writing the FLINQ queries, we can use similar comprehensions as we used earlier. For example when selecting all customers living in UK in the second sample, we use a when to write a filter that selects only customers we want and we also use -> for projection - in the third example we want to select only a category name and a product name. In the third example we return an F# tuple (which is just a pair of two values) in the projection. This is a very compact way for writing the code - in contrast to C# 3.0 (where similar thing is achieved using anonymous types) in F# it didn't require any language change.

Dynamic Queries #1: Selecting Customers

Now we can finally look at everything you need to know from F# to understand how to build LINQ-like queries dynamically in F#. Let's start with a same example as in the previous article, we will build a query for selecting customers from the Northwind database and we will let the user to choose what property of the Customer type he wants to enter (a choice between CompanyName, Country and a ContactName). After choosing the property, we will ask for the value and run the query constructed using the given values. First, we will write a utility function for printing a sequence of customers (which is what the SQL function returns) and create a Northwind data context (similarly as in C# example):

/// Utility function to dump a sequence (IEnumerable) of customers
let dump (q:#seq<Customer>) = 
  for c in q do
      ("{0,-25}{2,10}, {1,-8}{3,-30}", 
       c.CompanyName, c.Country, c.City, c.ContactName)

/// Northwind data context and customers table
let db = new Northwind("Server=.; Database=Northwind; Integrated Security=SSPI")
let custTable = « §db.Customers »

At the last line of the sample, we created a value custTable which is an F# quotation containing just a value of the customers data table - we will need it later in the examples. Now, let's build a function for building the query. The function takes two arguments, the first arguments is a quotation of a function that selects a property of the Customer type and the second argument is a quotation of a value that we want to look for:

/// Function for building a query working with the customer table.
/// Selector is of type 'CustomerPropSelector'
let queryTemplate selector (value:Expr<string>) = 
  custTable |> 
    « { for c in _ do
          let s = (_ c) in
          when (s:string).IndexOf(_:string) <> -1
          -> c } » value selector

There is a one new interesting thing in this example, we used underscore at a few places in the quotation. The underscore in the quotation means that we want to build a quotation template, which is a quotation with placeholders that can be filled later. Technically, this means that we build a function that produces a quotation, once you give it all the required arguments to fill the holes. In this code, we use three underscores and we give it three arguments: value, selector and also custTable (which is written before the query using the pipe-lining operator to get a good type inference). We use a few type-annotations in the query, so the compiler knows what the types of the holes are, for example that the selector returns a string (which has the IndexOf method). The queryTemplate function can be used rather easily:

let q = SQL (queryTemplate « fun c -> c.CompanyName » « "ab" »)
q |> dump

As mentioned, both parameters are quotations (so that they can be used as an arguments for the quotation template that we wrote earlier), which means that we have to give it two quoted blocks of F# code. In our case, the first argument is a quoted function that returns a CompanyName property of a customer and the second argument is a quoted string literal.

In the next code snippet we finish the example and add the interactive part that allows selecting a property of the customer and entering the required value:

/// Dictionary for getting a 'selector' of a Customer property
/// with key of type string
let (dict:Map<string,CustomerPropSelector>) = 
    [ "CompanyName", « fun (c:Customer) -> c.CompanyName »;
      "Country",     « fun (c:Customer) -> c.Country »;
      "ContactName", « fun (c:Customer) -> c.ContactName »; ]
/// Demonstrates the use of 'queryTemplate' function
let main() =
  Console.Write("Filter - field name (CompanyName, ContactName, Country):\n> ");
  let prop = Console.ReadLine();
  Console.Write("Filter - value:\n> ");
  let value = Console.ReadLine();
  let q = queryTemplate dict.[prop] « §value »
  SQL q |> dump

Similarly as in the C# version, we use a key-value dictionary to build a dictionary that has a property name as a key and a quoted function for selecting a property of a customer as a value, though we use F# type Map. We also don't have to write the type, because we use type annotation to specify that the argument of the function is of type Customer and everything else is inferred automatically by the F# compiler. In the main function we just ask user for a property and a value then we find the selector for the given property in the dictionary and finally we build the query using queryTempalte, execute it and print the results.

Dynamic Queries #2: Combining Functions Using “OR” and “AND”

In the next example, we will write a more complex application that generates a LINQ query by combining several criteria using AND or OR logical operator. We will again use the Customer type from the Northwind database and we will allow selecting same properties as in the previous example. As mentioned in the previous article about the C# version, this allows the user to enter queries like (CompanyName = "Google") OR (Country = "Czech Republic") or (CompanyName = "Microsoft") AND (Country = "USA"). The way of combining the conditions is a bit limited, because you can use only a few properties and you can only test if it contains a string as a sub-string, an you also can't build a tree of logical operations, but you could easily extend the example to support all of these options as well.

As we use the same data context (db) and same dictionary with property name as a key and quoted function for selecting a property of the customer (dict), I won't repeat them in this example and let's look at our code for combining conditions:

// Elementary conditions
let falseCond = « fun (c:Customer) -> false »
let trueCond  = « fun (c:Customer) -> true  »

We first defined two elementary conditions, falseCond which returns false for every customer and trueConde which returns always true. The functions are quoted, so it will be possible to translate them to SQL. We didn't have to write the type explicitly, because the F# compiler infers them, but if you move a mouse pointer over these values, you'll see that the type is Expr<Customer -> bool>, which is indeed a type of quotation (Expr) of a function taking Customer and returning a value of bool. The next step is to define combinators for combining quoted functions:

// Condition combinators, declared as infix operators
let (||*) f g = « fun (c:Customer) -> (_ c) || (_ c) » f g
let (&&*) f g = « fun (c:Customer) -> (_ c) && (_ c) » f g

Because F# allows us to declare our own infix binary operators, we declare combinators as operators - you'll see later that this makes the code more readable. Both operators take two quoted functions (f and g) as the arguments and use them to build a quotation that represents a function that combines f and g using either || or && operator. The type of these operator is slightly more complicated, because it takes two conditions (of type mentioned above) and returns a condition - Expr<Customer->bool> -> Expr<Customer->bool> -> Expr<Customer->bool>, but as usually in F#, we didn't have to write this type, because the compiler inferred it automatically. The following example demonstrates how we can use the combinators:

/// Demonstrates the use of combinators
let simplecombine_demo() = 
  let isUk = « fun (c:Customer) -> c.Country = "UK" »
  let isSeattle = « fun (c:Customer) -> c.City = "Seattle" »

  // Build an expression using 'or' combinator
  let expr = isUk ||* isSeattle
  let q = custTable |> « { for c in _ when _ c -> c } » expr
  SQL q |> dump

In this sample we build a query that returns customers who live in UK or in Seattle. To build the query we first write two basic quoted functions for testing the conditions and then combine them using the ||* combinator. Finally, we use the created quotation as an argument to a quotation template to build a representation of full query, which is later executed using the SQL function.

Let's move to the final example where we'll combine conditions for all the properties of a customer. We'll do this using a Fold method of the dictionary which takes an initial value and allows us to combine the initial value with every key-value pair in the dictionary. This means that we will for example start with FALSE, than combine it with a first condition and get something like FALSE || (Country = "UK") and so on.

/// An advanced demo using 'fold' to combine more than 2 conditions
let combining_demo() = 
  Console.Write("Build || or && query (enter 'or' or 'and'):\n> ");
  let generateOr = Console.ReadLine().ToLower() = "or"  

  // Declare infix combinator, depending on an operator we use
  let (^^) = if generateOr then (||*) else (&&*)
  // Build the expression by 'folding' all items in dictionary
  let expr = 
      // Function to combine key, value & state
      (fun key propSelector e ->
        // Read the value from the user
        Console.Write("Enter value for '{0}':\n> ", key);
        let enteredVal = Console.ReadLine();
        // Build a condition testing whether entered value is a substring
        // using 'testTemplate' and combine it with current expression using '^^'
        let currentExpr = 
          « fun (c:Customer) -> ((_ c):string).IndexOf(_:string) <> -1 » 
            propSelector « §enteredVal »
        (currentExpr ^^ e)) 
      // Initial state
      (if generateOr then falseCond else trueCond)
  // Dump the results..  
  let q = custTable |> « { for c in _ when _ c -> c } » expr
  SQL q |> dump

In the example we first ask user to choose if he wants to combine conditions using || or using && and declare a new operator ^^ (available just locally in the function) that represents the selected combinator. Then we call the Fold function, in which we ask the user for a value for every property, build a quotation representing the current condition and combine the current condition with the condition that we generated so far (e). Also note that when combining conditions using &&, the initial condition is trueCond (returning always true) and for ||, the initial condition always returns false.


When you compare the code I wrote earlier in C# 3.0 and the code presented in this article, you can say that the difference is not that big. Actually, the most important differences in the code are that in F#, code is quoted explicitly (which allows the compiler to infer the type automatically) and that F# supports quotation templates with holes that can be filled later. There are however a differences from an architectural point of view. In C# 3.0 it is more difficult to encapsulate constructs like elementary conditions or combinators, because these are values of some very complicated type that you'd probably have to expose as static class members. On the other side, in F# the type doesn't have to be written explicitly (but you can still see it if you need it) and all the basic building blocks that we used in this code can be easily written as a members of a module that can be distributed for example as a DLL.

Downloads & References

Published: Saturday, 18 August 2007, 2:38 AM
Author: Tomas Petricek
Typos: Send me a pull request!
Tags: c#, meta-programming, f#