A Great Blog Series on Algorithmic Programming in F#
I've just discovered Julien's great blog series on algorithmic programming in F#, a very useful resource. And if that doesn't whet your appetite, he also has a series on food :-) Here are some of his recent posts: Technical analysis indicators in F#   This is the first part of a series on technical analysis indicators in F#. We will define the basic object holding the data series which will be used to compute the indicators. We will also describe some functions to check the integrity of the said data (and which will be useful when defining the indicators). An immutable range library in F# An immutable range library in F# where a range is only defined by a minimum and a maximum value (hence, there is no step). An immutable queue in F# An immutable queue library in F#. The queue is divided into two lists : one for dequeueing, and one for enqueueing. All operations are based on the List module. A bitset library in F# ReadWrite Requests for groups of files In this post, we shall use read/write requests from a group of files considered as a single entity. We will also look at verifying the data. In our model, the group of files is defined by the files, and pieces. A piece is a chunk of data with a standardized size so that read/write requests are consistent. Of course, the last piece of the files stream could see its size differ from others since if the cumulative size of the files is not a multiple of the piece length.  Implementing Two-way TCP Traffic Control in F# This post describes how to implement two-way (TCP for instance) traffic control in F# by modifying slightly a Trolltech article available at http://doc.trolltech.com/qq/qq17-ratecontrol.html.   Crème pâtissière – Pierre Hermé, “Larousse des desserts”   Pâte à choux   Le chocolat    Pâte sucrée – Pierre Hermé, “Larousse des desserts”   And the list goes on! F# brush for Gorbatchev’s SyntaxHighlighter Dual quicksort in F# F# brush for Geshi Batch image resizer Tries and Anagrams with F#    
Sun, 08 Nov 2009 18:19:00 GMT

Equality and Comparison Constraints in F#
F# 1.9.7 introduces two new constraints to the F# language to help uncover issues in your code when using equality and comparison operators. In this blog entry we'll take a look at these constraints in a bit more detail. The topics in this blog post are   Tuples, Lists and other Structural Types The Basic Equality and Comparison Operations in F# What do the equality and comparison constraints mean? Defining New Structural Types Customizing Equality and Comparison Safer Code: Suppressing Equality and Comparison on a Type Safer Code: Safer Sets and Maps Safer Code: Declaring Conditions for Equality over Container Types Getting IEqualityComparer<’T> and IComparer<’T> Implementations which use F# Generic Equality Using unchecked equality and comparison Design Alternatives. Could interface constraints suffice? User defined constraints? Summary   You can also find the details in the draft F# Language Specification, where similar material is covered.  First, as usual, some background.   Tuples, Lists and other Structural Types   Functional programming in F# frequently involves the use of structural equality, hashing and comparison. For example:   (1,1+1) = (1,2) will return true, because tuple types support "structural" equality. Likewise these two function calls return identical values:   hash (1,1+1) hash (1,2)   Likewise an ordering on parts of a tuple induces an ordering on tuples themselves, so all the following evaluate to true:   (1,2) < (1,3) (1,2) < (2,3) (1,2) < (2,1) (1,2) > (1,0)   The same applies to lists, options, arrays and user-defined record, union and struct types whose constituent field types permit structural equality, hashing and comparison.    Equality and comparison are a surprisingly important part of the experience of “programming with functional data” – it is difficult to imagine F# being F# if you can’t compare tuples for equality, or lists for equality, and likewise for other user-defined structural types. In each case, the behaviour of these operations depends on the equality properties of the constituent components.   This in turn means that the “idea” of equality, hashing and comparison (including structural versions of these) is built in quite deeply into the F# language and core library – for example, several pages of the F# specification are devoted to defining what happens when you use equality with user-defined structural types.      The Basic Equality and Comparison Operations in F#   Let’s take a look at the signatures of the equality, comparison and hashing operations in the F# library:   (=)  : 'T -> 'T -> bool when 'T : equality (<>) : 'T -> 'T -> bool when 'T : equality hash : 'T -> int when 'T : equality   (<)  : 'T -> 'T -> bool when 'T : comparison (<=) : 'T -> 'T -> bool when 'T : comparison (>)  : 'T -> 'T -> bool when 'T : comparison (>=) : 'T -> 'T -> bool when 'T : comparison compare : 'T -> 'T -> int when 'T : comparison min     : 'T -> 'T -> 'T when 'T : comparison max     : 'T -> 'T -> 'T when 'T : comparison   First note that these are generic operations – they can be used on objects of many different types. This can be seen by the use of 'T in the signatures of these operations. These operations take one or two parameters of the same type. For example, you can apply the “=” operator to two Form objects, or two System.DateTime objects, or two System.Type objects, and something reasonable will happen.  Some other important derived generic types such as the immutable (persistent) Set<_> and Map<_,_> types in the F# library also use generic comparison on their key type:   type Set<'T when 'T : comparison> = ... type Map<'Key, 'Value when 'Key : comparison> = ...     In common with many other basic generic operators in the F# library, the above operations are constrained, in this case by the 'T : equality and 'T : comparison constraints. The purpose of constraints on type parameters is to make sure the operations are only used on a reasonable set of types. For example, consider using equality and comparison on a System.Windows.Forms.Form object. Equality is permitted, because the default for nearly all .NET object types is reference equality:   let form1 = new System.Windows.Forms.Form() let form2 = new System.Windows.Forms.Form() form1 = form1    // true form1 = form2    // false   However comparison is not permitted:   let form1 = new System.Windows.Forms.Form() let form2 = new System.Windows.Forms.Form() form1 <= form2     // Error: The type 'System.Windows.Forms.Form' does not support the 'comparison' constraint.     // For example, it does not support the 'System.IComparable' interface   That’s good! There is no natural ordering for these object - you could define one, on a derived type, by implementing IComparable, but there is not natural ordering provided by the .NET libraries.   Now, unlike other operations in the F# core library, equality and comparison are conditional on the structure of types. For example, you can only use the above equality and comparison operators on a tuple if the constituent parts of the tuple also support equality and comparison. For example, using equality on a tuple of forms is permitted:   let form1 = new System.Windows.Forms.Form() let form2 = new System.Windows.Forms.Form() (form1, form2) = (form1, form2) // true (form1, form2) = (form2, form1) // false   But attempting to order a tuple involving forms is not:   (form1, "Data for Form1") <= (form2, " Data for Form2")     // Error: The type 'System.Windows.Forms.Form' does not support the 'comparison' constraint.   Again, that’s good – this ordering would be a bug in your code.   Many types in the .NET libraries come with custom equality and comparison implementations. For example, System.DateTime has custom implementations of both equality and comparison. F# also allows you to define custom comparison and equality for new type definitions. We’ll be looking at how to customize equality and comparison implementations later in this blog post.     What do the equality and comparison constraints mean?   Let’s summarize where we are so far:   -          For some types, equality is structural. For example, lists, options, tuples and user-defined structural types. -          For some types, equality is reference based. These types do not tend to support comparison. For example, System.Windows.Forms.Form. -          For some types, equality is customized, for example System.DateTime. -          For some types, there is no sensible notion of equality and/or comparison. You can think of these types as being labelled no equality and no comparison. This case is only important for finding bugs in your code earlier rather than later.   The combination of these points underlies the decision to include equality and comparison constraints as first-class new, primary constraints in the F# language.  Later on in this blog post we consider other options in this design space. Now, let’s take a closer look at when equality and comparison constraints are satisfied in F#.    The essence of the rules is very simple:   The constraint type : equality holds if: -          the type definition for type doesn't have the NoEquality attribute, -          any  “equality dependencies” of the type also satisfy ty : equality The constraint type : comparison holds if: -          if the type is a named type, then the type definition doesn't have the NoComparison attribute; and -          the type definition implements System.IComparable; and -          any “comparison dependencies” of the type also satisfy tyi : comparison These rules mean that an equality constraint is a relatively weak constraint, since nearly all CLI types satisfy this constraint.  Reference equality is pervasive in other CLI languages such as C# and this shows through in CLI libraries. Note that the an equality constraint also implies the ability to use the F# hash function on an object.   A comparison constraint is a stronger constraint, since it usually implies that a type must implement System.IComparable.   We’ve discussed the notion of “dependencies” above, e.g. (int * string) is comparable because both int and string are comparable. Here, int and string are dependencies of the tuple type. We’ll look at declaring new dependencies for a type further below.     Defining New Structural Types   Structural type definitions are easy in F#:   type MyBox<'T> = MyBox of 'T   In this case, the type is given structural equality and comparison implementations, and F# infers that there is an equality and comparison dependency on ‘T. All done!   Sometimes you may want to assert that a structural type really MUST support structural equality, and you want an error at the definition of the type if it does not. You do this by adding the StructuralEquality or StructuralComparison attribute to the type   [<StructuralEquality;StructuralComparison>] type MyIntBox = MyIntBox of int   This simply adds extra checking.  In the example below, the code gives an error at compile time, because the type can’t logically support automatic structural comparison, because one of the element types does not support structural comparison:   [<StructuralEquality;StructuralComparison>] type MyData = MyBox of int * string * string * System.Windows.Forms.Form   More commonly, you may notice that F# function types do not support equality:   [<StructuralEquality;StructuralComparison>] type MyData = MyBox of int * string * string * (int -> int)   Again this will give an error, because function values are considered to be “no equality”   You can also declare that a structural type should use reference equality.   [<ReferenceEquality>] type MyFormWrapper = MyFormWrapper of System.Windows.Forms.Form * (int -> int)   In summary, the following attributes control the comparison and equality semantics of types in the cases outlined earlier in this blog post   -          StructuralEquality,StructuralComparison             – indicates a structural type MUST support equality and comaprison -          ReferenceEquality                                                          – indicates a structural type supports only reference equality -          NoComparison, NoEquality                                        – indicates a type doesn’t support equality or comparison at all -          CustomEquality, CustomComparison                     – indicates a structural type supports custom equality and comparison   Note there is no such thing as “reference comparison” (the object pointers used by .NET move around, so the ordering would change). You might implement that by using a unique tag and custom comparison.   Customizing Equality and Comparison   For some types it is often necessary to define your own comparison, equality and hashing semantics. For example, values of a type may carry a unique integer tag which can be used for this purpose.   In this case our recommendation is to take full control of your destiny and define custom comparison and equality operations on your type. For example, here is how you might compare based on a “stamp” integer value:   /// A type abbreviation indicating we’re using integers for unique stamps on objects type stamp = int   /// A type containing a function that can’t be compared for equality    [<CustomEquality; CustomComparison>] type MyThing =     { Stamp: stamp;       Behaviour: (int -> int) }        override x.Equals(yobj) =         match yobj with         | :? MyThing as y -> (x.Stamp = y.Stamp)         | _ -> false       override x.GetHashCode() = hash x.Stamp     interface System.IComparable with       member x.CompareTo yobj =           match yobj with           | :? MyThing as y -> compare x.Stamp y.Stamp           | _ -> invalidArg "yobj" "cannot compare values of different types"   You might also find these helpful to add to your library of F# helpers:       let equalsOn f x (yobj:obj) =         match yobj with         | :? 'T as y -> (f x = f y)         | _ -> false       let hashOn f x =  hash (f x)       let compareOn f x (yobj: obj) =         match yobj with         | :? 'T as y -> compare (f x) (f y)         | _ -> invalidArg "yobj" "cannot compare values of different types"   This can then make your custom implementations more uniform. For example, here is a custom implementation for a union type:   type stamp = int   [<CustomEquality; CustomComparison>] type MyUnionType =     | MyUnionType of stamp * (int -> int)        static member Stamp (MyUnionType (s,_)) = s       override x.Equals y = equalsOn MyUnionType.Stamp x y     override x.GetHashCode() = hashOn MyUnionType.Stamp x     interface System.IComparable with       member x.CompareTo y = compareOn MyUnionType.Stamp x y   You can also define custom equality and comparison implementations on other types.   Note: A bug in an error message in the 1.9.7 release of F# says “A type with CustomEquality must override Equals or implement IEquatable or IStructuralEquatable”. This is not the case: a type with CustomEquality must override Equals.   Safer Code: Suppressing Equality and Comparison on a Type   You can suppress equality on an F# defined type by using [<NoEquality>] attribute on the definition of the type. This simply means that the type will not be considered to satisfy the equality constraint. Likewise, you can suppress comparison on an F# defined type by using [<NoComparison>] attribute on the definition of the type. This simply means that the type will not be considered to satisfy the comparison constraint.   [<NoEquality; NoComparison>] type MyProjections =     | MyProjections of (int * string) * (string -> int)    Adding these attributes to your library types makes client code safer, as it is less likely to inadvertently rely on equality and comparison over types where these operations make no sense.     Safer Code: Safer Sets and Maps   All previous versions of F# did not check equality and comparison constraints. We always planned to address this, but the details were only finalized in 1.9.7.   One main motivation for checking these constraints is to make sure the F# Set and Map types, and other future F# immutable collections, are not misused. For example, consider the following:   let x1 = set [ (fun x -> x + 1); id ; (fun x -> x + 2) ] // static error   let x2 = set [ obj(); obj(); obj() ] // static error   let x3 = set [ typeof<int>; typeof<string> ] // static error     In early versions of F# these gave runtime errors. As another example, consider trying to compare functions for equality:   id = id // static error   This returned “false” in early versions of F#, because two different closures were allocated for “id” on each side of the equation – this is valid, according to the F# specification, which says that the results of equality comparison on function values was undefined. This now gives a static error. These cases alone indicate the importance of addressing this issue.   Safer Code: Declaring Conditions for Equality over Container Types   Programmers love defining new generic container types. This is done less often in .NET and F# programming than in other languages, but it's still important!    Equality and comparison play a role here. For example, it is common to have collections where some of the values can be indexed using hashing, or compared for equality when searching, or compared using an ordering. For example, seeing a constraint on this signature on a library type would come as no surprise:   type Graph<'Node when 'Node : equality>() = ...   Indeed the presence of the constraint is somewhat reassuring here, as the requirement on node types is made clearer.   Now, sometimes it is also desirable to be able to compare “entire containers”, e.g. compare one set with another, or one map with another, or one graph with another. This is a lot like comparing tuples or lists. At a first approximation this is done by customizing equality and/or comparison for the container.   type Graph<'Node when 'Node : equality>() =     override x.Equals(yobj) = ...     override x.GetHashCode() = ...   In this case, the node type already supports equality/hashing (for indexing inside the collection ) so the implementation of “Equals” is simple enough, following  the pattern laid out in the section “Customizing Equality and Comparison” above.   Sometimes, however, it is necessary to declare that equality (and comparison) over generic container values themselves is “dependent” on the type parameters of the container type. Just like F# list and tuple types. This is done by adding the EqualityConditionalOn and ComparisonConditionalOn attributes to the type parameters of a generic type.    As our example, we will use that beguilingly simple beast – a single-cell container that also supports equality and comparison over the container.  You can define this easily in F# as follows:   type MyBox<'T> = MyBox of 'T   In this case, this is a structural type definition, and F# infers that there is an equality and comparison dependency on ‘T. All done! You will be able to use MyBox<_> with values of any type, and you will only be able to do equality and comparison on MyBox values if the element type also supports equality and comparison – perfect!   However, what if MyBox is, for some reason, implemented as a class type, or with customized comparison and equality logic for the type? In this case you need to be more explicit, starting with the EqualityConditionalOn and ComparisonConditionalOn attributes on the type parameter:       type MyBox<[<EqualityConditionalOn; ComparisonConditionalOn >]'T> = ...   With these attributes, MyBox<A> will only satisfy the equality and comparison constraints if A satisfies these constraints. You will still be able to use MyBox<_> with any type.   Now, let’s look at the custom implementations for Equals, GetHashCode and System.IComparable. Here’s a full example of a container type that also supports conditional equality and comparison over the containers themselves:   type MyBox<[<EqualityConditionalOn; ComparisonConditionalOn >]'T>(value : 'T) =        member x.Value = value       override x.Equals(yobj) =         match yobj with         | :? MyBox<'T> as y -> Unchecked.equals x.Value y.Value         | _ -> false       override x.GetHashCode() = Unchecked.hash x.Value       interface System.IComparable with       member x.CompareTo yobj =           match yobj with           | :? MyBox<'T> as y -> Unchecked.compare x.Value y.Value           | _ -> invalidArg "yobj" "cannot compare values of different types"     Note that the implementation of the interfaces and overrides uses “unchecked equality and comparison”, something we’ll get to below. The need for unchecked equality here ultimately stems from the dual facts that (a)    F# asks you to specify custom equality at the level of .NET overrides and interface implementations; and (b)   .NET does not support conditional interface and override implementations (see discussion below).   There are great advantages to (a) – it simplifies F# and means you don’t have to look up the F# manual to see what behaviour your objects will have when handed over to C#.   Fortunately, the use of unchecked equality is isolated and localized, and actually surprisingly hard to get wrong. In any case, you should unit test to check that your type really does support equality and comparison correctly.     Getting IEqualityComparer<’T> and IComparer<’T> Implementations which use F# Generic Equality   When using .NET libraries, it is very common to need an implementation of IEqualityComparer<'T> or IComparer<'T>.  Two F# core library functions are very useful for getting objects which implement these interfaces in a way that is consistent with F# equality and comparison:   HashIdentity.Structural<'T>       : IEqualityComparer<'T> when 'T : equality ComparisonIdentity.Structural<'T> : IComparer<'T>         when 'T : comparable   These are most useful when instantiating .NET hash table and comparison operations. For example:   open System.Collections.Generic   let hashTable = new Dictionary<string,int>(HashIdentity.Structural<string>) let hashSet = new HashSet<string>(HashIdentity.Structural<string>)   You can also omit some of the type annotations here and let inference do its work:   open System.Collections.Generic   let hashTable = Dictionary(HashIdentity.Structural) let hashSet = HashSet(HashIdentity.Structural) hashTable.Add("three", 3) hashSet.Add("three")   The great advantage of giving an explicit HashIdentity.* or ComparisonIdentity.* argument is that your code is more rigidly checked: the F# compiler checks if your inferred key type actually admits F# equality. For example, F# function types are considered to be “no equality” (i.e. hashing on an F# function values is not a good idea):   open System.Collections.Generic   let concatOne (s:string) = s + "1" let hashTable = new Dictionary<_,_>(HashIdentity.Structural) hashTable.Add(concatOne, 10) // error: the type “string -> string” doesn’t support equality   Here the intended code was something like this:   hashTable.Add(concatOne "ten", 10) // ok: the type “string” supports equality     Using unchecked equality and comparison   As we saw above, it can occasionally it can be necessary to resort to “unchecked” equality and comparison on values. This doesn’t do any static checking, just like in earlier versions of F#.   Unchecked.equals: 'T -> 'T -> bool Unchecked.hash: 'T -> int Unchecked.compare: 'T -> 'T -> int   These are unconstrained operations, and work just the same way as the constrained operations – for example, they will also by optimized by the F# compiler if used on basic integer types. For Unchecked.equals and Unchecked.hash, they are semantically similar to converting to the type “obj” and doing equality over that static type.     Design Alternatives. Could interface constraints suffice? What about type classes?   Readers familiar with C# may ask “Does F# really need a new kind of constraint here? How about using an interface constraint?”. For example, could we use this signature for comparison?   compare : 'T -> 'T -> bool when 'T : System.IComparable   Or this one?   compare : 'T -> 'T -> bool when 'T : System.IComparable<'T>   The problem with both is that they are too permissive: for example, if F# lists implement IComparable or IComparable<'T>, then the above signatures would let you use comparison on any two F# lists, regardless of whether the element type supports comparison.   The underlying (and well known) problem is that interface implementation in .NET is unconditional – a type either supports an interface or it doesn’t.  This is a fundamental limitation of .NET generics. In F#, it is part of our design methodology to add additional, erased constraints to work around such limitations.   Equally it is also not possible to use a parameter constraint on the F# list type. For example, consider this option:   type FSharpList<'T when 'T : IComparable<'T>>() = ... // this leads the type to be over-constrained.   With this signature, lists become much less useful: you couldn’t create lists of objects that don’t support comparison!   As a result, .NET interface constraints are not sufficient to allow us to tackle equality and comparison constraints in F#. This underlies the decision to include equality and comparison constraints as new, erased constraints in the F# language.   Readers familiar with Haskell and other functional languages will be well informed of all the issues relating to equality and comparison, since the issues are fundamental to equality and comparison in any typed language, but particularly functional languages. The mechanisms used to address these points in F# are reminiscent of a weak form of type classes, particularly in the way equality and comparison are dependent on the structure of types, and the way these dependencies can be declared for any type. Haskell also lets users define their own constraints, in a very rich (and sometimes fairly complicated!) way.   Now, equality and comparison are the only operations in the F# Core Library that are statically conditional on the structure of types. This raises the question as to why F# doesn’t allow user-defined constraints (beyond interface constraints), and why other constraints can’t be declared conditional. After all, it is well known that it can be useful to make other operations conditional on structure too, e.g. printing and serialization.   The answer is two-fold. Firstly, in future versions of F# we may consider extending the mechanisms used to implement equality and comparison constraints to include user-defined constraints.   Secondly, however, for many common used constraints (such as formatting and serializability), there are other ways to achieve the same thing in F# that are not particularly amenable to using constraints. Also, in each case there are serious interactions with .NET libraries and existing design practice to consider. Finally, some conditional constraints would require a “dictionary passing” implementation. This brings added difficulties. Equality and comparison constraints are not dictionary passing – they are ultimately implemented via interfaces and overrides. As a result, for F# in Visual Studio 2010, we concentrated on resolving the interactions with .NET for the critical cases of equality and comparison, rather than adding a completely general mechanism.   Summary   F# equality and comparison constraints tighten up a key part of the F# language, they make user code safer and simpler.   On the whole, F# code is surprisingly unaffected by these constraints – in our test trees we have a very large collection of sample F# code, and only a very small amount of that code needed to have equality or comparison constraints added. These constraints catch problems, but do not intrude. For example, we use structural and equality constraints throughout the F# compiler codebase and, in a couple of cases, it helped to identify lingering potential bugs.   In 1.9.7 we also simplified some of the attributes used to control equality and comparison, notably removing the “true” and “false” arguments from StructuralEquality etc., and adding CustomEquality to help users declare exactly what is intended. If you need additional help to adjust your code for these changes, please let us know.   We wish you many happy days of safer and more productive coding!        
Sun, 08 Nov 2009 17:42:00 GMT

F# 1.9.7 Language Specification Now Available
The F# 1.9.7 Language Specification is now available, in PDF and HTML, matching the recent release of F# in Visual Studio 2010 Beta2, with matching CTP udpate for Mono and Visual Studio 2008. The latest language specification can also always be found via www.fsharp.net Many thanks to all those who sent so much helpful feedback on the specification during Beta1. And for those using 1.9.7 already, thanks for your patience in the last couple of weeks - it took us a little longer to get this out the door than we had planned, since a development deadline for Visual Studio 2010 intervened. We plan on making a second update to the 1.9.7 spec to polish some areas of the text in the next few weeks. thanks, don    
Wed, 04 Nov 2009 17:46:00 GMT

Language Integrated Query Support in the F# Power Pack
In this post I thought I would give some simple, up-to-date examples of writing queries using the F# Power Pack and executing them via LINQ. The techniques described here also apply to querying any obejcts that support the IQueryable interface.   My aim here is not to give a complete guide to "doing everything you can do in SQL" or "everything you can do with LINQ and F#". Instead, I just want to bring some of the material you might find on the web up-to-date for the Beta1/Beta2 releases of the F# Power Pack. Also, note that the IQueryable support described here is not in F#, but in the F# Power Pack, which includes other components such as FsLex and FsYacc. The binaries and code for the F# Power Pack is included with the F# CTP release and can be used with Visual Studio 2010, and we’ll be looking to do regular CodePlex releases of the Power Pack as VS2010 settles down.   For those unfamiliar with Linq and IQueryable, here’s a recap: .NET defines an interface IQueryable for roots of queries made up of select/where/join/group/sort and a few other SQL-like operations. C# and VB have a syntax to write queries, and desugar this syntax to expressions and expression trees. Engines such as LINQ-to-SQL then execute expression trees in various interesting ways, for example as SQL. There are many other interesting and powerful engines that implement IQueryable support too.   In this post we’ll be looking at how you can leverage IQueryables by using the F# Power Pack. You can walk through everything here step by step in F# Interactive and the script is attached. First, however, some basics, so let’s define some in-memory data:   type Customer =     { Name:string;       UniqueID: int;       Weighting:float;       Preferences: int list } let c1 = { Name="Don";    UniqueID=6; Weighting=6.2; Preferences=[1;2;4;8] } let c2 = { Name="Peter";  UniqueID=7; Weighting=4.2; Preferences=[10;20;30;40] } let c3 = { Name="Freddy"; UniqueID=8; Weighting=9.2; Preferences=[11;12;14] } let c4 = { Name="Freddi"; UniqueID=9; Weighting=1.0; Preferences=[21;22;29;42] }   let data = [c1;c2;c3;c4]   Simple In Memory Queries   In F# we express many queries using simple F# sequence expressions. Here is a very simple F# in-memory query:   let q0 =     [ for i in data do           if i.Name.Length = 6 then               yield (i.Name,i.UniqueID) ]   As expected, this generates a list of length 2, containing entries for Freddy and Freddi. You can use the same inner syntax for to generate an on-demand sequence (an IEnumerable<T>):   let q1 =     seq { for i in data do              if i.Name.Length = 6 then                  yield (i.Name,i.UniqueID) }   When executed, this will produce an IEnumerable. We can compute the length of this sequence as follows:   q1 |> Seq.length   or we might convert it to a list:   q1 |> Seq.toList   One thing to note is that F# sequence expression syntax looks and feels a lot like regular F# code except enclosed with [ ... ] or seq { ... } and with a few yiields added (it is much like a C# iterator, except in expression form).  Sequence expressions are useful for many things, but they have their limits. As a result, it is quite common to follow a sequence expression by a pipeline of combinators, e.g.       seq { for i in data do              for j in data do                 if i.Name.Length = j.Name.Length && i.Name <> j.Name then                    yield (i.Name,j.Name) }     |> Seq.sortBy (fun (name1, name2) -> name1)     |> Seq.toList   Here we did the sorting and conversion to a list just after the { ... } syntax.  The whole expression above is the “query”, but only one part of it uses the sequence expression syntax. This is quite common in F#. Also, there are other kinds of operators that can be considered queries, e.g. the functions Seq.pick, Seq.tryPick, Seq.find and Seq.tryFind are all queries for single elements. Queries for single elements should be written by applying one of these functions to a sequence or some other collection.   Using IQueryables with the F# Power Pack   Now, as we mentioned above, .NET 3.5 introduced nice machinery for executing queries “in other ways”, for example as SQL on a database. An indicator of this is when a data source supports the type IQueryable which can be thought of as a “super enumerable”. If you see an object supporting IQueryable, then it’s likely that something “smart” can potentially go on under the hood, e.g. your queries can be implemented through a translation or optimization of some kind. For example, the objects representing handles to SQL tables may implement IQueryable.   In the rest of this post we’re going to look at how to write and execute queries that utilize IQueryables by using some simple functionality from the F# Power Pack.  (Note: Anything supporting IQueryable also supports IEnumerable, so you can use it just like an ordinary F# sequence, if the data source is small).   First, however, let’s look at the simplest form of IQueryable, which is a simple wrapper around some in-memory data – this is, in a sense, a “dumb” IQueryable.   #r "System.Core.dll" open System.Linq let db = Queryable.AsQueryable<Customer>(data)   We can invoke the IQueryable “way” of accessing this data as  follows:   #r "FSharp.PowerPack.Linq.dll" open Microsoft.FSharp.Linq open Microsoft.FSharp.Linq.Query   let q2 =     query <@ seq { for i in db do                       if i.Name.Length = 6 then                          yield (i.Name,i.UniqueID) }  @>   That is, we take the original query, and put query <@ ... @> around it. Once the query is constructed, the result can be used as an ordinary IEnumerable, e.g.           q2 |> Seq.toList   This will give the same result as before. The important thing is the above can be used with any IQueryable, and that the query is executed through the IQueryable machinery. This means the syntax tree for the query is passed, piece by piece, to the IQueryable. For “real” IQueryables this in turn translates the query to a form executed on a database or a remote server.   Example: Database Queries   So far, we’ve seen the basic philosophy for the IQueryable support in the F# Power Pack; for F# query expressions involving IQueryables, you can query <@ ... @> around the expression and it gets executed through the IQueryable machinery. We’ll go into what constitutes an F# query expression a bit later, but first let’s take a look at doing database queries via this mechanism. (A short digression before we start doing database queries; don’t forget you can also do queries using more fundamental mechanisms such as those used by ADO.NET, a topic well covered in books such as Foundations of F# and Expert F#)   First let’s reference the SqlMetal generated interface to the famous NORTHWND database (Note: a version is in the zip attached to the blog, along with the northwnd.dll built by run SqlMetal.exe on this database and compiling the generated C# code to a DLL)   #r "System.Data.Linq.dll" #r "northwnd.dll"   Assuming you have copied NORTHWND.MDF to your working directory, you can open the database using a version of SQL Express with this connection string:   let sqlServerInstance = @".\SQLEXPRESS" let connString = @"AttachDBFileName='" + __SOURCE_DIRECTORY__ + @"\NORTHWND.MDF';Server='" + sqlServerInstance + "';user instance=true;Integrated Security=SSPI;Connection Timeout=30"   let db = new NORTHWND(connString)   It’s handy to set the log:   db.Log <- System.Console.Out   Let’s now define a simple query:   let q3 =     query <@ seq { for i in db.Customers do                       for j in db.Employees do                          if i.Country = j.Country then                             yield (i.ContactName, j.FirstName, j.LastName) } @>   We now recognize this as a query over an IQueryable (in this case the database tables are IQueryables). We can now execute this database query as SQL on the server and return the results, e.g.           q3 |> Seq.toList   This will produce a list of 93 entries. Here’s a second example:   let q4 =    query <@ seq { for c in db.Customers do                      for e in db.Employees do                          if c.Address.Contains("Jardim") &&                             c.Address.Contains("rosas") then                                yield (e.LastName,c.ContactName) } @>   // Now execute a query q4 |> Seq.toList   And a similar example using sorting, within the query:   let q5 =    query <@ seq { for c in db.Customers do                      for e in db.Employees do                          if c.Address.Contains("Jardim") &&                             c.Address.Contains("rosas") then                                yield e }             |> Seq.sortBy (fun e -> e.LastName) @>    q5 |> Seq.toList   Here the sortBy occurs within the <@ ... @> , indicating it is executed as part of the database query, rather than in-memory.   As indicated above, the aim of this blog post is not to show how to write every kind of SQL or LINQ query with the F# Power Pack. However, let’s take a quick look at the set of operators that you can use inside a query <@ ... @> . For starters, a query expression can be one of these forms,        seq { seq-expr }      [ seq-expr ]      [| seq-expr |]   Where the sequence expression contains the usual sequence expression constructs,:       seq-expr =       | for pat in query-expr do seq-expr       | if expr then seq-expr else seq-expr       | yield! query-expr            | seq-expr; seq-expr            | yield expr            | ...   Next, a query expression can also be made up of uses of the following operators and syntactic forms, perhaps via pipelining:         Seq.toArray       Seq.toList       Seq.length       Seq.head       Seq.find       Seq.max       Seq.min       Seq.average       Seq.averageBy       Seq.sum       Seq.exists         Seq.forall        Seq.sumBy       Query.maxBy       Query.minBy         Seq.empty       Seq.collect       Seq.filter       Seq.map       Seq.take       Seq.sort                    Seq.distinct       Seq.sortBy       Query.contains       Seq.append       Query.groupBy       Query.join       Query.groupJoin   Not all combinations of these can be used together – for example, Seq.sortBy and several other operators must appear as the “outer” or “last” part of a query. Finally, a query expression can contain the following, which are useful for defining macros and shortcuts in the query:         reflected-definition [optional-args]       let v = e in qexpr-with-post-processing       let f args = e in qexpr-with-post-processing       if expr then qexpr1 else qexpr2         expr (of type IQueryable<_>) // e.g. db.Customers, f x   The ability to use reflected definitions in queries gives an interesting and powerful way to reuse query fragments, something I plan to discuss in a future post.   For technical reasons, you must use the Query.* versions of some operators. For example, joins are expressed using the Query.join and Query.groupJoin operators.   query <@ Query.join db.Employees db.Customers              (fun e -> e.Country)              (fun c -> c.Country)              (fun e c -> e)           |> Seq.length  @>   Though often similar queries can be written using a conditional:   query <@ seq { for e in db.Employees do                   for c in db.Customers do                      if e.Country = c.Country then                          yield e }           |> Seq.length  @>   Note that when joins are expressed as combinators, they are a little more verbose than joins written in comprehension syntax such as in C#.    Some final notes:   Ø  The above hasn’t touched on nullable values, which are, of course, an important issue in database work. In F#, you must unwrap nullables explicitly – on the whole no implicit lifting of operators is provided.   Ø  There are many things that can not be used inside queries, for example arbitrary imperative code. The "query" function will give a runtime failure if the query can't be translated. There are also some restrictions we plan to lift in future versions of the power pack, mostly around the use of tuples as replacements for anonymous types.   Ø  Due to an omission, Seq.sort isn’t in the list above, though we’ll be adding it in the next release of the F# Power Pack. You can use Seq.sortBy instead.   Ø  The code for the F# Power Pack is in the F# CTP release, so if you wish you can take a look at how all this is implemented. For example, if you’re interested in how F# quotations get translated to LINQ expression trees, then this is where you to look. There is also an interesting pre-processing phase that effectively walks the F# quotation tree looking for the Query DSL outlined above.   Ø  We’re planning a CodePlex release of the Power Pack under a more general license – more on that sometime soon!   Ø  The design goals for the F# Power Pack support for queries aren’t the same of the design goals for C# and VB’s LINQ support. For example, those languages had a strict goal to make the embedded LINQ DSL query language look and feel much like SQL, though with some variations in phrasing and ordering. The F# Power Pack design goals are to make it feasible to write the most common queries against the strongly typed ORM models provided by SqlMetal, building on the existing techniques and knowledge of the F# programmer. It does assume you know and are comfortable with F# programming.    
Fri, 23 Oct 2009 21:58:00 GMT

New Book Out: F# for Technical Computing
Jon Harrop has a new book out, called F# for Techncial Computing. To quote: Read this full-color book to learn how Microsoft's new F# programming language can be used as a next-generation platform for high-performance interactive technical computing. Topics covered include the latest version of the F# language, parallel programming with the Task Parallel Library, Windows Presentation Foundation for visualization, concurrent programming with asynchronous workflows, file manipulation, text handling including regular expressions, data structures, algorithms and performance optimization. ... I've looked over a draft of the book, and, as always with Jon's writing, came away very impressed. Lots more details are on the page above. Enjoy! don
Fri, 23 Oct 2009 11:41:00 GMT