Rash thoughts about .NET, C#, F# and Dynamics NAV.

I’m happy to announce that I’m giving one of the “Progressive F# Tutorials 2012” in London this year. This event is going to be legendary. Abstract:

Test-Driven Development can give you a lot of benefits for your code but also needs a lot of practice. Come to this session and learn how to master TDD with F#, NaturalSpec and NCrunch.

NaturalSpec is a F# TDD framework which allows to express tests in a very intuitive way and NCrunch helps to execute these tests continuously on very key stroke. This gives a very fast feedback loop and helps to speed up your TDD coding.

After a short introduction of the tools we’ll try to solve a small coding problem together in a coding dojo. All skill levels are welcome and the session will give a lot of room to try out new ideas.

Book your tickets for this awesome event.

After the official Visual Studio 2012 launch yesterday I think it’s a good idea to announce two new type providers which are based on the DGMLTypeProvider from the F# 3.0 Sample Pack.

Synchronous and asynchronous state machine

The first one is only a small extension to the DGMLTypeProvider by Tao. which allows to generate state machines from DGML files. The extension is simply that you can choose between the original async state machine and a synchronous version, which allows easier testing.

If you want the async version, which performs all state transitions asynchronously, you only have to write AsyncStateMachine instead of StateMachine.

State machine as a network of types

The generated state machine performs only valid state transitions, but we can go one step further and model the state transitions as compile time restrictions:

As you can see the compiler knows that we are in State2 and allows only the transitions to State3 and State4.

If you write labels on the edges of the graph the type provider will generate the method names based on the edge label. In the following sample I’ve created a small finite-state machine which allows to check a binary number if it has an even or odd number of zeros:

As you can see in this case the compiler has already calculated that 10100 has an odd number of zeros – no need to run the test .

This stuff is already part of the FSharpx.TypeProviders.Graph package on nuget so please check it out and give feedback.

In the last post I wrote about the PersistentVector which I ported from Clojure to .NET. It’s implemented as an immutable hash array mapped trie which optimizes the constant factors so that we can assume O(1) for count, nth, conj, assocN, peek and pop.

But for some applications Rich Hickey shows us that we can optimize the constant factors even further. If we are sure that we are only holding exactly one reference to the vector than we can mutate the underlying representation instead of copying the arrays on every change. This idea is implemented in the TransientVector which I also ported from Clojure.Core to FSharpx.

Let’s look at a small example. Here we want to convert a collection to a PersistentVector:

As you can see we iterate over the collection and conj the items to the current PersistentVector. But in every step we forget the reference to the last version. This is exactly the point where can use TransientVector:

Here are the results:

Most higher-order functions on vectors like map are also implemented with this trick.

Rich Hickey created a very nice set of persistent collections for Clojure. I started to port them to FSharpx and today I want to present the PersistentVector. The basic idea is that we want to have something like an array but immutable.

Vectors (IPersistentVector)

A Vector is a collection of values indexed by contiguous integers. Vectors support access to items by index in log32N hops. count is O(1). conj puts the item at the end of the vector.
     From http://clojure.org/data_structures

These vectors are very fast in practical applications since the depth of the underlying tree is not greater than 7. First performance tests show the following on my machine:

These results are not that far away from the Clojure/Java implementation (see below). The lookup seems to be a bit faster but assoc is slower. Maybe that has something to do with the internal array copy function of .NET:

After installing the FSharpx nuget package can use this Vector<T> from C# like this:

More samples can be found in the PersistentVectorTest.fs file.

Additional resources:

• Original implementation
• Data structures in Clojure
• Rich Hickey on "Persistent Data Structures and Managed References"
• Understanding Clojure’s PersistentVector implementation
• Hash array mapped trie

I’m happy to annouce a new nuget release of FSharpx.TypeProviders. The new version 1.5.3 allows to access JSON and XML in a strongly typed way. These new type providers are based on an XML type provider by Tomas Petricek. I added a write API and a JSON version.

Idea

Whereas XML allows different ways to define a schema, JSON has no schema. Nevertheless most documents have some kind of an implicitly defined schema. These new type providers try to infer the schema from a sample file and provide you types to access any file which is conform to this schema.

Let’s take a look at some of the new features.

JSON access

Consider this JSON sample from Wikipedia:

Let’s add this file to a new F# solution and reference the FSharpx.TypeProviders.dll via install-package FSharpx.TypeProviders. Enable the type provider in the following dialog:

Now that we have a sample data and the type provider ready we get full Intellisense:

In most cases you want to use the initial document only as a sample, therefore it’s also possible to load a different document at runtime which the type provider will treat with the same schema:

It’s even possible to modify properties:

Accessing XML

After adding a reference to System.Xml.dll and System.Xml.Linq.dll it’s also very easy to access XML. Since both type providers have the same features we will use yet another way to provide a schema sample. In this case we give the schema inlined:

Schema invalidation

One important aspect of type providers is the schema invalidation. For instance try to remove the line with the age property of WikiSample.txt and save the file. The type provider will detect this schema change and your code will no longer compile:

Enjoy your statically typed JSON/XML documents.

F# 3.0 brings the new type providers feature which enables a lot of different applications. Today I’m happy to announce that the FSharpx project brings you a WPF designer for F# in the Visual Studio 11 beta.

A big kudos to Johann Deneux for writing the underlying XAML type provider.

1. Create a new F# 3.0 Console application project
2. Set the output type to “Windows Application” in the project settings
3. Use nuget and install-package FSharpx.TypeProviders.Xaml
4. Add references to WindowsBase.dll, PresentationFramework.dll, System.Xaml.dll and PresentationCore.dll
5. Add a Xaml file to your project. Something like this:
6. Now you can access the Xaml in a typed way:
7. Start the project

Enjoy!

BTW: No code generation needed is for this. No more nasty *.xaml.cs files.
BTW2: Try to change the name of Button1 in the Xaml and press save.

This is yet another blog post in my Currying and Partial application series. This is what I have posted so far:

• Partial application in F# and C#
• Why do we need partial application? – Part 1 of n – Fluent interfaces and piping
• Currying and uncurrying in C# and F#

In this post I want to show you a way to simulate type classes in C# and F#. Type classes are this wonderful feature in Haskell which allow you to specify constraints on your polymorphic types. We don’t have this in C# nor F#.

Let’s start with the following problem: We want to compute the sum of the squares of arbitrary numbers. We want to write something like this:

The problem is we don’t have a generic * function and of course we’d also need a generic + operator and maybe a generic zero. Obviously we need a constraint on the generic parameter T since + might not be defined for any type. So let’s define an interface for numbers:

Nothing special here, so let’s get straight to the implementation for integers and doubles:

So far so good. With this in our pocket we rewrite SumOfSquares() into this:

The trick is that we pass the concrete implementation as the first parameter into our function. This works exactly like a type constraint or as Simon Peyton-Jones would say: the vtable travels into the function. Notice that we don’t have access to the definition of in nor double. There is no way for us to express that int or double implement a number interface.

Now let’s try this out:

As you can see, this is perfectly type safe. We now have a way for poor man’s type classes in C#. Yay!

Now what has this to do with partial application? Let’s look at the same thing in F#:

We’re using a lot of partial application here. Exercise: Try to spot all the places.

Ok, you’re right. This post might be a little bit far away from the partial application stuff, but it’s still related. Somehow.

In the last couple of days I started to write some posts about Currying and Partial application:

• Partial application in F# and C#
• Why do we need partial application? – Part 1 of n – Fluent interfaces and piping

This time I want to show you how we can write a higher-order function which allows us to curry another function. Remember the multiplication function from the first post and it’s curried form:

Currying

The question is: how can we automate this transformation process? Remember we want to have the curryied form for partial application:

Let’s look at the signature of the desired Curry-function: in our case it has to take Func<int, int, int> and returns Func<int, Func<int, int>>.

If we generalize the ints to generic parameters and fix the signature then the implementation is trivial (Compiler Driven Programming). There is exactly one way to make this work:

The F# implementation does exactly the same, but without all the annoying the type hints:

Uncurrying

Of course you can undo the currying by applying a generic Uncurry-function:

And in F# this looks like this:

Libraries

Currying and Uncurrying are two very important concepts in functional programming so they are included in a couple of libraries:

• You can find it at the top of the Prelude in FSharpx (read more).
• You can find it in the Haskell Prelude.
• You can find similar functions in Scalaz.
• Adrian Lang wrote a library called partial-js which allows to do something similar in JavaScript.

My last blog post was yet another introduction to Currying and Partial application. Now I want to put the focus more on the why part. Why do we want to have our functions in curryied form most of the time? This is the first part of a small blog post series and shows partial application in F# pipelines.

Using “Fluent interfaces” is a popular technique to write code in a more readable form. In languages like C# they also provide a way to create the code much faster. On every . we get IntelliSense and this gives us a “fluid” way of writing.

Let’s consider the following task: we want to compute the sum of the square roots of all odd numbers between 1 and 100. In C# we can use the LINQ method chaining approach in order to do something like this:

Now how does this look in F#? It’s basically the same. We replace every . with the |> operator and use the analogous Seq.* functions:

Oups! What happened here? The F# compiler noticed a type error. Math.Sqrt needs a float as input but we gave it an int. C# uses implicit casts between int and float so we didn’t noticed the problem there. Implicit casts are a little bit problematic, at least if you want to have proper type inference so F# doesn’t have this feature. No problem, we are programmers so let’s add the conversion manually:

Notice that float is a function from int to float and not a cast.

Now you might ask: how does this all relate to partial application? The answer is simple: In every pipeline step we use a higher-order function (Seq.*) and apply the first parameter with a lambda. The second parameter is given via the |> operator from the line above.

By applying our rule of thumb from the last post were are able to remove the x parameters:

Now let’s step back to C#. Keeping this knowledge in mind we try to apply the same rule in order to get rid of the x parameters:

Oups again! Now we see same error in C#. In this case it doesn’t know how to apply the implicit cast. As I said they are “problematic”, but we know how to fix this:

Today I had a conversation on twitter about partial application and type inference in F#. Partial application is a very important and useful concept and there are a lot of resources out there. Here is a short list of related material:

• Uncovering the Unknown: Principles of Type Inference (video)
• Wikipedia: Currying, Partial application, Type inference
• StackOverflow: What is the difference between currying and partial application
• HaskellWiki: Partial application
• F# BootCamp Q&A on this blog

I promised to show a small sample and I hope this clarifies some of my points on twitter. Let’s consider a multiplication function in C#:

This function allows us to compute the product of two ints. But what can I do when I need a function which doubles its input? The solutions is easy: I just create a new function:

And when I need a function which triples its input? Same thing, just create another method. But can we do better?

Let’s transform the multiplication function into the curryied version. The transformation process is very easy once you see the pattern. It’s actually possible to write a function which curryies another function, but that’s something for another post. Anyway, here’s the curryied version:

It’s a little bit noisy with all the funky Funcs, but Ok. We can still write the double function in terms of multiply:

And of course we can use multiply directly (which might look a bit weird at first):

But we can also use it in another way, which we couldn’t really do before:

How cool is this? We just applied a single parameter and we got a new function without writing any method declarations. Unfortunately we wrote a lot of weird type declarations in order to get here, but hey.

Let’s move to a language which has type inference. Here’s the uncurryied version of multiply in F#:

The type signature tells us, that we have to give it a tuple of ints and then we get an int back. That’s exactly the same as in C#. Notice that we think about x1,x2 as only one parameter – a tuple. How can we get to the curryied form? It couldn’t be easier: just remove the parentheses and you’re done:

As you can see the type signature changes a little bit. The * is now just another arrow. This means we have basically the same as Func<int, Func<int, int>> but in a much nicer syntax. There is also another way to write this:

This looks like the C# version, but notice how nicely the arrows align to the type signature. If we want to use the multiply function than we can write something like this:

It’s also very easy to create partially applied functions:

And finally the point which made me write this post. There is a simple rule: whenever we have the same parameter as the last parameter of the left and the right side of a function definition, we can remove it. This leads us to:

Isn’t this beautiful?