F# |> I <3

I’ve been writing about F# for a little while now, and how it has influenced the way I code in C# on an everyday basis for 3 years. During the last couple weeks, I’ve finally had the chance to use F# at work for a real project (I’ll probably talk about that later). Yesterday evening (Europe time) at Build, Roslyn was open-sourced. That’s nice and people are probably going to talk about it for a while. But for me there was another very nice announcement : Visual F# is now taking contributions! F# is already an exciting language, full of clever features. With this new step, I’m convinced that it will go even further and I’m already looking forward to F# 4.0!

So don’t expect to see many more posts about C# on this blog, I’ve totally gone F#.

And now, the latest sample from Arolla’s Code Jam. The aim was to write code to express values with a range of uncertainty, and operations which manipulate those numbers. For instance, a value 3.5 +/- 0.5, multiplied by 1.0 +/- 0.1. The goal of the kata was to write code that expresses intent (the why), and not implementation details (the how).

In F#, I’ve just defined a type to wrap both the value and its precision, and an operator to conveniently build those values :

type Number = | Number of float * float

let (+-) n a = Number (n, a)

This code alone already allows me to build values just by writing expressions such as “4.0 +- 1.0”. The next step for me was to write some expressive tests, using FsUnit.

let [<test>] ``A number with accuracy is equal to itself`` () =
    (1.0 +- 0.5) |> should equal (1.0 +- 0.5)

let [<test>] ``Sum of two numbers sums the numbers and accuracies`` () =
    ((5.0 +- 0.5) + (3.0 +- 0.5)) |> should equal (8.0 +- 1.0)

Although we could handle distinctly every operator with specific logic, the goal of this kata is to express the intent in a generic fashion, so here is a combine method that has no specific meaning of what an operator does:

let combine op (Number(n1, a1), Number(n2, a2)) =
   let all =
      seq {
         for x in [n1-a1; n1+a1] do
         for y in [n2-a2; n2+a2] do
         yield op x y
   let minimum = all |> Seq.min
   let maximum = all |> Seq.max
   Number((minimum + maximum) / 2.0, (maximum - minimum) / 2.0)

Finally, we just have to add operator overloading to the type, the full code becomes:

type Number = | Number of float * float
    with override x.ToString() = match x with | Number(a, b) -> sprintf "%f +- %f" a b
         static member private combine op (Number(n1, a1), Number(n2, a2)) =
            let all =
                seq {
                    for x in [n1-a1; n1+a1] do
                    for y in [n2-a2; n2+a2] do
                    yield op x y
            let minimum = all |> Seq.min
            let maximum = all |> Seq.max
            Number((minimum + maximum) / 2.0, (maximum - minimum) / 2.0)
         static member (+) (x, y) = (x, y) |> Number.combine (+)
         static member (-) (x, y) = (x, y) |> Number.combine (-)
         static member (*) (x, y) = (x, y) |> Number.combine (*)
         static member (/) (x, y) = (x, y) |> Number.combine (/)
         static member Pow (x, y) = (x, y) |> Number.combine ( ** )

Thanks to @luketopia for the interactions on Twitter, and the trick which allows to pass the operator ** as an argument: use spaces between the parenthesis and the operator!

Posted in F sharp love | Tagged , | Comments Off

Pattern matching in C# – part 4 – more tuples

DISCLAIMER: this post has been written months ago and never posted. By that time I was still trying to bring F# goodness to C#. This might be easier today with Roslyn, but that is not the path I’ve taken. Since the last post of this series, I’ve been doing more and more F#, even during my day job. I don’t think I’ll ever post this kind of ‘’How to do F# in C#” posts. What you can expect from this blog is now mostly functional programming in F#…

Today’s post will be a short one, as an answer to question from several months ago:

But if we want to handle tuples with more values… do we have to write all the overloads ?!

The answer is yes. With the current implementation, there has to be a method overload for every combination of patterns that you want to be able to match…

But wait a minute… For a given tuple of n values, there are 3n combinations… That makes a lot of methods to write ?!

You don’t have to actually write all these overloads yourself! T4 templates are there exactly for that purpose. If we want to generate all the extensions methods for the tuples of 2 elements up to 4 elements, for instance, we just have to build a .tt file, and define the 3 individual patterns as a string array :

string[] argumentsPatterns = new[]
    "T{0} testValue{0}",
    "Expression<Func<T{0}, bool>> testExpression{0}",
    "MatchCase any{0}"

Then and include a first loop :

for(int cardinality = 2; cardinality <= 3; cardinality++)

As we are going to write the type arguments quite a few times, we store them in a string, as well as the type of the selector argument:

string typeArguments = string.Join(
    ", ",
    Enumerable.Range(1, cardinality)
              .Select(n => string.Concat("T", n.ToString())));

string selectorArgument = string.Concat(
    ", TResult>> selector");

Inside the first loop we then loop over all the 3cardinality combinations :

for(int caseNumber = 0;
    caseNumber < System.Math.Pow(3, cardinality);

And we decompose the caseNumber into an array of int whose values can either be 0, 1 or 2, corresponding to the index of the pattern associated with each argument. For instance, with a cardinality of 4 and a caseNumber or 4, we would get an array containing [0, 0, 1, 1] :

int[] argumentsPatternsCases = new int[cardinality];
int argumentFlags = caseNumber;
for(int argumentIndex = 0;
    argumentIndex < cardinality;
    argumentsPatternsCases[cardinality - argumentIndex - 1] =
        argumentFlags % 3;

    argumentFlags = argumentFlags / 3;

From all this, we can generate the signature of the method :

public static PatternMatcher<Tuple<<#= typeArguments #>>, TResult>
    Case<<#= typeArguments #>, TResult>(
    this PatternMatcher<Tuple<<#= typeArguments #>>, TResult> pattern,
    for(int argumentIndex = 0; argumentIndex < cardinality; argumentIndex++)
    <#= string.Format(argumentsPatterns[argumentsPatternsCases[argumentIndex]], argumentIndex + 1) #>,
    <#= selectorArgument #>)

To understand what happens for the body of the method, the best is to look at the generated code for a particular sample :

public static PatternMatcher<Tuple<T1, T2>, TResult> Case<T1, T2, TResult>(
    this PatternMatcher<Tuple<T1, T2>, TResult> pattern,
    Expression<Func<T1, bool>> testExpression1,
    T2 testValue2,
    Expression<Func<T1, T2, TResult>> selector)
    ParameterExpression testParam = Expression.Parameter(typeof(Tuple<T1, T2>), "t");
    MemberInfo[] members = GetTupleMembers<T1, T2>();

    List<Expression> testExpressions = new List<Expression>();
            Expression.MakeMemberAccess(testParam, members[0])));
            Expression.MakeMemberAccess(testParam, members[1]),

    Expression aggregateExpression = testExpressions.CombineAll();

    var testExpression = Expression.Lambda<Func<Tuple<T1, T2>, bool>>(

    var selectorExpression = GetSelectorExpression<T1, T2, TResult>(selector, members);

    return new PatternMatcher<Tuple<T1, T2>, TResult>(
        new MatchCase<Tuple<T1, T2>, TResult>(

I’ve just extracted two methods here :

  • an extension method CombineAll that combines test expressions into a single one by aggregating them using AndAlso expressions :
private static Expression CombineAll(
    this IEnumerable<Expression> expressions)
    Expression aggregateExpression =
            (a, e) => a == null ? e : Expression.AndAlso(a, e));

    return aggregateExpression ?? Expression.Constant(true);
  • a GetSelectorExpression method, because the selector expression is generated exactly in the same way for each case number of a given cardinality.

The whole sample is available on my Github, including hand-crafted unit-tests for tuples of cardinality 2 and 3…

Posted in Functional Inspiration, Syntax Puzzles | Tagged , , , , | 2 Comments

Scala.io, seen by a .NET guy

As you might have noticed, I’m a .NET guy. I work on a Microsoft platform, with almost only Microsoft tools. But I happen to also be a functional programming fanboy now. My main interest is in F#, but I’m also curious about many other platforms…

Last year, I took Martin Odersky’s Scala course on coursera, and enjoyed it. I also watched the whole series of Haskell lectures by Erik Meijer on Channel9. And in a week, for my birthday, both of them offer me a new “Reactive programming in Scala” course on coursera!

With all this background, I went last week to Scala.io, a brand new conference in Paris, mostly about Scala, but also other functional languages. As a not-working-on-the-JVM guy, and not using Scala in my work, I was not focused on tools and practical uses of  Scala, but rather on getting ideas from a wide range of practices and languages, and interoperability in mind. As you’ll see, I chose a polyglot track.

I’ve attended several talks during the two days, but I won’t go into the details of each of these. All the videos should be available soon, so if any of these talks seem interesting to you, watch them!

Keynote day 1, Victor Klang

The opening keynote, given by Victor Klang, head of engineering at Typesafe, focused on the importance of failure, and the need to embrace validation and error handling as part of the software. He envisioned a world of micro-services, concurrent and compartmentalized, location transparent: typed endpoints producing typed streams of data. Of course, he insisted on the importance of type-safety…

ZeroMQ and Scala, François Armand

ZeroMQ is a reaction to Message Oriented Middlewares, and the AMQP protocol, which took ages to be specified. ZeroMQ is not a MOM, it is a socket library acting as a concurrency framework. Is is asynchronous and scalable, and has numerous languages integrations. For this reason, it is a convenient communication channel between heterogeneous systems. The talk presented several demos of different communication patterns, using both Scala (with or without Akka) and Python.

SPL: Scala Powered Lisp, Stefan Chris

This talk was about a project to parse and interpret a LISP is Scala. Its goal was to show how parser combinators could be used in Scala to build an AST, and how to build an interpreter and a REPL on top of it.

After a quick intro about Lisp, and sample expressions evaluated in a REPL, Stefan showed us the definitions of the basic data types of the language, and the Lisp AST he had built. In Scala, all the types were represented as case classes, that can be pattern-matched. After showing the basic constructs, he moved on to anonymous functions, bindings, and more complex expressions. Then came the interpreter, environment and closures.

Lazy on a Thursday afternoon

During the afternoon, I saw some Clojure (I wasn’t that impressed, I should see another more advanced talk some time), reified trees sent to the GPU, JVM Garbage Collection theory and tuning, and then came…

Brain damage with Haskell, Yves Parès

This talk was a general presentation about Haskell, accelerated. It was a very nice talk, first focusing on the non-strict evaluation model of Haskell, where the evaluation is in the hands of the programmer. Yves then showed us several standard functions, and… finally introduced the classical vocabulary of Haskell developers: functors, applicatives, monad. He finally presented several monads usage: IO monad, state monad.

And after some more Scala patterns, and a nice evening party with the attendees and speakers…

Keynote day 2, Sadek Drobi

This keynote was about web modern challenges, and the motivations behind the Play2 framework. To sum up, Play2 is about composability and functional programming toolset. This really seems to be a pretty nice framework.

Functional groovy, Guillaume Laforge

This was a very nice talk! I had never taken the time to look at Groovy, well this is now solved. Groovy is a superset of Java with APIs and toolset. It is a great fit for DSLs, and offers a seamless integration with Java. It has many functional characteristics: closures are first-class citizens, it supports genericity through duck-typing and operator overloading.

A very clever feature is the ability to write the last argument of a function, if it is a closure, after the closing parenthesis of the function call. This brings a very nice syntax. Groovy also supports transformations (macros), which allows to automatically add behaviors such a structural equality or memoization to existing code. It’s definitely worth a look.

Several other talks

I attended a talk about Gatling2, a stress test tool that builds a DSL on top of Scala, a talk about Scalaz and Shapeless, Nicolas Martignole talking about his experience working in a startup, and finally Fabrice Croiseaux talking about an app combining Scala, Akka and Backbone for a reactive web application. I have really enjoyed all these talks, but I won’t go into the details of each of these.

And a conclusion!

These two days were really nice, there are so many new things I want to learn now… I was already playing with parser combinators in F#, I only want to play with them even more. I am also going to look at structures such as HLists. And of course, reactive programming in Scala.

I really think that it is when we cross boundaries and go outside of our comfort zone that real useful exchanges are made. I had a good time at Scala.io and hope to be there again next year, maybe even doing a talk about F#!

Posted in Events, Functional Inspiration | Tagged , , , , , | Comments Off

Andy Murray as an event source

With Wimbledon’s final this weekend, I recalled that I had not blogged about the “Evil Tennis kata” I played with, a few months ago. Its aim was to compute a tennis score from a series of game events. This kata is inspired by the original tennis kata, but does not stop at the game level and computes the score for a whole match.

Let’s consider a tennis match. We can see it as a list of points, either won by player A or player B. For instance, here are the first points from Sunday’s final:

["Murray"; "Murray"; "Murray"; "Djokovic"; "Djokovic"; "Djokovic"; "Djokovic"; "Djokovic"; "Murray"; "Murray"; "Murray"; "Djokovic"; "Murray"; "Djokovic"; "Murray"; "Murray"; "Murray"; "Djokovic"; "Djokovic"; "Djokovic"; "Murray"; "Murray"; "Djokovic"; "Murray"; "Djokovic"; "Murray"; "Murray"; "Djokovic"; "Djokovic"… ]

One of the goals of the kata is to be able to determine the final score from the match events. It can also be to print nicely every score from the start until the end, like it is done for instance on the following page:

Once again, it has been a nice way to practice F#:

type Player = PlayerA | PlayerB
type GameEvent = Point of Player
type GameScore = GameScore of int * int
type SetScore = GameScore list
type Match = SetScore list

type Outcome =
    | Win of Player
    | Pending

I use a single union type to define the score of a game, composed of the number of points won by player A and the number of points won by player B. For instance, GameScore(3,1) means that the current game score is 40-15. Using classical integers to count the points is much easier than trying to reason directly in the tennis scoring system, which is seriously twisted. In order to display a classical score from this representation, here is the first function:

let displayGame (GameScore(a, b)) =
    let displayScore score =
        match score with
        | 0 -> "0"
        | 1 -> "15"
        | 2 -> "30"
        | 3 -> "40"
        | _ -> failwith "Invalid argument score"
    match a, b with
    | a, b when a <= 3 && b <= 3 -> sprintf "%s - %s" (displayScore a) (displayScore b)
    | a, b when a = b -> "Deuce"
    | a, b when a = b + 1 -> "Adv A"
    | a, b when a = b - 1 -> "Adv B"
    | a, b when a > b -> "Game A"
    | _ -> "Game B"

Now what we want is to be able to build a GameScore from a series of GameEvent. This can be achieved nicely with a function and a fold:

let updateGame (GameScore(a, b)) event =
    let newGame =
        match event with
        | Point(PlayerA) -> GameScore(a + 1, b)
        | Point(PlayerB) -> GameScore(a, b + 1)

|> Seq.fold updateGame (GameScore(0, 0)) 
|> displayGame

The previous sample code prints out the score : “40 – 15”.

When we try to go a step further, displaying the score of a particular game becomes less interesting. What we really want is to check the victory condition at the game level, in order to determine whether the next point will start a new game:

let getGameOutcome (GameScore(a, b)) =
    match (a, b) with
    | a, b when a > 3 && a > b + 1 -> Win(PlayerA)
    | a, b when b > 3 && a < b - 1 -> Win(PlayerB)
    | _ -> Pending

From there, we can build an updateSet method:

let updateSet previousSet event =
    match previousSet with
    | previousGame :: previousGames ->
        match getGameOutcome previousGame with
        | Win(_) -> updateGame (GameScore(0, 0)) event :: previousGame :: previousGames
        | Pending -> updateGame previousGame event :: previousGames
    | [] -> updateGame (GameScore(0, 0)) event :: []

Similarly, we need to determine at some point whether the set has been won. In order to do this we have to count the games won by each player. Here is how I did it:

let countWins games =
    let rec countWinsRec games (a, b) =
        match games with
        | game :: otherGames ->
            let wins =
                match getGameOutcome game with
                | Win(PlayerA) -> (a + 1, b)
                | Win(PlayerB) -> (a, b + 1)
                | _ -> (a, b)
            countWinsRec otherGames wins
        | _ -> (a, b)
    countWinsRec games (0, 0)

From there, we can determine whether a set is won:

let getSetOutcome (setScore:SetScore) =
    let (a, b) = countWins setScore
    match (a, b) with
    | a, b when a > 5 && a > b + 1 -> Win(PlayerA)
    | a, b when b > 5 && a < b - 1 -> Win(PlayerB)
    | _ -> Pending

The next step is to move to the match level:

let updateMatch previousMatch event =
    match previousMatch with
    | previousSet :: previousSets ->
        match getSetOutcome previousSet with
        | Win(_) -> updateSet [] event :: previousSet :: previousSets
        | Pending -> updateSet previousSet event :: previousSets
    | [] -> updateSet [] event :: []

Finally, we can use the updateMatch method in a fold to build a representation of the match:

let buildMatch events = List.fold updateMatch [] events

The result is a reversed list of reversed list of GameScores…

[[GameScore (6,8); GameScore (1,4); GameScore (2,4); GameScore (2,4);
  GameScore (4,1); GameScore (4,1); GameScore (4,2); GameScore (4,2);
  GameScore (0,4); GameScore (2,4)];
 [GameScore (0,4); GameScore (2,4); GameScore (2,4); GameScore (4,0);
  GameScore (5,7); GameScore (4,6); GameScore (1,4); GameScore (4,2);
  GameScore (4,1); GameScore (4,2); GameScore (3,5); GameScore (4,1)];
 [GameScore (0,4); GameScore (5,3); GameScore (5,7); GameScore (0,4);
  GameScore (0,4); GameScore (4,2); GameScore (4,1); GameScore (6,8);
  GameScore (1,4); GameScore (5,3)]]

That is not a very readable result… Here I go for a last function:

let displayMatchScore events = 
    let displaysWins (a, b) = sprintf "%i - %i" a b
    let displaySet games = displaysWins (countWins games)
    let rec getSetScoreToDisplay sets =
        match sets with
        | games :: [] ->
            match games with
            | game :: _ -> displaySet games :: []
            | _ -> displaySet games :: []
        | games :: otherSets -> displaySet games :: getSetScoreToDisplay otherSets
        | [] -> failwith "Error"
    getSetScoreToDisplay (buildMatch events |> List.rev)

This last one aggregates the events, in order to display a much more simple list of scores:

let score = displayMatchScore events

And the final score is displayed : ["4 - 6"; "5 - 7"; "4 - 6"] !

Posted in Events | Tagged , | Comments Off

Potter Kata – Going further – Not following the rule

Last time, I blogged about the Potter Kata, and I carefully followed the advice, which was to only do the minimum required work to pass the tests. This time, I’m going to break the rule and implement a generic solver for the problem, although it may have no practical interest whatsoever.

Let’s pretend that in the pricing rules applied last time, the discount percentages could change, depending on the mood of a very lunatic sales person. For instance, he (or she) might decide that on a particular day, we remove the discount on the pack of two books, and introduce a “buy 2, get 1 free” offer. The prices would then become:

1 book No discount 8.00 EUR
2 different books No discount 8.00 * 2 = 16.00 EUR
3 different books 3rd one free 8.00 * 2 + 0.00 * 1 = 16.00 EUR
4 different books 20% discount 8.00 * 4 *0.80 = 25.60 EUR
5 different books 25% discount 8.00 * 5 *0.75 = 30.00 EUR

Now, let’s examine the previous “edge-case” basket, composed of:

  • 2 copies of the first book
  • 2 copies of the second book
  • 2 copies of the third book
  • 1 copy of the fourth book
  • 1 copy of the fifth book

With the new pricing rules, the new best price is obtained by (5 * 8.0 * 0.75) + (2 * 8.00 + 1 * 0.00) and is 46.00 EUR. Here, the greedy algorithm is correct again, so we could just remove our adjustment rule from last time, isn’t it? Of course not! If we add one more book in the basket, the best price becomes… 3 * (2 * 8.00 + 1 * 0.00) = 48.00 EUR.

So how do we solve that ? Well, we could simply try a brute force solution, compute every single possible set of sets of books, price them, and take the cheapest option. But here we have an interesting property: every book has the same price. So evaluating [[1;2];[1;2];[3]] and [[1;2];[1;3];[2]] is exactly the same. When we consider books, we don’t really care about their individual number or title, but only about whether they are distinct from each other or not.

So here is my take on a solver algorithm. First, we take the books and organize them by types, sorted by ascending quantity:

let types = books |> Seq.countBy id |> Seq.map snd |> Seq.sort |> Seq.toList |> List.rev

This means that the following books [1;2;3;1;2;3;4;5] get transformed to the list [1;1;2;2;2], which means “a book that appears only once, then another one, then one that appears twice, then another one, and yet another one”.

From this representation, we can price the basket by splitting it into two simpler baskets, in several ways, price each combinations, and take the cheapest. To split the basket, we remove a single item of each kind of book, for the first n types. An example is worth a thousand words here:

From [1;1;2;2;2] we can get the following splittings:

  • [1] + [1;2;2;2]
  • [1;1] + [2;2;2]
  • [1;1;1] + [1;2;2]
  • [1;1;1;1] + [1;1;2]
  • [1;1;1;1,1] + [1;1;1]

The first half is always priced directly as there is never more than one book of each kind. The second half is priced recursively using the same principle.

The algorithm is the following:

let rec priceTypes priceBucket (types: int list) =
    let nbTypes = List.length types
    if nbTypes = 0 then 0.0M
        let allPrices = seq {
            for bucketSize = 1 to nbTypes do
                let bucketPrice = priceBucket bucketSize
                let remainingTypes =
                    |> Seq.mapi (fun i n -> if i < bucketSize then n - 1 else n)
                    |> Seq.filter (fun n -> n > 0)
                    |> Seq.sort |> Seq.toList |> List.rev

                yield bucketPrice + priceTypes priceBucket remainingTypes }
        allPrices |> Seq.min

There are many combinations. This will lead to long computations, even with a low number of books. But many of these computations will share some identical combinations, and they don’t need to be run several times. This is just what memoization is designed for. The principle is simple: when an idempotent function gets the same input twice, it must generate the same output. From there, if we can record the generated output the first time and associate it with the input, the next time we get this input we can directly return the recorded output.

A standard memoize function can then be defined:

let memoize f =
    let dict = Dictionary<_, _>()
    fun x ->
        match dict.TryGetValue(x) with
        | true, res -> res
        | false, _ -> 
            let res = f x
            dict.Add(x, res)

The things get a little more complicated when recursion is involved because in order to memoize effectively a recursive function, the function itself has to call its memoized version recursively (instead of itself). It gets even more complicated if you need the whole recursive thing to be tail-recursive. For now, hopefully, we don’t need that, because the tree of combinations that we try to build is quite wide, but not very deep.

My implementation of the memoized version is the following:

let rec priceTypes priceBucketFunc =
    let rec memoizedPriceTypes =
        let priceTypesRaw (types: int list) =
            let nbTypes = List.length types
            if nbTypes = 0 then 0.0M
                let allPrices = seq {
                    for bucketSize = 1 to nbTypes do
                        let bucketPrice = priceBucketFunc bucketSize
                        let remainingTypes =
                            |> Seq.mapi (fun i n -> if i < bucketSize then n - 1 else n)
                            |> Seq.filter (fun n -> n > 0)
                            |> Seq.sort |> Seq.toList |> List.rev

                        yield bucketPrice + memoizedPriceTypes remainingTypes }
                allPrices |> Seq.min
        memoize priceTypesRaw

We can now build a price function that takes a “priceBucket” function as an argument, and returns the actual pricing function:

let price priceBucketFunc books =
    let types = books |> Seq.countBy id |> Seq.map snd |> Seq.sort |> Seq.toList |> List.rev
    priceTypes priceBucketFunc types

The function can then be used this way:

let priceBucket = function | 1 -> 8.0M | 2 -> 16.0M | 3 -> 16.0M | 4 -> 25.6M
                           | 5 -> 30.0M | _ -> failwith "Really ? 6 books ?"
let price = PotterKataTooMuch.price priceBucket
price [1;1;2;2;3;3;4;5]

It works on small to medium lists of books (such as 50 books for instances). Let’s pretend the world is perfect, and that it’s enough for today!

The code from this post and the previous one is available on GitHub.

Posted in Events | Tagged , | Comments Off