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#  

 

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 ty_i : 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!

 

 

 

 

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

 

 

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.

 

 

Posted by dsyme | 0 Comments

Filed under: F# Design Notes, F# Snippets

Attachment(s): queries-with-fsharp-powerpack-v1.zip

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

dnAnalytics + Iridium --> Math.NET Numerics

I notice that two good open source .NET math projects, dnAnalytics and Iridium, are in the process of merging into one combined project, called Math.NET Numerics. Great to see some consolidation and alignment here.

If you're interested in open source math on .NET, this looks like a good opportunity to get involved. There is good F# expertise on this combined team, including Juergen van Gael, and I'm sure contributors looking to work on the these libraries from the F# persepctive will be welcome.

[ Note: there are other great math products on .NET, both open source and commercial - if you'd like me to blog about one, please let me know ]

don

 

Some Smaller Features in the Latest Release of F#

Brian has blogged about some of the smaller features in the latest release of F# which weren't explicitly called out in the detailed release notes.

• Error and warning messages have unique numbers (in particular replacing the ubiquitous "FS0191")
• Some common error diagnostics have been improved
• VS2010 Beta2 has more item tempaltes

I'll add a few here as well:

• A note on version numbers
• A note on .fsproj file portability
• PowerPack: Adding "module" declarations to FsLex and FsYacc
• Power Pack: Unicode Lexing
• PowerPack: HashMultiMap constructor needs HashIdentity.Structural parameter
• PowerPack: Explicit "open Microsoft.FShap.Math" needed for "complex"

A note on version numbers

A note on version numbers. In previous releases of F# we've used one version number for everything: language, library, power pack etc. This doesn't make quite so much sense when we now ship F# bits for use with both .NET 2.0 and 4.0. On the whole you won't need to be aware of this difference, but in this release we use:

• 1.9.7 : the F# language version. This will be the number used at the top of the language specification

You'll also see 1.9.7.4 reported as the F# compiler version number for VS2010, and 1.9.7.8 for the compiler in the CTP ZIP and MSI. These compilers are the same apart from some very minor differences such as this.

FSharp.Core.dll has version number 2.0.0.0 or 4.0.0.0 in this release, depending on whether you're running on .NET 2.0 or 4.0. For .NET 4.0 references to the former are redirected to the latter automatically.

.fsproj files

For various reasons unrelated to F#, Visual Studio project files (.fsproj, .csproj etc.) can't be authored in a way that makes them imediately usable with both VS2008 and VS2010. I personally prefer to edit project files by hand, and if you don't mind doing that, then to make an F# VS2008 project file usable with VS2010 you just have to do two things:

• Replace ToolsVersion="3.5" with ToolsVersion="4.0" at the top of the file
• Replace

            <Import Project="$(MSBuildExtensionsPath)\FSharp\1.0\FSharp.PowerPack.Targets" />

with

             <Import Project="$(ProgramFiles)\Microsoft F#\v4.0\Microsoft.FSharp.Targets" />

at the bottom of the file. You may need to adjust some of the contents of the files as well, particularly project references.

PowerPack: Adding "module" declarations to FsLex and FsYacc

The F# Power Pack includes tools fslex and fsyacc, which are lexer generators and parser generators. You can use these in F# projects using an entry like the following in your .fsproj file:

    <FsYacc Include="Parser.fsy">
      <OtherFlags>--module Parser</OtherFlags>
    </FsYacc>

    <FsLex Include="Lexer.fsl" >
      <OtherFlags>--unicode</OtherFlags>
    </FsLex>

The "module" argument to FsYacc is recommended because F# now requests that you prefix compiled .fs files with a namespace or module declaration. FsYacc must add this to both generated .fs and .fsi. You can also add "--internal" if you want this module to be internal.

To specify a module declaration for an FsLex file, use a definition at the top of the .fsl file, e.g.

lex.fsl:

    {

        module internal Microsoft.FSharp.Compiler.Lexer

        ....

The different ways of treating this for FsLex and FsYacc are a little non-orthogonal, but this is how the F# Power Pack does work for this release, and we'll continue to support this going forward.

Power Pack: Unicode Lexing

Since we're on the topic of lexing and the power pack, we may as well mention unicode lexing. The "unicode" argument to FsLex is optional, but if enabled generates a unicode lexer.

A unicode lexer works with a LexBuffer<char> rather than LexBuffer<byte>. This means extracting the text from of a lexeme is a little different. There are basically two ways:

lexbuf.Lexeme  -- returns a character array

LexBuffer<_>.LexemeString lexbuf    -- returns a string

For example, the MegaCalc example in the F# tutorial includes this rule:

| ['-']?digit+    { INT32 (Int32.Parse(LexBuffer<_>.LexemeString lexbuf)) } 

In a unicode lexer, you can use Unicode character classes and individual Unicode characters in your rules. For example, the following may be used as definitions in an FsLex file (note, these are definitions in the FsLex domain specific language, and not F# code)

let letter = '\Lu' | '\Ll' | '\Lt' | '\Lm' | '\Lo' | '\Nl'

let surrogateChar = '\Cs'

let digit = '\Nd'

let connecting_char = '\Pc'

let combining_char = '\Mn' | '\Mc'

let formatting_char = '\Cf'

 

let ident_start_char =

    letter | '_'

 

let ident_char =

    letter

  | connecting_char

  | combining_char

  | formatting_char

  | digit 

  | ['\'']

 

PowerPack: HashMultiMap constructor needs HashIdentity.Structural parameter

The F# Power Pack includes a mutable collection type called HashMultiMap. The "new" constructor for this type now requires an extra argument of type IEqualityComparer<'T>. You can usually fill this in by using HashIdentity.Structural, which is an F# implementation of IEqualityComparer<'T> which works by using F# generic hashing and equality.

 

PowerPack: Explicit "open Microsoft.FShap.Math" needed for "complex"

The F# Power Pack includes a complex type and a function "complex" for making complex number values from rectangular coordinates. You now need to both reference the F# Power Pack and use "open Microsoft.FSharp.Math" to acccess this function.

 

 

 

 

 

F# in Visual Studio 2010 Beta2 is now available ( plus matching F# CTP Update for VS2008)

The latest release of F# is now out! This is included in Visual Studio 2010 Beta2 , released today for MSDN Subscribers, with the matching release of the F# CTP for Visual Studio 2008, and a compiler ZIP for Mono. The detailed release notes are here. (Note: general download availability of Visual Studio 2010 Beta2 will begin in the next few days.)

This is an incremental release, supporting the vision outlined by the F# team, the Microsoft Developer Division and Microsoft Research of including F# as a supported language in Visual Studio.  The focus of the release has been to address some design issues necessary to improve F# and put it on a long-term stable, reliable and supported basis.

With this release, we are enabling F# support for multi-targeting with VS2010. This means that VS2010 projects can be targeted to produce binaries for any of .NET 2.0-4.0, for example if you are a library vendor building 2.0 dlls for use on 2.0-4.0, or working in an environment where .NET 2.0-3.5 development is the norm.  Additionally, we will be supporting development of F# components targeting Silverlight, through the inclusion of a template for Silverlight library components. In line with the philosophy we outlined in the previous release of F#, we expect the focus of F# in this domain to be components that handle the algorithmic and communication patterns common in client-side programming, particularly in enterprise scenarios.

We have also taken crucial steps towards our goal of ensuring binary compatibility for components across .NET 2.0-4.0. For example, in previous releases different copies of the F# Power Pack were required for .NET 2.0-3.5 and 4.0. However, in this release we have one version of the Power Pack which can be used on both .NET 2.0-4.0 (installed via the CTP MSI or ZIP). If you are authoring F# binary components, you can now build binary compatible components in a similar way (note: some important Beta2 caveats are in the release notes). As we have discussed with the F# community, full ongoing binary compatibility is expected starting with the version of F# that comes with the Visual Studio 2010 RTM release.

At the source level, we are now aiming for no more changes to FSharp.Core.dll before the Visual Studio 2010 RTM release, apart from removing deprecated functionality. Existing F# users should pay careful attention to deprecation warnings since we will be removing deprecated functionality with the version of F# that will come with the Visual Studio 2010 RTM release.

There are also some simplifications to the F# language. For example, the OverloadID attribute is no longer needed when defining method overloads, we have added support for placing definitions in the global namespace and simplified conversion operators such as int32. Some important restrictions have been lifted with regard to object oriented programming, and discriminated unions now have a cleaner code generation pattern when used from other .NET languages. We’ve also made F# programming safer by adding a new feature called equality and comparison constraints used to ensure that F# types such as Map and Set are only used with types supporting the necessary operations. This is documented further in the F# release notes, and an update to the F# language specification will follow in the next week.

This release also includes final, relatively modest improvements to the F# Core Library. These include simplifications to F# asynchronous programming. For example, using asynchronous programming with WPF, Silverlight and ASP.NET components is now even easier, as described in the release notes. We have included the array2D operator for creating 2D arrays. We’ve also addressed version-stable serialization of Map and Set, and aligned F# lazy values and cancellation with the designs of .NET 4.0. F# first class events now support the IObservable interface (new in .NET 4.0, also supported by F# 2.0, and also used by the Reactive Framework). The F# library also includes a modest library of Observable operators, following the pattern of the Event operators already present in F#.

F# now supports reusable script components through the support of #load on .fsx components. By taking the closure of script references, common code can now by factored into reusable .fsx components. These components can be executed with F# Interactive, or compiled with the command line F# compiler.

For F# in Visual Studio, we have addressed a multitude of issues, including F1 support, improvements for the Error List, issues in the Project System and better debugger display of unions and other F# types. For F# documentation, the F# Core Library docs have been integrated into MSDN.

Many thanks to everyone in the F# community for so much great feedback and encouragement during the last few months. The F# core team have worked hard to ensure a good release, and as always we’re very keen to hear your continued feedback. Please report any issues or problems you spot as soon as possible, to ensure we can act on it in time for Visual Studio 2010 RTM! (really, I mean that – try it now, and please send us feedback!)

Don, for the F# team!

Release notes

Release Notes for the F# October 2009 release

 

(These notes apply to the F# October 2009 CTP update and Visual Studio 2010 Beta2)

 

Summary

• Release
• F# in Visual Studio2010 Beta2 can build applications for .NET 2.0/3.0/3.5/4.0 and Silverlight 2/3. 
• Updated F# CTP for Visual Studio 2008
• F# PowerPack available as part of the CTP Update, and can be used with either CTP Update of VS2010 Beta2
• F# Language
• OverloadID no longer required for defining overridden methods
• Require module/namespace at top of files
• ‘comparison’ and ‘equality’ constraints
• Core conversion operators use .NET standard op_Implicit/op_Explicit instead or ToInt32, etc.
• Support for global namespace qualification, “global.A.B.C” and “namespace global”
• More flexibility in defining yield! and return! in computation expressions using YieldFrom and ReturnFrom
• Extension methods can participate in overload resolution
• Support for volatile fields using [<Volatile>]
• Support for letting F# types allow “null” using [<AllowNullLiteral>]
• Interface implementations can now be inherited
• Private type abbreviations (type private X = int)
• More flexibility for list literals and subtyping
• Recursive type inference improvement
  
• F# Compiler
• HTML doc generation moved from compiler to PowerPack
• Discriminated Union code generation provides simpler .NET view
  
• F# Core Libraries
• Complete the under_score -> camelCase name standardization, of_list -> ofList
• Async API Additions for Web Requests
• Async API Additions  for Reactive Applications
• Array2D enables easily creating 2D arrays
• Observable module
• Version-stable serialization of Map and Set
• [.NET 4.0] Lazy, CancellationToken, BigInteger in .NET4.0
• CompiledName used to ensure .NET view is C#/VB friendly
  
• Visual Studio
• Multitargeting for VS2010: 2.0-4.0 + Silverlight
• Error list improvements
• Much improved debug display of unions and other F# types.
• F1 support
  
• F# Interactive
• #load .fsx
  
• F# PowerPack
• Async additions
• FsHtmlDoc.exe
  
• Miscellaneous
• Deletion of features deprecated in previous F# releases
• Plus many minor fixes and improvements
  

F# Language

OverloadID no longer required for defining overridden methods

 

Overloaded methods can now be defined without the need for the OverloadID attribute. 

 

type Foo() =

    member this.CountChars(s : string ) = s.Length

    member this.CountChars(c : char) = 1

Require module/namespace at top of files

 

All .fs files, except the last file in an application project, must begin with either a module or namespace declaration.  Previously files were put in a default module named after the file.  Files can be structured to define an F# module:

 

module Widgets

 

type T() =

    member this.X = 12

let x = 12

Or a namespace:

namespace Widgets

 

type T() =

    member this.X = 12

Nested modules and namespace may be defined as before.

Note: Code of the form

namespace Widgets

 

module Module1

…

should be rewritten as

 

module Widgets.Module1

 

…

 ‘comparison’ and ‘equality’ constraints

 

Two new F#-specific  constraints  are added:

ty : comparison

ty : equality

Note: Equality includes "hashing"

 

A type satisfies ty : equality under these conditions

Ø  if the type has dependencies T1, ..., TN then each of these must satisfy equality; AND

Ø  the type doesn't have the NoEquality attribute; AND

Ø  the type is not inferred to be NoEquality (for record, union and struct types)

A type satisfies ty : comparison under these conditions

Ø  if the type has dependencies T1, ..., TN then each of these must satisfy comparison; AND

Ø  the type doesn't have the NoComparison attribute; AND

Ø  the type implements IComparable, or the type is an array/IntPtr/UIntPtr; AND

Ø  the type is not inferred to be NoComparison (for record, union and struct types)

One ramification of this is that most .NET types satisfy equality, even if this defaults to reference equality.

 

These constraints are used on some common parts of the F# library:

 

    val max        : 'T[] -> 'T        when 'T : comparison

    val min        : 'T[] -> 'T        when 'T : comparison

    val sort       : 'T[] -> ‘T[] when 'T : comparison

    val sortInPlace: 'T[] -> unit      when 'T : comparison

    val maxBy      : ('T -> 'Key) -> ‘T[] -> 'T when 'Key : comparison

    val minBy      : ('T -> 'Key) -> ‘T[] -> 'T when 'Key : comparison

    val sortBy     : ('T -> 'Key) -> ‘T[] -> ‘T[] when 'Key : comparison

    val sortInPlaceBy: ('T -> 'Key) -> ‘T[] -> unit when 'Key : comparison

    val countBy    : ('T -> 'Key) -> seq<'T> -> seq<'Key*int> when 'Key : equality

    val distinct   : seq<'T> -> seq<'T> when 'T : equality

    val distinctBy : ('T -> 'Key) -> seq<'T> -> seq<'T> when 'Key : equality

 

 

    val ( < )   : 'T -> 'T -> bool when 'T : comparison

    val ( > )   : 'T -> 'T -> bool when 'T : comparison

    val ( >= )  : 'T -> 'T -> bool when 'T : comparison

    val ( <= )  : 'T -> 'T -> bool when 'T : comparison

    val ( = )   : 'T -> 'T -> bool when 'T : equality

    val ( <> )  : 'T -> 'T -> bool when 'T : equality

    val compare : 'T -> 'T -> int  when 'T : comparison

    val hash    : 'T -> int        when 'T : equality

    val max     : 'T -> 'T -> 'T   when 'T : comparison

    val min     : 'T -> 'T -> 'T   when 'T : comparison

 

In some cases, code may need to be updated to take into account these constraints.

 

F# types may indicate how they participate in generic comparison or equality using attributes NoEquality/Comparison, StructuralEquality/Comparison. These are used on some F# library types, for example:

 

   

    [<NoEquality>]

    [<NoComparison>]

    type Async<'T>

 

In some circumstances it is also useful to make equality and comparison of a collection type conditional on a type parameter having equality/comparison. This is done using the EqualityConditionalOn and ComparisonConditionalOn attributes:

 

    type Set<[<ComparisonConditionalOn>] 'T  when 'T : comparison>

 

These attributes are inferred for structural types:

 

    // inferred: [<EqualityConditionalOn>] for T1, T1

    // inferred: [<ComparisonConditionalOn>] for T1, T2

    type Choice<'T1,'T2> =

      | Choice1Of2 of 'T1

      | Choice2Of2 of 'T2

 

Two new functions are available to access an "Unchecked" implementation of equality and comparison that is equivalent to the regular equality and comparison implementations, as used in previous implementations of F#, but may be used with any types without constraint

 

    Unchecked.compare

    Unchecked.equals

 

 

Further details of the equality/comparison constraint feature will be contained in the updated F# specification, to be released after these notes are posted.

Core conversion operators use .NET standard op_Implicit/op_Explicit instead or ToInt32, etc.

Overloaded conversion operators such as ‘int’, ‘char’ and ‘float’ which previously provided custom overloading via ToXXX conversion functions now use .NET standard op_Implicit/op_Explicit instead.  Any type defining an op_Implicit or op_Explicit returning the expected type can be used with these conversion operators.

type MyInt(x : int) =

    member this.X = x

    static member op_Explicit(myint : MyInt) = myint.X

 

let myInt = new MyInt(3)

 

// The 'int' conversion function calls the op_Explicit method on MyInt

let oldInt = int myInt

 

Support for global namespace qualification, “global.A.B.C” and “namespace global”

Types can now be defined in the .NET “global” namespace using:

namespace global

 

type T() =

    member this.X = 12

 

Additionally, in cases where partially-qualified names clash, name lookup can be qualified to the global namespace environment:

 

let line = global.System.Console.ReadLine()

 

More flexibility in defining yield! and return! in custom computation expressions

To support more flexible uses of computation expressions, the two computation expression forms yield! and return! are now de-sugared as follows:

yield! expr    ->   builder.YieldFrom expr

return! expr   ->   builder.ReturnFrom expr

 

Extension methods can participate in overload resolution

 

Extension methods can be defined as overloads of existing methods.  These are given a lower priority in overload resolution.  See the F# spec for full details.

 

type System.String with

    member this.Split(seps : string) =

        this.Split(

            [|seps|],

            System.StringSplitOptions.RemoveEmptyEntries)

       

let parts = "a b c  d".Split(" ")

 

Support for letting F# types allow “null” using [<AllowNullLiteral>]

 

Types defined in F# do not generally allow the use of the ‘null’ literal as a proper value.  However, null values can be passed in for these types from non-F# .NET callers, and sometimes it is necessary to write F# types that naturally do support a null proper value. 

type T1() =

    member this.X = 12

 

[<AllowNullLiteral>]

type T2() =

    member this.X = 12

 

let t1 : T1 = null // Error

let t2 : T2 = null // No error

 

Interface implementations can now be inherited

 

Interfaces implemented by inherited classes can be used to satisfy interface implementation requirements on a derived class. Code such as the following now compiles without the need to explicitly implement I1 in C2.

 

type public I1 =

    abstract V1 : string

   

type public I2 =

    inherit I1

    abstract V2 : string

   

type public C1() =

    interface I1 with

        member this.V1 = "C1"

 

type public C2() =

    inherit C1()

    interface I2 with

        member this.V2 = "C2"

More flexibility for list literals and subtyping

List and array literals may now be used to create collections from elements that are subtypes of the collection element type.  For example:

 

let myControls: (Control list) = [ new Button() ; new TextBox() ]

 

F# Compiler

HTML doc generation moved from compiler to PowerPack

The --generatehtml compiler option has been removed, and the functionality moved into a separate tool in the F# PowerPack (see below).  This enables decaoupling documentation generation from compilation, and more customization of doc generation.

F# Binary Compatibility 2.0-4.0

 

 

As we have discussed with the F# community, full ongoing binary compatibility is expected starting with the version of F# that comes with the Visual Studio 2010 RTM release.

 

This release has taken crucial steps towards the F# team goal of ensuring binary compatibility for components across .NET 2.0-4.0. For example, in previous releases different copies of the F# Power Pack were required for .NET 2.0-3.5 and 4.0. However, in this release we have one version of the Power Pack which can be used on both .NET 2.0-4.0 (installed via the CTP MSI or ZIP).

 

If you are authoring F# binary components, you can now build binary compatible components in a similar way. There are some important caveats to this due to two missing type forwarders in FSharp.Core.dll, notably

 

Ø  DLLs using Array2D.* or 2D arrays in public API surface area are not automatically binary compatible across 2.0/4.0. With care these DLLs can be made binary compatible across 2.0/4.0, and this has been done for the F# Power Pack,  but normally these APIs will not be binary compatible across 2.0/4.0 until Visual Studio 2010 RTM

 

Ø  Likewise DLLs using F# lazy values (System.Lazy<_>) are not automatically binary compatible. With care, these DLLs can be made binary compatible across 2.0/4.0 by using a private copy of the F# lazy implementation from .NET 2.0, and this has been done for the F# Power Pack. However in the absence of special attention these APIs will not be binary compatible across 2.0/4.0 until Visual Studio 2010 RTM

 

Binary compatibility can be checked in part by running peverify for .NET 2.0 and .NET 4.0 after installing Visual Studio 2010, a version of Visual Studio 2008 and the F# CTP.

 

F# Core Libraries

 

 

 

Async API Additions for Web Programming

 

The extension methods webClient.AsyncDownloadString and webRequest.AsyncGetResponse are now defined in FSharp.Core.dll, and accessed via

 

open Microsoft.FSharp.Control.WebExtensions

 

For example:

 

open System.Windows.Forms

open System.Net

open System.IO

open Microsoft.FSharp.Control.WebExtensions

 

/// Fetch the contents of a web page, asynchronously

let httpAsync (url:string) =

    async { let req = WebRequest.Create(url)            

            let! resp = req.AsyncGetResponse()

            // the rest is a callback

            use stream = resp.GetResponseStream()

            use reader = new StreamReader(stream)

            return reader.ReadToEnd()  }

 

 

 

 

Async API Additions  for WinForms, WPF, Silverlight  and ASP.NET applications

 

The Async API has a number of new additions and design extensions to better enable writing “single-primary-thread-of-control” reactive applications using F# asyncs. This is a commonly used idiom for Windows Forms, WPF, Silverlight  and ASP.NET programming.

 

These applications are I/O parallel, but only use CPU parallelism in constrained ways. In this kind of application, CPU processing is done on a single thread of control, but multiple I/O requests may be overlapped.

 

In .NET, these applications will typically have a non-null, dedicated value for System.Threading.SynchronizationContext.Current on the main “thread”.

Waiting for .NET Events

 

The method Async.AwaitEvent is now defined in FSharp.Core.dll. This method runs the continuation of the async the first time .NET event fires.

 

open System.Windows.Forms

 

let form = new Form(Visible=true,TopMost=true)

 

async { let! firstClick = Async.AwaitEvent form.Click

        form.Text <- "I got clicked once!"

        let! nextClick = Async.AwaitEvent form.Click

        form.Text <- "I got clicked twice!" }

|> Async.StartImmediate

 

Starting Asyncs on the Current Thread

 

The methods Async.StartImmediate and Async.StartWithContinuations are now defined in FSharp.Core.dll. These methods start the async immediately on the current thread, until the first point where the thread yields through an operation such as Async.AwaitEvent or an I/O operation.

 

These methods are particularly useful for starting async operations on the GUI or ASP.NET thread.

 

A use of StartImmediate is shown above.

 

Automatic Return to Context

 

F# library async I/O and waiting primitives can now be used from GUI or ASP.NET threads in a simpler fashion. Conceptually, if you start an async I/O operation or an async wait operation on a GUI thread, then it will “complete” on the GUI or ASP.NET thread.

 

If a primitive async operation is started on a thread where SynchronizationContext.Current  is set, then the continuation of such an async is posted using SynchronizationContext.Post.  

 

In the following example the overall async is started on the GUI thread using StartImmediate. As the click happens and the asynchronous fetches of the web pages return, the overall async is in each instance continued on the GUI thread.  This means the GUI components can be safely updated from the async.

 

open System.Windows.Forms

 

let form = new Form(Visible=true,TopMost=true)

 

async { let! firstClick = Async.AwaitEvent form.Click

        form.Text <- "I got clicked!"

        let! firstPage = httpAsync "http://www.google.com"

        form.Text <- "I got the first page!"

        let! secondPage = httpAsync "http://www.bing.com"

        form.Text <- "I got the second page!" }

|> Async.StartImmediate

 

F# asyncs built using the following API operations implement “automatic return to context”:

  

Async.Parallel

Async.Sleep

Async.AwaitEvent

Async.AwaitIAsyncResult

Async.AwaitTask

Async.AwaitWaitHandle

Async.FromBeginEnd

Async.FromContinuations

 

type System.Net.WebRequest with

    member AsyncGetResponse()

 

type System.Net.WebClient with

    member AsyncDownloadString()

 

type System.IO.Stream with

    member AsyncRead()

    member AsyncWrite()

 

Async API Renamings

System.Threading.AsyncSleep         ->    Async.Sleep

extension waitHandle.AsyncWaitOne   ->    Async.AwaitWaitHandle

extension waitHandle.AsyncWaitOne   ->    Async.AwaitWaitHandle

Async.BuildPrimitive                ->    Async.FromBeginEnd

Async.SwitchToGuiThread             ->    Async.SwitchToContext

Async.RunWithContinuations          ->    Async.StartWithContinuations

 

Complete the under_score -> camelCase name standardization, of_list -> ofList

 

The naming normalization across the F# core libraries is finalized in this release, with the following removals of underscores and abbreviations:

to_list      -> toList

to_array     -> toArray

to_seq       -> toSeq

of_list      -> ofList

of_array     -> ofArray

of_seq       -> ofSeq

of_nativeint -> ofNativeInt

to_nativeint -> toNativeInt

hd           -> head

tl           -> tail

 

Observable module and F# events

 

The IObservable and IObserver interfaces provide a general interface over observable data, which can be easily composed.  These interfaces are provided in .NET4.0, and are available in F# for .NET2.0. 

1^st class events in F# now implement the IObservable interface, enabling them to interoperate with other IObservable programming models.  A new Observable module in the F# library provides compositional functions for manipulating general Observable data:

    Observable.merge

    Observable.map

    Observable.filter

    Observable.partition

    Observable.split

    Observable.choose

    Observable.scan

    Observable.add

    Observable.subscribe

    Observable.pairwise

 

array2D enables easily creating 2D arrays

 

A new ‘array2D’ function converts data into 2d arrays:

 

let matrix = array2D [[1;2;3];

                      [2;3;4];

                      [3;4;5]]

 

 [.NET 4.0] Lazy, CancellationToken, BigInteger in .NET4.0

 

Some F# types have moved into mscorlib in .NET4.0, making it easier to reuse these types between F# and other .NET languages.  On .NET2.0, these F# types have been moved to corresponding namespaces within FSharp.Core.dll.  The following important F# types have moved to System namespaces:

Lazy -> System.Lazy

Tuple -> System.Tuple

BigInt -> System.Numerics.BigInteger

AsyncGroup -> System.Threading.CancellationTokenSource and System.Threading.CancellationToken

 

CompiledName used to ensure .NET view is C#/VB friendly

 

The .NET-visible names of types and members in FSharp.Core.dll are modified to align with standard .NET naming conventions.  This makes it easier to use FSharp.Core defined types from other .NET languages.  For example:

Seq.iteri -> Microsoft.FSharp.Collections.SeqModule.IterateIndexed

failwith -> Microsoft.FSharp.Core.Operators.FailWith

Visual Studio

 

[VS2010] Multitargeting support for 2.0-4.0 + Silverlight

 

With VS2010, F# users can target .NET 2.0, 3.0, 3.5, 3.5 Client, 4.0 and 4.0 Client.  F# libraries can also be built targeting Silverlight 2 and 3.  F# libraries built against .NET2.0 can also be used as part of F# applications targeting later versions of .NET.

 

Error list improvements

 

The Visual Studio error list is populated with F# errors both during editing of F# files, and during building of F# projects.  This release ensures that errors are tracked between these two sources when they are available in both.

 

F1 support

 

F1 contextual help support is available in the F# editor.  This will open documentation for the type or member reference at the cursor.  In addition, in VS2010, F1 help on F# keywords or F# library functions will go to the new MSDN documentation on these subjects.

F# Interactive

 

#load .fsx

 

When building complex F# scripts, it is sometimes necessary to split a script into multiple .fsx files.  F# scripts now support the ability to load other F# scripts, enabling factoring of scripts into source components. 

F# PowerPack

 

FsHtmlDoc.exe

 

A new tool called fshtmldoc.exe is now available in the F# Power Pack. This replaces the HTML doc functionality in the F# compiler. The command line options are shown using “fshtmldoc.exe --help"

 

 

Posted by dsyme | 0 Comments

Filed under: F# Announcements, F# Design Notes, F# Snippets, F# Concurrency

Soma on F# in Visual Studio 2010

Soma has a nice blog post on F# in Visual Studio 2010

With Visual Studio, we strive to give your organization the tools to tackle a broad range of software problems with the interoperability and efficiency that you need and have come to expect from software based on the .NET Framework.

 

As part of this, Visual Studio 2010 marks the first release to directly support functional programming through the F# programming language.

 

F# is a highly productive .NET programming language combining functional programming and object-oriented programming, and is ideally suited for parallel, algorithmic, technical and explorative development.  F# is the result of a close partnership between Microsoft Research and the Visual Studio team, and since announcing F# in Visual Studio 2010 we’ve seen a surge of interest and uptake in the language. We’ve also worked closely with the F# community and major adopters to ensure it meets the needs of professional software developers working in these domains.

Soma is a Senior Vice President at Microsoft in the Developer Division. Full post here.

Downloading F# Tutorial Code and Slides (JAOO 2009 Edition)

I've had a few reports of people having issues downloading the F# tutorial code and slides from my last post.

I just tried myself and it worked OK - I got a zip as expected. Please email me (dsyme at microsoft dot com) or leave a comment if you're still having problems after a few retries.

Thanks

don

F# Tutorial Code and Slides (JAOO 2009 Edition)

One of the great pleasures of my job is to go to conferences like JAOO and present on F# and other topics. This year I presented both a tutorial and a lecture at JAOO 2009, and I've included the tutorial and lecture slides below! Thanks to everyone who came along - I really enjoyed giving this one!

Some highlights of the code are:

• Foundational material on F# async programming, and samples including:
• Fetching web pages in parallel
• The Bing translator sample using async programming
• A Graphical, asynchronous twitter client in 50 lines
• A Twitter feed example that uses F# first class reactive event processing to process the stream of feeds
• An asynchronous web crawler
• Processing images in parallel, using a mixture of I/O and CPU parallelism
• An updated version of the famous Interactive DirectX demo
• Lots of great micro samples on foundational topics such as
• object oriented programming
• language oriented programming
• function composition
• design patterns
• discriminated unions
• records
• units of measure

The tutorial slides include important new slides on asynchronous programming. Over the next few blog entries I'll be taking a closer look at some of the material, especially in the areas of parallel and asynchronous programming.

I'd really appreciate your input on how we can make this tutorial even better. Giving an F# tutorial is enormously enjoyable and if you'd like to give a tutorial, please drop me a note (dsyme at microsoft dot com) and I'll send you the latest copy of the slides and code - we're already planning to add a few more , including a section on the standard F# "functional programming operators" such as List.map, List.fold etc.Send us your suggestions for further topics to cover!

Some of this material comes from Chris Smith, Matthew Podwysocki, Luke Hoban, Brian McNamara and James Margetson from the F# core team at Microsoft. Some snippets of the async samples showing the use of the PeriodicTable web service were co-developed with Robert Pickering (thanks Robert!)

Enjoy!

Don

 

F# Job: Credit Suisse GMAG seek Trader Tools Project Lead

Over the last few years the F# team at Microsoft have been very glad to work with the Credit Suisse GMAG group . GMAG (Global Modelling and Analytics)are successful adopters of F#, as they reported on at CUFP 2008. This continues strongly and the group continue to provide essential feedback on the design and implementation of the F# language and its related Visual Studio tools. 

The group is now looking for an outstanding project lead for a new initiative where they expect F# to play a significant role. A snippet of the job description is below, contact Howard Mansell (howard.mansell@credit-suisse.com) for more details.

THE POSITION: Trader Tools Project Lead (London)

One of the core activities of GMAG is to deliver tools to sales & trading that allow them to analyse markets and portfolios, and price trades.  We employ a number of technologies and frameworks, developed in GMAG-AD, for this purpose.  Our trader tools are currently deployed with an Excel front-end, with some amount of calculation implemented in Excel.  We intend to transition the delivery of these tools to a non-Excel environment.  We are looking for an outstanding individual to lead this effort.

 

Key requirements for the role are:

·         Experience of leading teams of highly-skilled technical specialists, and a demonstrated ability to deliver outstanding solutions to difficult problems.

·         Very strong understanding of commercial software development processes and distributed team development of complex code bases.

·         Ability to communicate well and understand the requirements of modellers and traders.

·         Expert-level hands-on knowledge of the Microsoft .NET framework.

·         Knowledge of functional and object-oriented programming paradigms.

·         Ideally the candidate will have experience with F#, WPF, COM, C++, C# and web development.

·         Experience in the finance sector is highly desirable but not essential.

Don

Keynote at EclipseCon Europe, 2009: Taking Functional Programming Into the Mainstream

Just to mention that I'll be giving a keynote lecture at the Eclipse Summit in Ludwigsburg, Germany on Wed 28 Oct. 2009.

I haven't been to EclipseCon before. am looking forward to learning a lot about the Eclipse community. In the past few years, my work has been in the context of Visual Studio, but I've definitely learned that there is much that the various IDE communities can share and learn from each other.

If you're planning on attending, drop me a note or stop by after the talk.

 

 

F# at JAOO 2009, Aarhus, 4-6 October

I’m excited to be giving a tutorial, a presentation and a panel at JAOO 2009 in Aarhus in early October. I’ve had the good fortune to be involved with JAOO and QCon a few times over the last few years, and am honoured to be presenting in Aarhus, the home of it all.

 

I’ve copied details below – hope to see you there!

 

Tutorial: "Getting Started With F#"

Time: Sunday, 4 Oct,  9:00 – 12:00

Abstract:  F# is a succinct and expressive typed functional programming language for the .NET platform, and Microsoft will be supporting F# as a first class language in Visual Studio 2010. In this tutorial you'll get a taste or F# programming from the basics through to some parallel and asynchronous programming with F#. You'll learn how to get started with the functional, imperative and object-oriented programming in F#, how to use shaped functional data to reduce the amount of state in your application, and how to use units of measure to bring sanity and checking to your numerical code. You'll also get a taste for some parallel and asynchronous programming, and take a look at some more advanced techniques in reflection.

 

Target Audience: Developers, architects and anyone interested in learning how to apply functional techniques in practice and have fun along the way

Presentation: "An Introduction to F#"

Track: Programming Languages

Time: Monday, 5 Oct, 13:30 - 14:30

Abstract: F# is a succinct and expressive typed functional programming language for the .NET platform, and Microsoft will be supporting F# as a first class language in Visual Studio 2010. We'll take a look at what you need to know to start having fun with F#, and how to use it productively. We'll also look at some sample applications of F# and functional programming and cover aspects of parallel, reactive and asynchronous programming with F#.

Target Audience: Developers, architects and anyone interested in learning how to apply functional techniques in practice and have fun along the way

Panel: "Concurrency Expert Panel"

Track: The Concurrency challenge

Time: Tuesday, 6 Oct,  13:30 - 14:30

Abstract: One theme of the panel is concurrent programming models. Specifically; classic locking, transactional memory and actors. And with concurrency we mean parallel systems (e.g. shared-memory multicore, cluster)

• The goal is performance
• One trust domain
• Latencies are small and predicable
• One failure => kill the program is just about tolerable
• One of the goals for the discussion would be to get a better understanding of strengths and weaknesses; advice and discussion about when to use which model.

Another goal is:

• for the audience to get to "pick the brains of the experts"
• to get a good discussion going amongst the experts
• to get concrete advice on choice of programming language (hence model) for certain problems.
• advice on solving common problems that appear when using a particular model