This post is part of the F# Advent Calendar in English 2016 project. Check out all the other great posts there! And special thanks to Sergey Tihon for organizing this.

I’m very happy that F# is getting used more and more in my work place. It has even got to a point where some code has been written a while ago and maintenance is done by someone who hasn’t been involved in the project at all in the beginning. This has been an chance to work on a somewhat “legacy” F# code, which was the first time for me. The code on which we’ve worked had been written by someone who was a well-grounded C# dev, but not fluent in F#. Let’s say that the produced F# code is not very idiomatic. After going through this code, here is some advice I’d like to give to beginners.

Disclaimer: I’m talking about regular code here, there is no particular constraint on performance nor memory (this is not real-time nor high-frequency trading). We can afford to allocate memory and trigger GC collections. The advice given here may not be relevant to your specific use-case.

Type all the things

While gradually building something in F#, you’ll probably use tuples, because they’re so easy to use. And when writing a function, adding a new parameter is really easy, so of course you’ll do. However, if you keep doing that, you end up with code that’s difficult to maintain. The classical answer in a statically typed functional language for such a problem is “add more types”.

If you find yourself using:

1. tuples with too many items in it: use a type to name your items (a record for instance)
   
2. record types with too many properties: compose smaller types to group related properties
3. higher-order functions: define a type for each non-trivial function signature you consume or return
4. functions with too many arguments: group arguments with types (but still remember points 1 & 2)

Keep things simple

This applies to any language, and is not F# specific. However when some people start to “get” how F# works, they tend to over-complicate things, where they could have been kept simple. Don’t forget the common sense good practices that apply to other languages, just because you’re coding in F#. FSharpLint (available as part of F# Power Tools) is a tool that can help you with that. In particular, it enforces the use of:

• small functions
• even smaller lambdas
• small tuples only (4 items max, and I’d say 4 is already too much)

Piping

Piping is super cool. I acknowledge that. In my opinion, it allows you to easily express the “flow” of data through steps, and is very expressive. However that doesn’t mean you should go crazy with pipes.

Piping into 10 steps of complicated filters, grouping, and folds, is not as readable after 6 months as you thought it was when you were writing it. Comments could help, but defining steps in named variables, and composing them in the end, is very easy to do and will allow you to express the intent directly in the code.

Curried functions

Curried functions only make sense if you can do partial applications that also make sense. If your arguments don’t make any sense if they’re not provided together, they compose a single unit of meaningful data, and you should:

• either group those items in a tuple,
• or (most probably) define a type.

Higher-order functions

“Higher-order” means that at least one parameter of the function is going to be a function itself. Why not? Functions are first-class citizens. However, don’t try to be too smart. Remember, “Keep things simple”. Taking functions as parameter is one thing, but taking higher-order functions as parameters starts to become complicated. There can probably be cases where it makes sense, but don’t overuse it. And if you need to take functions as parameters, consider defining meaningful types for theses function signatures.

Explicit side-effects

F# is not a pure functional language, as it doesn’t prevent you from mutating state or having side-effects in your code. However, when you write a function that has side effects, make it as explicit as you can. Don’t hide a function that has side effects in the middle of a call chain, unless it is obvious from the caller standpoint that the call is intended to have side effects. F# type system will not prevent you from such things, so you’ll need a bit of discipline there.

Tests

Writing tests in F# is supposed to be easy. When you write tests, you shouldn’t have to build a big context for each test. If you’ve kept your types and functions simple, your unit tests will not have many dependencies or boilerplate setup. Composition is what functional programming is really about. As soon as your tests feels like wiring things up instead of validating your code behaviour, stand back and try to see if concerns can be separated.

Conventions & whitespaces

I do get that it’s not easy to choose a convention and stay consistent when you’re new to a language, but having a consistent convention regarding spaces makes your code much more pleasant to read (or maybe it’s just me and my OCD). Please do.

Dependencies

Switching to a new language doesn’t mean you should forget everything you’ve learned so far. For instance, the Single responsibility principle is still a good practice! You can think of a function signature as an interface with a single method on it. When you provide a function as a parameter, it’s like injecting the implementation of an interface. Whenever you do it, you should ask yourself whether you really want to inject it. “Do you want to inject a database access function there, or do you want to perform the call somewhere else and just pass in the returned data to the function?”. Every function parameter can be considered a dependency.

Write (or don’t, actually) your own DSLs, Computation expressions, and Type providers

Don’t do that in the first week! I’m totally guilty of using fun and cool features just because I think they’re amazing (and sometimes I want to show off), but try to get the basics right first…

• DSLs will only prove useful if they’re built on top of well-thought abstractions. Trying to build the DSL first, in order to have a user-friendly readable code, can also lead to overcomplicated implementation underneath.
• Computation expressions are just syntactic sugar over abstractions. You can probably achieve the same result without them. Try to get your types and concepts right before you find yourself trying to use the “MaintainsVariableSpaceUsingBind” property on a CustomOperationAttribute.
• Type providers (erased ones, at least) are usually also only syntactic sugar that helps ensure type-safety and convenience. Before writing your own, consider using a simpler approach (but it definitely can make sense to write your own, and if you ever need, you can ping me!)

The advice given here may seem too simplistic, but it can’t hurt, can it?

PS: Now I understand the imposter syndrome

Fortunately, F# has a feature called computation expressions, that can bring you back the joy of an unpredictable behaviour at runtime! I hope you’ll enjoy the ones I’m going to introduce today. For instance, they allow you to write the following code:

let theAnswer = usually { return 42 }
let basicArithmetic = mostProbably { return 6 * 7 }

As those samples clearly state, they usually and mostProbably behave as expected. However, they sometimes do slightly different things. Indeed, the computation expressions are sometimes mutated, and then evaluate to something else. Using this, you can cause subtle bugs, that only occur from time to time, deep inside more complex computations. And as you can expect, the debugging experience will be completely awful.

That’s a nice first step. But didn’t I mention cursing an praying? Stay tuned. Using a combination of custom operations and mutable state (ouch!), this is perfectly valid code:

pray God {
    // This begins a safe section
    ``The lord is my shepherd``
    let x = 6
    ``He led me in the paths of righteousness``
    // Here the safe section is over

    let y = 55

    // this is just another safe section
    ``Whoever walks in integrity walks securely``
    let z = 2
    ``But whoever takes crooked paths will be found out``
    // And here the safe section ends

    // This starts a perilous section
    ``I walk through the valley of the shadow of death``

    return (y * z + 1) * x
}

And it comes in different flavours, you can pray your own favourite god if you wish:

pray FlyingSpaghettiMonster {
    ``I believe Thou art the Creator of Goodness and Nourishment``
    let x = 1
    ``I believe that Thou are neither Male, nor Female``
    let y = 2
    ``I thank Thee for the giving of healthful Green Salad``
    let z = 3
    ``R'amen``
    return x + y - z
}

In the previous samples, you compose a prayer, that will change the mood of the god who listens to it:

• in the default state, there is a small chance that mutation occur in the expressions,
• when the god is pleased, the code is safe and no mutation occurs,
• when the god is angry, expect numerous mutations.

Of course, using a sentence which is not intended for the right god will trigger mutations.

So how do we build this? Computation expressions are in most cases just used as syntactic sugar that allows you to bind continuation functions to a given state (as very well explained on fsharpforfunandprofit). But you can also use computation expressions to get a quotation of the expression. This is what’s behind the cloud expression offered by MBrace.

Once given an expression, you can manipulate it to build a new derived expression. In the end, in order to evaluate the expression, I’ve used the evaluator packaged in Unquote. In the end, the computation expression builder class is almost empty:

type ChaosBuilder (mutationSitePicker:IMutationSitePicker,
                   expressionReplacer:IExpressionReplacer) =
    member this.Return(x) = x
    member this.Quote (expr) = expr
    member this.Run (expr:Expr<'T>) =
        let choaticExpr =
            mutate mutationSitePicker expressionReplacer expr
        choaticExpr.Eval<'T>()

The IMutationSitePicker is responsible for choosing a site, ant the IExpressionReplacer actually performs the expression maniputation. Here is a sample implementation that give every eligible expression a random chance to be replaced:

type MutateWithProbability(proportion) =
    let r = new System.Random()
    let mutable lastRandom = r.NextDouble()
    interface IMutationSitePicker with
       member this.PickNextSite = lastRandom < proportion
       member this.NotifyIgnoredSite() = lastRandom <- r.NextDouble()
       member this.NotifyMutation() = lastRandom <- r.NextDouble()

I’m not going to include the actual expression manipulation code here, but my current work on this very valuable feature is available as a Gist. Implementing computation expressions which allow (and encourage) cursing is left as an exercise to the reader.

Some of the code used here could actually be used to perform mutation testing. the only replacement implemented so far is numeric constants mutation, but there are many other kinds of fun mutations to add (see Mutation Testing of Functional Programming Languages for instance) such as “replacing an arithmetic, relational, logical, bitwise logical […] operator by another of the same class”, “Reordering Pattern Matching”, and even “Type-aware Function Replacement”.

As a conclusion, I want to say that even if I often abuse computation expressions to do stupid things, they’re a really powerful feature of the F# language and really allow to write cool DSLs.

EDIT: I’ve implemented the arithmetic operator replacement in the train this morning, the gist has been updated.

This post is part of the F# Advent Calendar in English 2015 project. Check out all the other great posts there! And special thanks to Sergey Tihon for organizing this.

A few weeks ago, while at BuildStuff, I walked next to an image built with words, like a tag cloud picturing some company’s logo. My first reaction was: “That looks nice, but has someone been paid to manually placed all these words? I bet it can be automated…”

I started putting together a script, in order to fill an image with words. My first attempt had disastrous performance and memory characteristics. Several hours of work later (quite a few, actually), and with contributions from my co-workers, we ended-up with a much better algorithm.

F# is a wonderful language to experiment with ideas. The convenience of quickly defining types with almost no ceremony lets you focus on what you’re really trying to build. The power of the .NET ecosystem lets you use all the standard APIs that you expect to find on a serious platform. This is really enjoyable and helps you to build simple things first, and evolve to more complicated ones while staying focused.

In the end we’re able to produce images such as:

In order to produce such an image, we need an image to use as the model, and a list of words to fill the shape with. We had much fun doing it, both trying to identify strategies to make the images look good and get the generation time down. You can find the full source code on Github: https://github.com/pirrmann/Wordz

The goal: build a nice picture

Another area where F# shines is related to getting data from various sources and manipulate it. This enables so many scenarios. What if we could get pictures, and related text, from some place such as https://sergeytihon.wordpress.com/2015/10/25/f-advent-calendar-in-english-2015/ for instance, and generate all sorts of images?

Step 1: parse the the posts list

I’m happy @TeaDrivenDev hasn’t published his first post idea about generating the RSS feed from the FsAdvent page, because I also have to parse the page in order to get my data… so first thing, we need to get the posts URLs from the page. It gives me a chance to mention the HTML Type Provider, which is part of the FSharp.Data library. Accessing the list of posts and downloading all the posts is as easy as:

type adventCalendarPage =
    HtmlProvider<"https://sergeytihon.wordpress.com/[...]/">
type PageRow =
    adventCalendarPage.FAdventCalendarInEnglish2015.Row

let postsTable =
    adventCalendarPage
        .GetSample()
        .Tables
        .``F# Advent Calendar in English 2015``

let extractPostsLinks (tr:HtmlNode) =
    let lastTd = tr.Elements("td") |> Seq.last

    lastTd.Elements("a")
    |> List.map (fun a -> a.AttributeValue("href"))

let postLinks =
    postsTable.Html.Descendants("tr")
    |> Seq.tail
    |> Seq.map extractPostLinks

let downloadPostsAsync links = 
    links
    |> Seq.map HtmlDocument.AsyncLoad
    |> Async.Parallel

let postsDownloads =
    postLinks
    |> Seq.map downloadPostsAsync
    |> Async.Parallel
    |> Async.RunSynchronously

let allPosts = Array.zip postsTable.Rows postsDownloads

From the previous sample, you may notice how the HTML type provider also allows you to access the elements of the page through the DOM. This is quite representative of how a good library design gracefully lets you use the underlying technology when the high-level API doesn’t suit your needs.

Step 2: extract words

We have now obtained all published FsAdvent posts in the form of HtmlDocument objects, but we don’t have their content yet… No magic type provider here, all posts are hosted on different blogging platforms, I had to use several strategies and fallbacks to identify the HTML element containing the post in each case. Semantic web is really not there yet! The search function finally looks like this:

let search =
    findDivWithEntryClassUnderDivWithPostClass
    |> fallback findWintellectContent
    |> fallback findDivWithClassStoryContent
    |> fallback findArticle
    |> fallback findElementWithClassOrIdPost
    |> fallback findH1TitleParentWithEnoughContent
    |> fallback findScottwContent
    |> fallback findMediumContent
    |> fallback wholePageContent

The next step of interest is how to extract the most important words from each post. Another handy feature of F# are computation expressions, and in particular the built-in ones such as async an seq. Returning a sequence while recursively traversing a tree is as easy as:

let getMultiplier (node:HtmlNode) =
    match node.Name() with
    | "h1" -> 16 | "h2" -> 12 | "h3" -> 8
    | "h4" -> 4  | "h5" -> 3  | "h6" -> 2
    | _ -> 1

let rec collectAllWords multiplier (node:HtmlNode) = seq {
    match node.Elements() with
    | [] ->
        let text = node.InnerText()
        let words =
            text.Split(delimiters)
            |> Seq.filter (not << String.IsNullOrWhiteSpace)
            |> Seq.filter (fun s -> s.Length > 1)
            |> Seq.map (fun s -> s.ToLowerInvariant())
        for word in words do
            if not(filteredWords.Contains word) then
                yield word, multiplier

    | children ->
        let multiplier' = getMultiplier node
        yield! children
               |> Seq.collect (collectAllWords multiplier')
}

The last step once we’ve obtained all the words from each post with is to group them and sum their weight in order to get an indicator of their importance in the post. We define a function for that:

let sumWeights words =
    words
    |> Seq.groupBy fst
    |> Seq.map (fun (word, weights) -> word,
                                       weights |> Seq.sumBy snd)
    |> Seq.sortByDescending snd
    |> Seq.take 100
    |> Seq.toList

Step 3: get Twitter profile pictures

So we have all words from the FsAdvent posts published so far, and their relative importance in each post. But in order to create a visualization, we need model images, right? Let’s download the Twitter profile pictures of the authors! The profile urls can be extracted from the FsAdvent page (actually some of them are not links to twitter, so I had to cheat a bit, and this is why the function extractCleanLink is omitted…)

let extractProfileLink (tr:HtmlNode) =
    let lastTd = tr.Elements("td") |> Seq.item 1
    let a = lastTd.Elements("a") |> Seq.head
    a.InnerText(), a.AttributeValue("href")

let profilesLinks =
    postsTable.Html.Descendants("tr")
    |> Seq.tail
    |> Seq.map extractProfileLink

let downloadAndSavePictureAsync (name:string, twitterProfileUrl:string) = async {
    let fileName = getFileName "profiles" name

    let cookieContainer = new Net.CookieContainer()

    let! twitterProfileString = Http.AsyncRequestString(twitterProfileUrl,
                                                        cookieContainer = cookieContainer)
    let twitterProfile = HtmlDocument.Parse(twitterProfileString)

    let profileImageLink =
        twitterProfile.Descendants("a")
        |> Seq.find(fun a -> a.HasClass("ProfileAvatar-container"))
            
    let profilePictureUrl = profileImageLink.AttributeValue("href")

    let! imageStream = Http.AsyncRequestStream profilePictureUrl

    use image = Image.FromStream(imageStream.ResponseStream)
    image.Save(fileName, Imaging.ImageFormat.Png)

    return () }

profilesLinks
|> Seq.map (extractCleanLink >> downloadAndSavePictureAsync)
|> Async.Parallel
|> Async.RunSynchronously
|> ignore

Step 4: cut the profile pictures into layers

My early experiments with this did not have any feature to cut pictures into layers, but I didn’t want to manually edit each picture profile! So what I’ve done to build “layers” is just to cluster pixels by color similarity (actually I’ve tried to really cluster them with a K-means cluster but I ended up using my custom clustering with magic numbers, as it performs better on that specific set of pictures).

This topic could be a blog post of its own so I’ll just sum up the steps I’ve performed:

• In order to get rid of outliers, first blur the image
• then generate color clusters using the following algorithm:
  • considering each pixel, if it’s close enough (below a given threshold) to an existing cluster, put it in the cluster. If too far from any existing cluster, create a new cluster with the single pixel in it.
  • after having seen each pixel, merge clusters that are close enough
  • finally, merge clusters that are too small with their nearest neighbour, regardless of the distance

This way, we can go from one image to several ones with the grouped pixels:

Step 5: fill images with words

As some authors have decided to blog more that once, I’ve decided to merge their posts and generate a single image per author.

let mergePosts posts =
    let allImportantWords =
        posts
        |> Seq.collect (fun post -> post.Words)
        |> Seq.toList
    { Seq.head posts with Words = sumWeights allImportantWords }

let mergedPosts =
    parsePosts allPosts
    |> Seq.groupBy (fun post -> post.Author)
    |> Seq.map(fun (_, posts) -> mergePosts posts)
    |> Seq.toArray

Using sumWeights to merge posts is like considering that each post is a paragraph containing only its 100 most important words.

I then consider each layer generated previously from the Twitter profile picture of an author, and fill it with the most important words from his/her posts. This generates one file per layer on the disk.

Step 6: generate the calendar!

So… 62 posts (before the last one) – 2 which were not published – 1 because I decided to group Steffen’s posts (even if scheduled on 2 different dates) + 1 because Steffen’s post have been unmerged (as I neeeded 60 posts in the end) = 60 posts (yeah!). This gives me a nice 8 * 8 square, with a 2 * 2 tile in the middle for the F# foundation! All is needed is to iterate on the generates layers filled with words, and place them on the calendar. I’ve randomly shuffled the posts list, can you identify everybody? Here is the result, enjoy!

(click on the calendar to view the full size image)

I’ve just updated this post with all posts written so far…

Let’s start from the start: my goal was to design some way for me to explain my daughter what programming is about and how it works. There are some nice graphical tools for that, like Scratch or more recently Hour of code, however I wanted to show something which is closer to what I actually do on a daily basis: write (and read) code. There are some nice educational programming languages, some of them are even usable in a localized way (French, in my case). LOGO is a good example of this, and I could have used an existing tool, but where is the fun if you don’t build your own?

It appears that building an internal LOGO-like DSL is surprisingly easy, and requires almost no code! What you need is just to define the basic types to describe your actions:

type Distance_Unit = STEPS
type Rotation_Unit = GRADATIONS
type Rotation_Direction = | LEFT | RIGHT
let STEP = STEPS
let GRADATION = GRADATIONS

type Color = | RED | GREEN | BLUE

type Action =
    | Walk of int * Distance_Unit
    | Turn of int * Rotation_Unit * Rotation_Direction
    | LiftPenUp
    | PutPenDown
    | PickColor of Color

type Turtle = Action seq

And then a computation expression to do the trick of transforming sentences to sequences of actions:

type AS_word = AS
type TO_word = TO
type THE_word = THE
type PEN_word = PEN
type UP_word = UP
type DOWN_word = DOWN
type TIMES_word = TIMES
type WHAT_word = WHAT
type DOES_word = DOES

type TurtleBuilder() =
    member x.Yield(()) = Seq.empty
    [<CustomOperation("WALK", MaintainsVariableSpace = true)>]
    member x.Walk(source:Turtle, nb, unit:Distance_Unit) =
        Seq.append source [Walk(nb, unit)]
    [<CustomOperation("TURN", MaintainsVariableSpace = true)>]
    member x.Turn(source:Turtle, nb, unit:Rotation_Unit, to_word:TO_word,
                  the_word:THE_word, direction:Rotation_Direction) =
        Seq.append source [Turn(nb, unit, direction)]
    [<CustomOperation("LIFT", MaintainsVariableSpace = true)>]
    member x.LiftPenUp(source:Turtle, the_word:THE_word, pen_word:PEN_word,
                       up_word:UP_word) =
        Seq.append source [LiftPenUp]
    [<CustomOperation("PUT", MaintainsVariableSpace = true)>]
    member x.PutPenDown(source:Turtle, the_word:THE_word, pen_word:PEN_word,
                        down_word:DOWN_word) =
        Seq.append source [PutPenDown]
    [<CustomOperation("PICK", MaintainsVariableSpace = true)>]
    member x.PickColor(source:Turtle, the_word:THE_word, color:Color, pen_word:PEN_word) =
        Seq.append source [PickColor color]
    [<CustomOperation("DO", MaintainsVariableSpace = true)>]
    member x.Do(source:Turtle, as_word:AS_word, turtle:Turtle) =
        Seq.append source turtle
    [<CustomOperation("REPEAT", MaintainsVariableSpace = true)>]
    member x.Repeat(source:Turtle, nb:int, times_word:TIMES_word, what_word:WHAT_word,
                    turtle:Turtle, does_word:DOES_word) =
        Seq.append source (List.replicate nb turtle |> Seq.collect id)

let turtle = new TurtleBuilder()

And with nothing more, you can now write this kind of plain English instructions:

turtle {
    LIFT THE PEN UP
    WALK 4 STEPS
    TURN 3 GRADATIONS TO THE RIGHT
    PICK THE GREEN PEN
    PUT THE PEN DOWN
    WALK 4 STEPS }

Now, this doesn’t solve my initial problem, I want a French DSL. But I just need to define another builder, and a few translation functions:

type Tortue = Turtle

type Unite_De_Distance = PAS with
    member x.enAnglais = match x with | PAS -> STEP

type Unite_De_Rotation = | CRANS with
    member x.enAnglais = match x with | CRANS -> GRADATION
let CRAN = CRANS

type Sens_De_Rotation = | GAUCHE | DROITE with
    member x.enAnglais = match x with
                         | GAUCHE -> LEFT
                         | DROITE -> RIGHT

type Couleur = | ROUGE | VERT | BLEU with
    member x.enAnglais = match x with
                         | ROUGE -> RED
                         | VERT -> GREEN
                         | BLEU -> BLUE

type Mot_A = A
type Mot_DE = DE
type Mot_LE = LE
type Mot_STYLO = STYLO
type Mot_COMME = COMME
type Mot_FOIS = FOIS
type Mot_CE = CE
type Mot_QUE = QUE
type Mot_FAIT = FAIT

type TortueBuilder() =
    member x.Yield(()) = Seq.empty
    member x.For(_) = Seq.empty
    [<CustomOperation("AVANCE", MaintainsVariableSpace = true)>]
    member x.Avance(source:Tortue, de:Mot_DE, nb, unite:Unite_De_Distance) =
        Seq.append source [Walk(nb, unite.enAnglais)]
    [<CustomOperation("TOURNE", MaintainsVariableSpace = true)>]
    member x.Tourne(source:Tortue, de:Mot_DE, nb, unite:Unite_De_Rotation,
                    a:Mot_A, sens:Sens_De_Rotation) =
        Seq.append source [Turn(nb, unite.enAnglais, sens.enAnglais)]
    [<CustomOperation("LEVE", MaintainsVariableSpace = true)>]
    member x.Leve(source:Tortue, le:Mot_LE, stylo:Mot_STYLO) =
        Seq.append source [LiftPenUp]
    [<CustomOperation("POSE", MaintainsVariableSpace = true)>]
    member x.Pose(source:Tortue, le:Mot_LE, stylo:Mot_STYLO) =
        Seq.append source [PutPenDown]
    [<CustomOperation("PRENDS", MaintainsVariableSpace = true)>]
    member x.Prends(source:Tortue, le:Mot_LE, stylo:Mot_STYLO, couleur:Couleur) =
        Seq.append source [PickColor couleur.enAnglais]
    [<CustomOperation("FAIS", MaintainsVariableSpace = true)>]
    member x.Fais(source:Tortue, comme:Mot_COMME, tortue:Tortue) =
        Seq.append source tortue
    [<CustomOperation("REPETE", MaintainsVariableSpace = true)>]
    member x.Repete(source:Tortue, nb:int, fois:Mot_FOIS, ce:Mot_CE, que:Mot_QUE,
                    tortue:Tortue, fait:Mot_FAIT) =
        Seq.append source (List.replicate nb tortue |> Seq.collect id)

let tortue = new TortueBuilder()

And I can write my instructions in French!

tortue {
    AVANCE DE 5 PAS
    TOURNE DE 6 CRANS A DROITE
    AVANCE DE 5 PAS
    TOURNE DE 6 CRANS A DROITE
    AVANCE DE 5 PAS
    TOURNE DE 6 CRANS A DROITE
    AVANCE DE 10 PAS }

The next steps involved:

• Writing a Windows Forms client to actually see the turtle draw things
• Making it possible to send actions to the turtle using FSI
• Hand-coding every letter of the alphabet
• Adding a new keyword to my turtle builders

And please welcome my “Hello world” sample:

turtle {
    WRITE "MR T. SAYS:\nHELLO WORLD!\n\n"
}

As usual, all the code is available on my github.

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!

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 3ⁿ 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(
    "Expression<Func<",
    typeArguments,
    ", TResult>> selector");

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

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

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;
    argumentIndex++)
{
    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>();
    testExpressions.Add(
        Expression.Invoke(
            testExpression1,
            Expression.MakeMemberAccess(testParam, members[0])));
    testExpressions.Add(
        Expression.Equal(
            Expression.MakeMemberAccess(testParam, members[1]),
            Expression.Constant(testValue2)));

    Expression aggregateExpression = testExpressions.CombineAll();

    var testExpression = Expression.Lambda<Func<Tuple<T1, T2>, bool>>(
        aggregateExpression,
        testParam);

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

    return new PatternMatcher<Tuple<T1, T2>, TResult>(
        pattern,
        new MatchCase<Tuple<T1, T2>, TResult>(
            testExpression,
            selectorExpression));
}

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 =
        expressions.Aggregate(
            (Expression)null,
            (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…

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#!

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:
http://www.flashscore.com/match/SSmzQE8d/#point-by-point;1

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)
    newGame

[Point(PlayerA);Point(PlayerA);Point(PlayerB);Point(PlayerA)]
|> 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"] !

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:

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
    else
        let allPrices = seq {
            for bucketSize = 1 to nbTypes do
                let bucketPrice = priceBucket bucketSize
                let remainingTypes =
                    types
                    |> 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)
            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
            else
                let allPrices = seq {
                    for bucketSize = 1 to nbTypes do
                        let bucketPrice = priceBucketFunc bucketSize
                        let remainingTypes =
                            types
                            |> 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
    memoizedPriceTypes

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.

Yesterday evening I was running Arolla’s Code Jam, and I suggested that we practice on the Potter Kata. This kata is a tricky one, which seems pretty simple at first, but shows its challenges after a few minutes, and it is very easy to get it wrong. In order to prepare the Jam and improve my level in F#, I practiced the kata this week, and I wanted to share my thoughts about it.

You can read the original problem description on codingdojo.org. I’ll just recap the pricing rules here for reference:

The rules are then followed by some clues:

You’ll find that this Kata is easy at the start. You can get going with tests for baskets of 0 books, 1 book, 2 identical books, 2 different books… and it is not too difficult to work in small steps and gradually introduce complexity.

However, the twist becomes apparent when you sit down and work out how much you think the sample basket above should cost. It isn’t 5*8*0.75+3*8*0.90. It is in fact 4*8*0.8+4*8*0.8. So the trick with this Kata is not that the acceptance test you’ve been given is wrong. The trick is that you have to write some code that is intelligent enough to notice that two sets of four books is cheaper than a set of five and a set of three.

You will have to introduce a certain amount of clever optimization algorithm. But not too much! This problem does not require a fully-fledged general purpose optimizer. Try to solve just this problem well in order to share it. Trust that you can generalize and improve your solution if and when new requirements come along.

It is clear here that the goal of this kata is not to write a general-purpose solver. I must agree that a general-purpose solver is not the best solution to the problem, as most probably You Aren’t Gonna Need It.

So I first tackled the kata, trying to do the bare minimum required to handle the requirements. In F#, my implementation goes down to 20 lines of code. The trick is that a greedy grouping of books (the “most intuitive” solution) is correct, except for the corner case where a group of 5 five books and a group of 3 books is actually more expensive than two groups of 4 books.

Disclaimer: I’m going to show an implementation of the kata here. If you’ve never tried it before, I suggest that you practice on your own first, because the solution in itself is really not as valuable as the path to get there.

I’ll use some of the test cases provided in the original kata, plus the ones we came up with last night. In F#, I get these kinds of tests:

[<TestMethod>]
member x.``1 book (each kind)`` () = 
    Assert.AreEqual(8.0M, price [1])
    Assert.AreEqual(8.0M, price [2])
    Assert.AreEqual(8.0M, price [3])
    Assert.AreEqual(8.0M, price [4])
    Assert.AreEqual(8.0M, price [5])

[<TestMethod>]
member x.``2 same books`` () = 
    Assert.AreEqual(16.0M, price [1;1])
    Assert.AreEqual(24.0M, price [2;2;2])

[<TestMethod>]
member x.``2 distinct books`` () = 
    Assert.AreEqual(15.2M, price [1;2])

[<TestMethod>]
member x.``3 distinct books`` () = 
    Assert.AreEqual(21.6M, price [1;2;3])

[<TestMethod>]
member x.``4 distinct books`` () = 
    Assert.AreEqual(25.6M, price [1;2;3;4])

[<TestMethod>]
member x.``5 distinct books`` () = 
    Assert.AreEqual(30.0M, price [1;2;3;4;5])

[<TestMethod>]
member x.``Simple discount`` () = 
    Assert.AreEqual(29.6M, price [1;2;1;3])

If we read the test cases carefully, nothing forces us to have a notion of “discount” in our implementation. In fact, pricing a group of distinct books is almost a single-liner:

let priceGroup = function | 1 -> 8.0M | 2 -> 15.2M | 3 -> 21.6M
                          | 4 -> 25.6M | 5 -> 30.0M | _ -> failwith "What ? A 6th book ?"

Now, this obviously doesn’t work when we try to buy the same book more than once. In order to consume the previously defined function, we have to build groups of books. A greedy grouping seems accurate at first:

let greedyGroup books = 
    // we count how many books there are of each type and sort them
    let types = books |> Seq.countBy id |> Seq.map snd |> Seq.sort |> Seq.toList
    // then we recursively compute how many groups of books we can build
    let rec countGroups types used =
        match types with
        | [] -> []
        | head :: tail -> head - used :: countGroups tail head
    countGroups types 0 |> List.rev

I’m pretty happy with function. The first expression get en ordered list from the books: a list of books [1;1;2;2;3;4] produces a list of of types of books [1;1;2;2], that can be read as “a type with a single book, a type with a single book, a type with 2 books, a type with 2 books”. The recursive function counts how many groups of distinct books can be built from these type. Here, the output is [0;1;0;1] which means “0 group of 1 books, 1 group of 2 books, 0 group of 3 books, 1 group of 4 books”.

Now, we combine our functions into a price function:

let price books =
    books
    |> greedyGroup
    |> Seq.mapi (fun i nb -> priceGroup (i+1) * decimal nb)
    |> Seq.sum

We’re almost there. This code is incorrect for the edge case we identified before. But do we have to break everything and build a general-purpose solver? No. We just have to handle the edge case and adjust the grouping:

let adjust = function 
    | [a; b; c; d; e] ->
        let shift = min c e
        [a; b; c-shift; d+2*shift; e-shift]
    | l -> l

Basically, this adjust function replaces every pair of 5 distinct books and 3 distinct books by a 2 groups of 4 distinct books, which are cheaper.

Finally, the pricing function with the adjustment becomes:

let price books =
    books
    |> greedyGroup
    |> adjust
    |> Seq.mapi (fun i nb -> priceGroup (i+1) * decimal nb)
    |> Seq.sum

And that’s done.

Bonus: F# brings you such a nice type inference that without changing any line in my previous code, I can use the book titles instead of their numbers (or anything that has equality comparison!).

let test_generic_1 = price ["Harry Potter and the Philosopher's Stone";
                            "Harry Potter and the Chamber of Secrets";
                            "Harry Potter and the Prisoner of Azkaban";
                            "Harry goes to Hollywood";
                            "Harry Rabienkirira - ledernier"]

let test_generic_2 = price [typedefof<System.Collections.ArrayList>;
                            typedefof<System.String>;
                            typedefof<System.Int32>]

Of course, building a general purpose solver for the same problem is too appealing to be ignored. That will be the subject of the next post, featuring tail-recursion and memoization!

(For those of you who wonder where the “Pattern-matching” series has gone, it’s coming back soon)

This month, the kata was about printing user-supplied pictures:

• of any size (in pixels),
• in a given format (10×13 cm, 11×13 cm, 13x15cm, 15×18 cm, 18×24 cm…)
• with a given filling mode (“full-paper” or “full-image”)

The printer always prints at 300 dots-per-inch, so the images must be resized in order to fit in the available printing space.

The expected output data, needed for printing the images, would be:

• the output printer (13 cm width or 18 cm width printer),
• the rotation applied to the picture (0° or 90°, the direction doesn’t matter),
• the expansion/reduction ratio to apply to the picture,
• the position where the picture must be drawn.

The kata’s description also involved some drawings in order to explain the meaning of the filling modes. There was, for instance, a picture of Winston Churchill. Unfortunately, there was not a single kitten picture. I fixed this, in order to provide samples illustrating the two filling modes.

Here is a train picture in full-image mode:

The same picture in full-paper mode, where the red areas will be cropped at printing:

And the same with the kitten, full-image:

And full-paper, with the cropped areas in red:

The exercise chosen by Damien for this kata is really an interesting one, as it is in fact quite simple, but there are many ways to misunderstand it and make it more complicated than it really is. Although we were not so many coders, there were several different techniques, problems and outcomes:

• some people paired, some worked alone,
• some worked in TDD, some didn’t (but we all wrote tests!),
• some of us didn’t consider the print format as an input but rather as an output (trying to determine the most appropriate format for a given picture),
• some of us took much time trying to define data types, and in the end had not enough time to handle the core business problem of the image resizing,
• some others (amongst the C# devs) used dynamic types for prototyping, so they were able to write the logic first, rather than focusing on the types.

As to myself, I had come to this breakfast with the goal to code in F#, so this is what I’ve done. I paired with Peter Even, who I hope is now addicted to F#! In order to focus on the core problem, we stated that:

• selecting the good output printer given the print format is trivial,
• selecting whether or not we must rotate is not very complicated (although we could get it wrong),
• the ratio computation is the tricky part.

Here is what we came up with (with the French words translated) for the ratio computation. First the unit tests:

[<TestClass>]
type UnitTest() = 
    [<TestMethod>]
    member x.``A 2.54*2.54cm square is 300*300 pixels`` () = 
        let converted = (2.54, 2.54) |> toPixels
        Assert.AreEqual((300.0, 300.0), converted)
        
    [<TestMethod>]
    member x.``Winston churchill in 18*24cm full-image`` () = 
        let ratio = getResizeRatio (664, 1000) (18.0, 24.0) FullImage
        Assert.AreEqual(18.0 * 300.0 / 2.54 / 664.0, ratio)

    [<TestMethod>]
    member x.``Winston churchill in 18*24cm full-paper`` () = 
        let ratio = getResizeRatio (664, 1000) (18.0, 24.0) FullPaper
        Assert.AreEqual(24.0 * 300.0 / 2.54 / 1000.0, ratio)

And here is the implementation:

type Mode =
    | FullImage
    | FullPaper

let toPixels (x, y) =
    (x * 300.0 / 2.54, y * 300.0 / 2.54)

let getResizeRatio (photoHeight, photoWidth) (formatHeight, formatWidth) mode  =
    let (photoHeight, photoWidth) = (float photoHeight, float photoWidth)
    let (paperWidth, paperHeight) = toPixels (formatWidth, formatHeight)

    let photoRatio = photoWidth / photoHeight
    let formatRatio = formatWidth / formatHeight

    let isPhotoWider = photoRatio > formatRatio

    match (isPhotoWider, mode) with
    | (true, FullImage) | (false, FullPaper) -> paperWidth / photoWidth
    | (false, FullImage) | (true, FullPaper) -> paperHeight / photoHeight

Jérémie Chassaing, who also worked in F#, had a more engineered solution where he:

• determines, from the filling-mode, which operator to use in order to compare the ratios,
• performs the comparison with the operator and determines from that which side of the image must be used to get the correct ratio (but the return type here is directly a function, where a less-functional approach would have returned a boolean for instance),
• uses the resulting function to extract the length and compute the ratio.

It sounds more complicated (to my mind it is, in fact), but I still find that beautiful from a functional perspective!

While writing this blog post, I could not resist the will to go further and investigate the other parts of the problem, because I so much wanted to be able to pipe my functions! In the end, the assumptions we made during the kata were not wrong, but reasoning about the position where the image must be drawn is not as simple as I first thought!

Finally, here is my code:

let printers = [ 13.0; 18.0 ]

let findPrinter (formatShortSide, formatLongSide) =
    let printerWidth = printers |> List.tryFind (fun w -> w = formatShortSide || w = formatLongSide)
    Option.bind (fun w -> Some(w, w = formatShortSide)) printerWidth

let getResizeRatio (photoShortSide, photoLongSide) (frameShortSide, frameLongSide) mode  =
    let isPhotoRatioHigher = (photoLongSide / photoShortSide) > (frameLongSide / frameShortSide)
    match (isPhotoRatioHigher, mode) with
    | (true, FullImage) | (false, FullPaper) -> frameLongSide / photoLongSide
    | (false, FullImage) | (true, FullPaper) -> frameShortSide / photoShortSide

let getPrintData (photoWidth, photoHeight) (formatShortSide, formatLongSide) mode =
    let printer = findPrinter (formatShortSide, formatLongSide)
    match printer with
    | Some(printerWidth, withFormatRotation) ->
        let (withPhotoRotationInFrame, photoShortSide, photoLongSide) =
            if photoHeight > photoWidth
                then (true, float photoWidth, float photoHeight)
                else (false, float photoHeight, float photoWidth)
        
        let (frameLongSide, frameShortSide) = (formatLongSide, formatShortSide) |> toPixels

        let ratio = getResizeRatio (photoShortSide, photoLongSide) (frameShortSide, frameLongSide) mode

        let xInFrame = (frameLongSide - photoLongSide * ratio) / 2.0
        let yInFrame = (frameShortSide - photoShortSide * ratio) / 2.0

        let (x, y) = if withFormatRotation
                        then (yInFrame, xInFrame)
                        else (xInFrame, yInFrame)

        let withRotation = withFormatRotation <> withPhotoRotationInFrame

        Some(printerWidth, (x, y) |> toCentimeters, withRotation)

    | None -> None

Notes: the images used in the samples are under a creative commons license, and can be found at http://commons.wikimedia.org/wiki/File:Antigo_Tren_Old_Train._Santiago_de_Compostela.jpg and  http://commons.wikimedia.org/wiki/File:Red_Kitten_01.jpg.

What makes the pattern-matching mechanism so powerful in functional languages is its ability to match many sorts of data structures, amongst which are tuples.

Defining a match expression on a tuple or 2 values in F# can be done this way :

let result =
    match input with
    | 1, 1 -> 1
    | 2, _ -> 2
    | _, 3 -> 3
    | a, b when a > 4 -> 4
    | _ -> 5

This sample shows some interesting cases. A tuple of 2 values can be matched with several expressions, each value of the tuple being compared with individual patterns.

In part 1 of this series, we stated these individual patterns:

• a constant pattern,
• a conditional pattern,
• a default pattern, known as the wildcard pattern (the underscore in F#).

Now, we have to handle every possible combination of these patterns!

The following sample translated in C# in my experimental syntax is the following:

var tupleSample =
    PatternMatcher.CreateSwitch<int, int, int>()
    .Case(1         , 1, (a, b) => 1)
    .Case(2         , _, (a, b) => 2)
    .Case(_         , 3, (a, b) => 3)
    .Case(a => a > 4, _, (a, b) => 4)
    .Case(_         , _, (a, b) => 5);

Welcome to the parenthesis hell. Soon it will like like Lisp if we go on… But how do we enable that syntax ?

In order to handle gracefully the wildcard (“_”) pattern, I have used a non-generic MatchCase class with a static field called Any:

public class MatchCase
{
    public static readonly MatchCase Any;

    static MatchCase()
    {
        Any = new MatchCase();
    }

    private MatchCase()
    {
    }
}

This trick allows me to define methods with a MatchCase-typed parameter to handle the wildcard pattern case. Moreover, if I add the following line before my patterns definitions :

var _ = MatchCase.Any;

I’m then able to use a simple “_” to represent the “any” case.

The method used previously to build the pattern matching Func and its invocation in the Eval method doesn’t change: only the “recording” process is impacted. The pain point here is that we need to define each necessary overload of the Case extension method, in order to handle all the patterns. These extensions methods are all based on the following model:

public static PatternMatcher<Tuple<T1, T2>, TResult>
    Case<T1, T2, TResult>(
    this PatternMatcher<Tuple<T1, T2>, TResult> pattern,
    {arg1},
    {arg2},
    Expression<Func<T1, T2, TResult>> selector)

where the {arg1} and {arg2} placeholders are replaced with :

• T1 testValue1, T2 testValue2
• T1 testValue1, Expression<Func<T2, bool>> testExpression2
• T1 testValue1, MatchCase any2
• Expression<Func<T1, bool>> testExpression1, T2 testValue2
• Expression<Func<T1, bool>> testExpression1, Expression<Func<T2, bool>> testExpression2
• Expression<Func<T1, bool>> testExpression1, MatchCase any2
• MatchCase any1, T2 testValue2
• MatchCase any1, Expression<Func<T2, bool>> testExpression2
• MatchCase any1, MatchCase any2

The implementation of each method follows the same pattern as in the previous post, and builds an expression that determines whether a given tuple matches the pattern, returning, and evaluates the selector expression when there is a match.

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

In order to handle match expressions where none of the expressions would match a given candidate, I decided to use an option type. This allows the generation of this type of expressions:

Func<double, Option<double>> matchSomeOrNone =
    (double d) =>
        (d > 0.0)
        ? Option<double>.Some(d)
        : Option<double>.None();

Given this these options, the translation of last time’s sample code:

var stringPattern = PatternMatcher
    .CreateSwitch<string, double>()
    .Case("TEST"                        , s => Math.PI)
    .Case("TEST_1"                      , s => Math.E)
    .Case((string)null                  , s => 0.0)
    .Case(s => s.StartsWith("TEST__")   , s => Math.E * 2)
    .CaseElse(                            s => s.Length);

would become:

Func<string, Option<double>> generatedFuncOption =
    (string s) =>
        (s == "TEST")
            ? Option<double>.Some(Math.PI)
            : (s == "TEST_1")
                ? Option<double>.Some(Math.E)
                : (s == null)
                    ? Option<double>.Some(0.0)
                    : s.StartsWith("TEST__")
                        ? Option<double>.Some(Math.E * 2)
                        : Option<double>.Some(s.Length);

In order to instantiate option types in LINQ expressions, I have to use the corresponding MethodInfo instances, obtained from reflexion :

MethodInfo createSomeMethodInfo =
    typeof(Option<TResult>)
        .GetMethod(
            "Some",
            BindingFlags.Public | BindingFlags.Static);

MethodInfo createNoneMethodInfo =
    typeof(Option<TResult>)
        .GetMethod(
            "None",
            BindingFlags.Public | BindingFlags.Static);

And then, in order to finally build a matching expression, I loop over the match conditions and result selector expressions the following way:

private Func<TSource, Option<TResult>> BuildPatternMatchingFunc()
{
    ParameterExpression parameter =
        Expression.Parameter(typeof(TSource));

    Expression noneExpression = Expression.Call(
        createNoneMethodInfo);

    Expression caseExpression = noneExpression;

    foreach (var matchCase in this.cases.Reverse())
    {
        caseExpression =
            Expression.Condition(
                Expression.Invoke(
                    matchCase.TestExpression,
                    parameter),
                Expression.Call(
                    createSomeMethodInfo,
                    Expression.Invoke(
                        matchCase.SelectorExpression,
                        parameter)),
                caseExpression);
    }

    return Expression
        .Lambda<Func<TSource, Option<TResult>>>(
            caseExpression,
            parameter)
        .Compile();
}

The createNoneMethodInfo and createSomeMethodInfo are the MethodInfo corresponding to the generic Option<T>.None() and Option<T>.Some() methods obtained by reflection.

Debugging this kind of expression building can be complicated, particularly without the ability to visualize clearly the expression tree… Hopefully, I have built an expression tree visualizer in the past (I could also have used the easy path and install the classical one) ! From the C# sample again, I can produce the following expression tree:

This tree may seem wide, but is is just a succession of conditional expressions… Finally, the the function that evaluates the result of the pattern-matching expression is the following one:

public TResult Eval(TSource candidate)
{
    if (this.patternMatchingFunc == null)
    {
        this.patternMatchingFunc = BuildPatternMatchingFunc();
    }

    Option<TResult> matchResult = patternMatchingFunc
                                    .Invoke(candidate);

    if (!matchResult.IsSome)
        throw new NoMatchFoundException();

    return matchResult.Value;
}

As you can see, it’s a wrapper around the expression evaluation invocation. It first generates the expression  instantiates upon the first call (in a non-threadsafe way, but who cares !) and handles “nothing matches” case by throwing an exception. And this works !

Now, you might say that matching a single value in of very limited interest. I can’t deny it. Why don’t we try to match several values, then ?

let test str =
    match str with
    | "TEST" -> Math.PI
    | "TEST_1" -> Math.E
    | null -> 0.0
    | s when s.StartsWith("TEST__") -> Math.E * 2.0
    | s -> float s.Length

If we analyse these patterns, we see 3 different cases:

• a constant pattern (including the null value),
• a conditional pattern (the lambda one)
• a default pattern (the else case).

So in C#, what I’ve managed to build is the following:

var stringPattern = PatternMatcher
.CreateSwitch<string, double>()
.Case("TEST"                        , s => Math.PI)
.Case("TEST_1"                      , s => Math.E)
.Case((string)null                  , s => 0.0)
.Case(s => s.StartsWith("TEST__")   , s => Math.E * 2)
.CaseElse(                            s => s.Length);

What is difficult here is to write something that is valid C#, because:

1. I can’t change the compiler,
2. To keep things simple, I don’t want to use Roslyn in the first attempt (although that might come later).

Recording expressions for individual tests

This solution is mainly based upon a generic class called PatternMatcher<TSource, TResult>, which represents the match expression being built. Each Case overload builds an instance of a MatchCase class. As with many “fluent” syntax nowadays, in order to chain the calls in a single statement, each Case overload returns a new instance of the PatternMatcher, which keeps track of all the cases registered so far.

The MatchCase’s sole purpose is to encapsulate two expressions:

• a test expression that will be used to determine if a particular source value matches the case: this will be an expression of Func<TSource, bool>,
• a selector expression that will be used to produce the result of the match expression when the input value matches this particular case: this will be an expression of Func<TSource, TResult>.

Getting an Expression of a given Func type is nothing more that changing the type of a variable. The compiler will change its work accordingly, and produce an Expression from a given lambda-expression, instead of a typed delegate.

The most general case is the conditional pattern. Let’s take a look at the following extension method:

public static PatternMatcher<TSource, TResult>
    Case<TSource, TResult>(
        this PatternMatcher<TSource, TResult> pattern,
        Expression<Func<TSource, bool>> testExpression,
        Expression<Func<TSource, TResult>> selector)

You can see that the testExpression and selector parameters are already the types that my MatchCase class needs. From this values, I just have to instantiate the class and store it for later use.

The two other  cases (constant and default) will also provide directly the selector expression, only the test expression will have to be provided:

• as an expression that tests equality with a given constant, for the constant pattern,
• as an expression that is always true, for the default pattern.

These cases are just special cases of the previous one, called with an appropriate lambda, which will be converted to the test expression.

Building an expression tree

Of course, what we want to do is more that just record the expressions ! The next step is to combine them in a global match expression.

The kind of code I would like to produce, for the previous sample, would be the following:

Func<string, double> generatedFunc =
(string s) =>
    {
        if (s == "TEST") return Math.PI;
        if (s == "TEST_1") return Math.E;
        if (s == null) return 0.0;
        if (s.StartsWith("TEST__")) return Math.E * 2;
        return s.Length;
    };

Or even “better”, the same, but with conditional expressions instead of if and return statements:

Func<string, double> generatedFuncNoIf =
    (string s) =>
        (s == "TEST")
            ? Math.PI
            : (s == "TEST_1")
                ? Math.E
                : (s == null)
                    ? 0.0
                    : s.StartsWith("TEST__")
                        ? Math.E * 2
                        : s.Length;

An expression corresponding to the previous code could be generated, but I also want to handle an additional case: when there is no match. This means that my expression has to be able to return some result or… none. Some or none ? Isn’t there a type for that ? We’ll see how to use it next time.

[1] I know this sample is useless and theoretical, but isn’t this whole series ? If you really want to use match expressions, embrace F#, not C# !

What is pattern matching ?

From the MSDN entry on Pattern matching :

Patterns are rules for transforming input data. They are used throughout the F# language to compare data with a logical structure or structures, decompose data into constituent parts, or extract information from data in various ways.

The point I want to focus on is in fact the F# match expression. The match expression is a powerful way to express conditions over data. It is often described as a “switch statement on steroids”. Its characteristics are the following :

• Just like a switch, it takes a value as its input,
• Unlike a switch, the value is not limited only to enums or built-in value types.
• It has a return type. If there is nothing to return, F# uses a special unit type, but there is no void as a return type neither a null value.
• If the values to return can be of different types depending on the input, Discriminated Unions (DUs) can be used as return types.

I’ll start with a simple F# sample, to show what a discriminated union is :

type Shape =
    | Point
    | Circle of float
    | Rectangle of float * float

In this sample, a type Shape is defined, that can be either a Point, a Circle or a Rectangle. Although the Point could be considered a simple enum value, the Circle and Rectangle cases, unlike enums, carry data. For instance :

let p = Point
let c = Circle(5.0)
let r = Rectangle(10.0, 20.0)

If we want to extract the data components of a particular union type, we use pattern-matching in the following way :

let Rectangle(w, h) = r

This expression binds the value of w and h to the data elements of the r Rectangle defined earlier. But my purpose in the blog series is to introduce in C# a syntax that would look like a match expression, which in F# is the following :

let getArea s =
    match s with
    | Point -> 0.0
    | Circle(r) -> r * r * System.Math.PI
    | Rectangle(w, h) -> w * h

In this attempt, I first consider matching simple values (which has no practical interest of any sort), then matching tuples, and I’ll finish with matching against some sort of Discriminated Union, although DUs are not a native C# construct.

First, let’s consider what we want to build. From the sample above, we can see that what we get from the match expression is a “getArea” that takes an instance of the union type as input, and gives a float as output. As this is just the definition of a function, it looks like we’re trying to build a construct that generates instances of the generic Func<TInput, TOutput> delegate.

In F#, match expressions can also be used to perform actions, and in this case will return the special unit type. To perform actions in C# we have the Action<T> delegate type. In this series I’ll consider only the functions, but actions could be built exactly the same way.

In the next part, I’ll show my first naive attempt to deal with simple values, before targeting any tuples or discriminated union types.