Navigate / search

F# and Databases Part Deux (Parameters)

This entry is part 2 of 2 in the series F# and Databases

In the last post I showed a handful of lines of code that allowed us to query a database and map the results to a record type in a really simple way. One limitation was that while it could run any SQL query we wanted, it couldn’t handle parameters, and we don’t want to include parameter values directly in the SQL.

Fortunately we can add handling for parameters very easily and learn a few things about F# along the way. Here’s the code from the last post:

module SQLiteLoader
    open System.Data
    open System.Data.SQLite
    let Query (connectionString: string) toType (sql: string) = 
      seq { use cn = new SQLiteConnection(connectionString)
            let cmd = new SQLiteCommand(sql, cn) 
            cmd.CommandType<-CommandType.Text

            cn.Open()
            use reader = cmd.ExecuteReader()
            while reader.Read() do
                yield reader |> toType
         }

And we can call it as follows:

    let ProductLoader = Query @"Data Source=SkuMaker.db3;Version=3;" ToProduct 
    let products = ProductLoader "SELECT * FROM products"   

How can we fit parameters into this setup? What would the ideal solution look like. Perhaps something like this:

    let queryText = "SELECT id, description FROM products where id >= :minId AND id <= :maxId"            
    let parameters = [("minId" min); ("maxId" max)]

    ProductLoader queryText parameters    

We simply create a List of Tuples. Each Tuple represents a name value pair of parameter and value. It could hardly be simpler. Unfortunately it won’t work. When we have a list of Tuples the type or signature of each Tuple in the list must be the same. In the example above we’re in good shape, it’s a list of string*int tuples. But what about the following

    let queryText = "SELECT id, description FROM products where id = :Id AND description = :Description"            
    let parameters = [("Id" 4); ("Description" "Super Dooper Widget")]
    ProductLoader queryText parameters    

To paraphrase a famous quote, One does not simply put a string*int tuple in the same list as a string*string tuple. So, we’re screwed.

Of course, we could commit the henious crime of mentioning the word Object in the context of a functional language. F# is still a .Net language after all, and it’s ‘obj’ type is equivalent to ‘Object’ in C#. Any value we would want to use as a parameter value can ultimately be boxed into an ‘obj’. So we can use a list of string*obj tuples to get the job done. We can do this:

    let queryText = "SELECT id, description FROM products WHERE id = :id AND description = :Description"            
    let parameters = [("Id", box 4); ("Description", box "Super Widget")]
    ProductLoader queryText parameters

It’s not bad, We could definitely work with this as a solution. In C# I’d be delighted to be able to magic up a list of tuples this easily, but this is F# and we can take things a little further. Let’s see if we can get rid of the parenthesis, and maybe that word box. We could write a function that produces a tuple whie boxing the second element in the tuple:

    let param name value =
        (name, box value)

Now our query can be rewritten as:

    let queryText = "SELECT id, description FROM products WHERE id = :id AND description = :Description"            
    let parameters = [param "Id" 4; param "Description" "Super Widget"]
    ProductLoader queryText parameters

It’s important to note that our parameters list still has exactly the same type, it is a list of string*obj tuples. But instead of explicitely creating the tuples inline, we use a function to create them instead. The ‘param “Id” 4’ syntax almost reads like we’ve created a statement in a mini language. This is immensly powerful stuff. Your brain should be spinning with all the potential for creating more literate code without going through the whole process of writing Domain Specific Languages.

The code for our Loader module, including new code for actually using the parameters, now looks like this:

module SQLiteLoader
    open System.Data
    open System.Data.SQLite

    let param name value =
        (name, box value)
        
    let MapParameter (p:(string*obj)) =
        SQLiteParameter(fst p, snd p)

    let Query (connectionString: string) toType (sql: string) (parameters: (string*obj) list)= 
      seq { use cn = new SQLiteConnection(connectionString)
            let cmd = new SQLiteCommand(sql, cn) 
            cmd.CommandType<-CommandType.Text
        
            let SQLiteParams = List.map MapParameter parameters
            List.iter (fun p->cmd.Parameters.Add(p) |> ignore) SQLiteParams

            cn.Open()
            use reader = cmd.ExecuteReader()
            while  reader.Read() do
                yield reader |> toType
         }

Modifying this for another database like Oracle is a trivial exercise.

F# and Databases

This entry is part 1 of 2 in the series F# and Databases

Here’s an F# function that takes a connection string, a SQL query, and wedged between them a function that
can convert the results from a DataReader to a Sequence of suitable typed records. Even if you’re unfamiliar with
F# this code should look familiar, it’s straightforward ADO.Net

module SQLiteLoader
    open System.Data
    open System.Data.SQLite
        
    let Query (connectionString: string) toType (sql: string) = 
      seq { use cn = new SQLiteConnection(connectionString)
            let cmd = new SQLiteCommand(sql, cn) 
            cmd.CommandType<-CommandType.Text
        
            cn.Open()
            use reader = cmd.ExecuteReader()
            while reader.Read() do
                yield reader |> toType
         }

Let’s look at that ‘toType’ function more closely. I have a type called Category with two properties, and I have a function ‘ToCategory’ that takes a SQLiteDataReader and sets the properties of a Category. The ‘ToCategory’ function, or another very like it will be passed to the Query function above when the time comes.

module Categories

    open System.Data.SQLite
    open SQLiteLoader

    type Category =
        { 
            Code: string
            Description: string    
        }

    let ToCategory (reader: SQLiteDataReader ) =
        { 
            Code = unbox(reader.["Code"])
            Description = unbox(reader.["Description"])
        }    

Don’t worry about that unbox function. If you come from a C# or VB.Net background you may know about boxing and unboxing, or, more likely, you know of it, but don’t usually give it much of a thought. C# and VB.Net allow from implicit type conversions so boxing and unboxing usually just works. In F# all type conversions must be explicit. This can catch you by surprise because in F# Type inference is such an impressive feature it’s a bit of a jolt to be caught out by a casting issue. In this case unbox is just casting the value in the reader (an obj) to the desired type.

OK, the stage is set, we have a query that can load data from the data base, we have a type that we’d like that data mapped to, and we have a function to do the mapping. Time to have some fun.

open System
open SQLiteLoader
open Categories

let Display category =
    printfn "%s - %s" category.Code category.Description

[<EntryPoint>]
let main argv = 
    let categories = Query @"Data Source=SkuMaker.db3;Version=3;" ToCategory "Select * from Categories"
    Seq.iter Display categories
    Console.ReadKey() |> ignore;
    0

Getting our categories is just a matter of calling Query and giving it a connection string, our mapping function and a sql query.

Passing the connection string every time we want to query the database is going to get a bit tiresome. Let’s see if we can avoid doing that.

[<EntryPoint>]
let main argv = 
    let Loader = Query @"Data Source=SkuMaker.db3;Version=3;"
    let categories = Loader ToCategory "SELECT * FROM Categories"    
    
    Seq.iter Display categories
    Console.ReadKey() |> ignore;
    0

That’s better, we create a new function Loader which is a partial execution of Query. We’ve used Currying to lock in the connection string. Now we can use Loader in place of Query and it will work exactly the same way, except we’ve eliminated the need to keep passing in a connection string.

This is pretty cool. We have a function that knows where our Database is, and we just need to give it a mapping function and a sql query and it will return a suitably mapped sequence of results.

We can go further.

Taking Loader as our starting point we can use partial execution (currying) again to lock in the ToCategory mapping function and create a new function CategoryLoader that knows about both the connection string and the mapping to categories. This new function just needs to be passed a sql string.

[<EntryPoint>]
let main argv = 
    let Loader = Query @"Data Source=SkuMaker.db3;Version=3;"    
    let CategoryLoader = Loader ToCategory   
    let categories = CategoryLoader "SELECT * FROM Categories"    
    
    Seq.iter Display categories
    Console.ReadKey() |> ignore;
    0

We can use Loader to create loaders for other ‘Types’ and we can use CategoryLoader for different queries that load categories. And we can even create different Mapping functions if we want different representations of a Category.

I’m not really interested in investing any time in creating some all encompassing Data Wrapper for F#, I’ve been down that road in C# and it’s just heartache and struggle and code that ends up more complicated than it needs to be.

In the example above you can see that F# allows us to quickly and easily spin up code that just works, is light weight enough that writing it shouldn’t be a huge burden.

The joy of this is that as we find limitations or better ways of doing things we can simply start doing things differently for situations where it works. We’re not left trying to shoehorn whatever problem we have into the Framework we’ve shackled ourselves to.

Learning to think Functionally: Memoization

This entry is part 8 of 11 in the series Learning to think Functionally

Imagine you have a long running function that you’d like to avoid running unnecessarily. For the purposes of this post you’ll have to suspend disbelief and pretend that negating a number is an expensive task. This example prints out a message so you can see when it actually gets called.

let Negate n =
    printfn "Negating '%A' this is hard work" n
    -n

val Negate : int -> int

> Negate 5;;
Negating '5' this is hard work
val it : int = -5

Now, let’s use that function when writing another. This function takes two numbers, negates the first, then adds the second.

let addNegatedValue x y =
    let n = Negate x
    n + y

val addNegatedValue : int -> int -> int

> addNegatedValue 2 3;;
Negating '2' this is hard work
val it : int = 1

If you call this function repeatedly the telltale message lets you know that the expensive negation function is called every time. We’d like to avoid that.

Perhaps currying can help. Let’s create a curried version of ‘addNegatedValue’ and see what happens.

let negateTwoThenAdd = addNegatedValue 2

val negateTwoThenAdd : (int -> int)

> negateTwoThenAdd 3;;
Negating '2' this is hard work
val it : int = 1
> negateTwoThenAdd 3;;
Negating '2' this is hard work
val it : int = 1

This gives us a new function with the first argument (2 in this case) locked in, so we can call it passing only the 3 (or whatever other number we want to add to -2).

Unfortunately, as you can see above, when you use the curried function ‘negateTwoThenAdd’ a second time, it runs the negation code again. This makes sense. Currying locks in the argument 2 not the result of negating it. It doesn’t and shouldn’t get involved in optimizing out any lines of code in the function.

We need to explicitely ‘cache’ the negated value to avoid recalculating it.

let cachedAddNegatedValue x =
    let n = Negate x
    fun y -> n + y

val cachedAddNegatedValue : int -> (int -> int)

let cachedNegateTwoThenAdd = cachedAddNegatedValue 2

Negating '2' this is hard work

val cachedNegateTwoThenAdd : (int -> int)

This time the Negation function fires when we create the curried version of the function. Of course it does, look at the code, it’s right there. Negate x then return a function.

We now have a handle ‘cachedNegateTwoThenAdd’ to that returned function. All that function does is accept another value and add ‘n’ (the result of negating ‘x’) to it.

> cachedNegateTwoThenAdd 3;;
val it : int = 1

Bingo. We can call this all day and it will add any number we want to -2 without needing to rerun the ‘expensive’ negation operation.

I don’t want to gloss over the significance of this function being able to access ‘n’. It’s not passed as an argument, it’s just there, in scope, available. This is what’s known as a closure and it’s kind of a big deal as we’ll see shortly.

Before we take this code any further, let’s divert slightly to talk about closures and mutability. We’ve seen that ‘cachedNegateTwoThenAdd’ can access the variable ‘n’, however it can’t modify that variable. Even if you flag the variable as mutable. This code isn’t valid.

let addAndRememberTotal =
    let mutable n = 0
    fun x -> 
        n <- x + n
        n

In fact if a variable is flagged as mutable you can’t use it at all in a closure, even if you only read it.

let addAndRememberTotal =
    let mutable n = 0
    fun x -> x + n

Sorry for that little diversion, but mutability and closures are important for the rest of this post.

Where were we?

We have a solution that allows us to lock in a specific result of the expensive operation, we can then use that as many times as we want without needing to run the negate function again. That’s fine in so far as it goes, but it would be nice if we could cache the result for more than one input.

We should be able to throw all sorts of values at a function and have it cache return values so that subsequent calls for the same input don’t require another call to negate.

To do this, we can’t simply use a single cached value like an int. We need something that maps inputs to computed outputs. The snag is this cache needs to be mutable because every time we get a new input we want to compute an answer for it and store it in the cache. But, we just showed that closures can’t access mutable variables.

Except…they can…sort of. We can rope in some old mavericks, guys who don’t play by the rules, guys who eat mutability for breakfast.

Take a look at this little function for a clue to where this is heading.

let rememberTheEvens =
    let theList = List<int>()
    fun n ->
        if n%2 = 0 then theList.Add(n)
        theList 

It’s a closure, but it’s calling the ‘Add’ method on a List. The List in this case is a .Net System.Collections.Generic List. We’re changing the state of the List by adding items to it, but from the perspective of F# it’s still the same list, the mutability is hidden behind a reference to the list, and that’s good enough for F# to get off our backs about it.

Once you realise you can do this it’s a short hop to the following code.

let memoizedNegation =
    let cache = Dictionary<int,int>()
    fun x ->
        if cache.ContainsKey(x) then
            cache.[x]
        else
            let res = Negate x
            cache.[x] <- res
            res

This might look a little complicated but odds are you’ve written code just like this at some point. At it’s heart this is just a function that uses a dictionary to cache the return values keyed by the input values. For a given value the “expensive” function should only need to be called once. Subsequent calls for the same value can use the cached value.

The quirk here is that this is a closure, this function creates the cache then returns a different function that uses that cache. If you’ve followed everything I’ve written above this should be easy enough to grasp.

All this boilerplate code just to add caching to the ‘Negate’ function hardly seems worthwhile. There has to be a better way.

Of course there is. This is where the notion of functions as first class citizens really comes into it’s own. The following code is where this whole post has been heading all along, and it’s lifted directly from this post by Don Syme

Take a look at this code. Play a little spot the difference between this and the ‘memoizedNegation’ function above.

let memoize f =
    let cache = Dictionary<_, _>()
    fun x ->
        if cache.ContainsKey(x) then 
			cache.[x]
        else 
			let res = f x
            cache.[x] <- res
            res

This function takes an argument f, the previous function specifically executed the ‘Negate’ function, this one executes ‘f’ whatever ‘f’ is. So, we can use this to add caching to any function. The other big difference is that we don’t limit the dictionary to ints, both the key and value are generics.

Other than those two differences, it’s basically the same function.

Here are two simple examples of the memoize function in action. Again, these are trivial examples that aren’t worth the effort, they just illustrate how to use the general ‘memoize’ function.

let increment n =
        printfn "Adding 1 to '%A'" n
        n + 1

let mIncrement =
    memoize (fun n -> increment n)

let add x y =
        printfn "Adding '%A' to '%A'" x y
        x + y

let mAdd =
    memoize (fun x y -> add x y)

There’s one interesting problem with memoization and that is it’s behaviour on recursive functions. Take a look at the following naive recursive implementation of the factorial function. If we memoize it and try to get the factorial of 5 we see that the factorials of 4, 3, 2, 1 and 0 must be calculated. Trying to get the factorial of 5 again gives the result immediately because it’s cached. However the factorials of the lower numbers are not cached. If you try to get the factorial of 4 it must be calculated.

let rec fact x =        
    printfn "Getting factorial of '%A'" x
    if x < 1 then 1
    else x * fact (x - 1)

let mfact = memoize (fun n -> fact n)

> mfact 5;;
Getting factorial of '5'
Getting factorial of '4'
Getting factorial of '3'
Getting factorial of '2'
Getting factorial of '1'
Getting factorial of '0'
val it : int = 120
> mfact 5;;
val it : int = 120

I’ll leave this here as a little exercise. Figuring out why the lower values are not cached is fairly trivial, figuring out what to do about it is a bit more of a challenge. Perhaps that’s a topic for the next post.

Learning To Think Functionally: Back To Basics

I’m going back to some of the fundamentals of F# here, functions and arguments.

How many arguments does this function take?

let add x y =
    x + y

If you said two then you might like to watch this before continuing.

http://www.youtube.com/watch?v=CUn7zy8Ya20

At first glance (particularly if you are an old imperative kinda coder like me) this function clearly takes two arguments and returns the result of adding them together. In reality ‘add’ only takes one argument, just like every other function in F#. The point of this post is to explore this and a few other quirks of functions.

Let’s back up and look at a function that actually only takes one argument, to see what that looks like.

let numToText (n:int) =
    n.ToString()

I’ve specified that the input is an int, for reasons that will become apparent. The function also doesn’t do anything apart from convert the int to a string. All I care about here is the signature of the function, which is as follows.

val numToText : int -> string
                    ^^

The key part of the signature is the ‘->’ indicated. This tells us that we’re dealing with a function that turns an int into a string.

What happens if we don’t specify that the type of the input is int?

val numToText : 'a -> string

OK, F# still knows the function will result in a string, but it doesn’t know what the input is, so ‘a acts as a placeholder, it means, this function takes
in ‘something’, we don’t know what it is, but we know this function will produce a string based on it.

What should be the signature of a function that takes two arguments, adds them together and returns the result?
It turns out it has the following signature.

val add : int -> int -> int

What’s going on here? Shouldn’t there only be one -> with two arguments on the left (the inputs) and one on the right (the output).

Let’s break this down and look at the input and the output for that first ->.

int -> int -> int
    ^^

Looking to the left of the -> we see that we have one input (an int).
The output of the function is represented by everything to the right of the ->, in this case the output is

int -> int

In other words, the output is itself a function. One that takes in an int an returns an int.

We wrote the code, you’d think we’d remember returning a function, but, memory be damned, there it is in black and white.

We actually can replicate in code what F# is doing here.

let add x =
    fun y -> x + y

Now it’s clear. If you try out this code you’ll find it has exactly the same signature as the original add function.

int -> int -> int

The function accepts an int and returns a function that adds that int to another. F# in order to enforce the notion that functions can only accept one argument has automagically converted the original add function to something akin to this version.

We don’t have a function that takes two inputs, we have two functions that take one input each. This is very very important. It’s what makes currying possible, and understanding it is crucial to understanding how F# code fits together.

For an example of the kind of trouble you can get yourself into if you don’t really know what you’re doing, you need look no further than my last post.

We can check that the add function takes in an int and returns a function, by simply calling it

let addFive = add 5
val addFive : (int -> int)

There you go. The result of calling add with a single integer argument, is a function that itself takes an int and returns an int.
Here’s one to try for yourself. What would the signature of this function be?

let Foo (x:int) (y:float) =
    "Bar"

Once you’re happy that you understand it’s signature, try calling the function passing it just an int.

So, what are the implications of all of this? What difference does it make if functions only accept one argument?

To answer that let’s look at another example. What does this code do?

List.map (fun n -> n * 2) nums

The List.map function appears to take two arguments, a function that tells us what to do to each item in a list, and the list that we want to apply that function to. But, we know better than to think that List.map really takes two arguments. No function takes more than one argument. Not even the cool ones like List.map.

The signature of List This .map is as follows

(('a -> 'b) -> 'a list -> 'b list)
            ^^

The ‘a -> ‘b is in parenthesis so it is the single input to the function indicated. The output is a function that takes a list of type ‘a and turns it into a list of type ‘b. Think about that again. List.map does not apply a function to a list. What List.map does is return a function that applies a function to a list.

We can see this in action in the following code.

let nums = [1..10]
let doubleUp = List.map (fun n -> n * 2)
 
val nums : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9; 10]
val doubleUp : (int list -> int list)

> doubleUp nums;;
val it : int list = [2; 4; 6; 8; 10; 12; 14; 16; 18; 20]

List.Map takes one argument (a function) and returns a function that can be used to transform a list. This is exactly as we would expect. Whether it’s worthwhile using currying to create a function depends on the situation, but whether you use currying or not, the reality is that functions in F# to not receive more than one argument.

Let’s look at a few more functions, and plug some of them functions together

let evensAGoGo = List.filter (fun n -> n%2 = 0)
let oddsAPalooza = List.filter (fun n -> n%2 <> 0)
let doubleUp = List.map (fun n -> n * 2)

let doubleAllTheOddNumbers nums =
    nums
    |> oddsAPalooza
    |> doubleUp

The doubleAllTheOddNumbers function could also be written like this

let doubleAllTheOddNumbers nums =
    nums
    |> List.filter (fun n -> n%2 <> 0)
    |> List.map (fun n -> n * 2)

But, it’s arguably not as neat.

Let’s look at another impact of this one argument rule.

let multipleArgs x y z =
    (1 * x) + (2 * y) + (3 * z)

let pipeInAnArg n = 
    n |> multipleArgs 0 0

> pipeInAnArg 10;;
val it : int = 30

The first time I saw the Pipe Forward operator ‘|>’ I thought, “Oh, I see, it sets the last argument of the method being called”

The code above seems to confirm that, the first two args of multipleArgs are set to 0. When n (i.e. 10) is piped in it is treated as the third argument z, and is multiplied by 3.

This is all nonsense of course, n is not piped into the last argument of multipleArgs, it’s piped into the only argument of the function returned by multipleArgs when it’s called with values for x and y of 0.

We can rewrite this code as follows for a little more clarity

let multipleArgs x y z =
    (1 * x) + (2 * y) + (3 * z)

let gimmeAZeee =
    multipleArgs 0 0

let pipeInAnArg n = 
    n
    |> gimmeAZeee


val multipleArgs : int -> int -> int -> int
val gimmeSomeZeee : (int -> int)
val pipeInAnArg : int -> int

> pipeInAnArg 10;;
val it : int = 30

I’ll stop here. I decided to write this up for the simple reason that I glossed over it when I first looked at F#, it’s tempting if you have a bit of programming experience to take a quick look at functions in F# and think “ok, that I understand” and then move on to more interesting things. There’s a reasonable chance that doing that will slow you down later on.

Learning To Think Functionally – Stuck

This entry is part 7 of 11 in the series Learning to think Functionally

When you learn a new language there’s a phenomenon that happens fairly frequently which is you get it into your head that something “should” work. So you just try it.

There are two possible outcomes.

It may work, in which case you fall a little more in love with the language.

or

It doesn’t work, and you feel a little like you asked somebody to dance and they kind of made a face and carried on talking to their friends.

F# just snubbed me. Everything was going well, I had written the following:

let IsDivisibleBy divisor value =
    value % divisor = 0

let IsFizz = IsDivisibleBy 3
let IsBuzz = IsDivisibleBy 5
let IsFizzBuzz n = IsFizz n && IsBuzz n

let ToFizzBuzzValue x =
    match x with
    | n when IsFizzBuzz n -> "FizzBuzz"
    | n when IsFizz n -> "Fizz"
    | n when IsBuzz n -> "Buzz"
    | n -> n.ToString()

let FizzBuzz first last =
    [first..last]
    |> List.map (ToFizzBuzzValue)

Standard FizzBuzzy goodness. I was particularly pleased with using curried functions for IsFizz and IsBuzz. I still think the pattern matching code is a little clunky, but that’s not todays problem.

I wanted to add a new requirement. Expand the definition of Fizz to also include numbers that contain the digit 3 (e.g. 13), and Buzz to include numbers that contain the digit 5 (e.g. 51), and FizzBuzz to include numbers that contains both (e.g. 35, 53).

Start easy, let’s just work on numbers that contain 3.
This will figure out if a number contains a given digit.

let ContainsDigit digit value =
    value.ToString().Contains(digit.ToString())

Now what? How do I include the extra constraint into my IsFizz function, which is remember a curried version of IsDivisiblyBy.

let IsFizz = IsDivisibleBy 3

This was my first thought

let IsFizz = IsDivisibleBy 3 || ContainsDigit 3

Note, I originally used && instead of ||, that’s the danger of trying to finish a blog post before a train arrives at a station.
If that had worked I wouldn’t be writing this post. I realise that the following will work, but it just seems a little less elegant than the version that didn’t work.

let IsFizz n = IsDivisibleBy 3 n || ContainsDigit 3 n

I’m going to throw this out there, while I keep playing with it. I suspect that what I tried to do here was very silly indeed and suggests I’m still missing something fundamental about currying and functions in general in F#. It feels like it’s worth thinking about this and getting it straight.

So, if you feel you can answer my question, send me a comment explaining why curried functions can not be combined in this way, and what you would do instead in this situation.

In the meantime I’m going to try and figure it out myself.

C# is too damn noisy

This entry is part 6 of 11 in the series Learning to think Functionally

I am growing increasingly frustrated with C#. I think the reason for that may be my exposure to languages like F#. In many ways my feelings for C# are quite similar to feelings I had about VB.Net when I was first exposed to C#.

It’s taken me a while to figure out what it is that I find irritating about C# and I think I’m ready to call it. The problem with C# is exactly the same problem I had with VB.Net, it’s too damn noisy.

Take a look at this code from Martin Rosén-Lidholm

This is clearly a good programmer who cares a lot about writing good code. He went through not one but two approaches that he discarded before settling on a somewhat functional approach. His journey mirrors almost exactly my experience of playing with Conway’s Game of Life.

His ultimate solution in C# is almost identical to my F# approach which was itself based on Vagif Abilov’s approach as presented at NDC Oslo in 2012. The similarity in approach makes it an excellent case study on the relative noise levels in C# and F#.

Noise is code that is not related to the problem being solved, but is instead related to the language, tools, frameworks etc being used.

Let me define what I mean by noise. Noise is code that is not related to the problem being solved, but is instead related to the language, tools, frameworks etc being used.

The first thing I note in Martin’s solution is that Coordinate implements IEquatable, which means two functions called Equals and one called GetHashCode.

By any definition, implementing IEquatable and getting hash codes is not about Conway’s Game Of Life, so, this is noise.

Now, ok, maybe you can build Game Of Life without implementing IEquatable, but I’m sure Martin does it simply because it’s the “right” thing to do. He’s using LINQ and IEnumerable and for historic reasons this is something you do in C# for performance reasons or whatever. But, to me, it’s noise.

In the F# version there is none of that.

Let’s look at all that text in blue in Martin’s example.

‘public class’
‘public void’
‘new’
‘private readonly’
‘params’
‘return’
‘private static’
‘private readonly int’
‘public override bool’
‘unchecked’

And all those
{
curly brackets
}

oh the humanity.

I haven’t even mentioned all of the explicit specifying of types for fields, for arguments and for return types.

All this is just the pieces of code that have nothing to do with the problem domain. Let’s look at the code that actually does something.

Here’s Martin’s code for creating the next generation

public Grid CreateNextGeneration() {
    var keepAliveCoordinates = _aliveCoordinates
        .Where(c => GetNumberOfAliveNeighboursOf(c) == 2 || GetNumberOfAliveNeighboursOf(c) == 3);
 
    var reviveCoordinates = _aliveCoordinates
        .SelectMany(GetDeadNeighboursOf)
        .Where(c => GetNumberOfAliveNeighboursOf(c) == 3);
 
        return new Grid(keepAliveCoordinates.Union(reviveCoordinates).ToArray());
}

Here’s the same function from the F# solution.

 let nextGenerationOf existingCells =
        cellsThatSurviveFrom existingCells
        @
        cellsThatAreAddedTo existingCells

OK, perhaps that’s not the fairest comparison, Martin mentions in a comment that he could push some of that LINQ out into helper functions, but even still, there’s a point here I think.

Is the F# code perfect? No, I dislike the following …

let neighboursOfLiveCells pattern = 
    List.map (fun x -> neighboursOf x) pattern 
    |> flattenList 
    |> Set.ofList |> Set.toList

This was the first F# program I wrote, and maybe if I take another swing at it I can tidy that up a bit, but still, this was the first F# program I wrote, and that function is all that annoys me. That’s ‘noise’ in the F# context.

So far, I’m finding that the noise generally in F# code is much lower than in C# code. I don’t know if that will hold true as I scale up the problems I’m working on, but I see no reason why it wouldn’t. There is a lot of ceremony in C# that really only distracts from the work that the code is supposed to be doing.

None of this is a reflection on Martin, he clearly knows his stuff and cares a great deal about the code he writes. I am using his blog as an example for no other reason than it’s a great example of C# code solving a problem in the same way as some F# code that I happen to have to hand.

Bowling Game Kata in F#

This entry is part 5 of 11 in the series Learning to think Functionally

I’m on an ongoing quest to get competent with F#. I’m also on an ongoing quest to get competent with TDD. Interestingly until now those two quests hadn’t crossed paths. I had written no unit tests in F#. Why you might ask?

When I started writing Unit Tests I found the biggest win wasn’t the design that tests drive, nor was it catching regression bugs. The biggest win was the huge saving on time spent in the debugger.

When I started playing with F# using the REPL, I found that I wasn’t spending any time in the debugger. I mean literally none. After a few weeks of playing with It I actually consciously tried using the debugger to see what it was like. To date I still have had no problem in F# that required me to debug the code.

I recognise that that’s possibly a result of working on “relatively” simple code. I’d hope code would always be simple, but, there will probably come a time when I’ll need to either debug code, or use tests to avoid debugging. So, it’s time to bring F# and TDD together.

The Bowling Game kata seemed like a good start. The attraction of this Kata is that it seems perfectly set up for a functional solution. You have an input (a list of scores from frames) and a desired output (the score for that game) and your job is to write a transformation from one to the other. A list of tuples seems like a really nice way to represent the rolls in a game of bowling, and, I initially thought I may be able to write some sort of ‘fold’ or ‘reduce’ function that would reduce the list of tuples to the correct score. As you’ll see, it didn’t quite work out like I had hoped.

Let’s start with a test for the simplest type of games, one with no Spares or Strikes.

    [<TestCase(Result=30)>]
    member x.RegularGame() =
        let rolls = 
            [(1,2); (1,2); (1,2); (1,2); (1,2); (1,2); (1,2); (1,2); (1,2); (1,2)]
        ScoreGame rolls

My first thought for this was to just use a fold function.

let ScoreGame (frames: List<int * int>) =
    List.fold (fun score frame -> score + fst frame + snd frame) 0 frames 

This does get the test passing, but having played with this I found it virtually impossible to add support for strikes and spares. I’m going to back up and show you the route I eventually settled on, but please feel free to let me know if you manage to make something of the ‘fold’ approach.

let rec ScoreGame (frames: List<int * int>) =
    match frames with
    | [] -> 0
    | frame::rest -> fst frame + snd frame + ScoreGame rest 

This is essentially the same as the fold, but the pattern matching allows us a way of handling special cases. Let’s take a look at one of those now, Spares.

    [<TestCase(Result=38)>]
    member x.ContainsSpares() =
        let rolls = [(1,2); (1,2); (1,2); (5,5); (1,2); (1,2); (1,2); (1,2); (1,2); (1,2)]
        ScoreGame rolls

A frame is a Spare when the two rolls add up to 10. If the first frame on it’s own is 10 then that’s a Strike. We’ll ignore Strikes for now. The following code gets us to green.

let rec ScoreGame (frames: List<int * int>) =
    match frames with
    | [] -> 0
    | frame::rest when fst frame + snd frame = 10
        -> 10 + fst rest.Head + ScoreGame rest
    | frame::rest 
        -> fst frame + snd frame + ScoreGame rest 

When a Spare occurs, the first subsequent roll is added as a bonus.

We can refactor a little bit to make things clearer.

let ScoreFrame (roll:int * int) =
    fst roll + snd roll

let IsASpare (frame:int * int) =
    ScoreFrame frame = 10

let rec ScoreGame (frames: List<int * int>) =
    match frames with
    | [] -> 0
    | frame::rest when frame |> IsASpare
        -> 10 + fst rest.Head + ScoreGame rest
    | frame::rest 
        -> ScoreFrame frame + ScoreGame rest

This is all fairly straightforward so far. There is one little edge case for Spares and that is how they are handled when they occur in the 10th frame. As mentioned above, when you score a Spare the first roll of the subsequent frame should be added as a bonus. The 10th frame is the final frame, so to allow for bonuses on strikes or spares bowled in the 10th frame, up to two additional balls can be rolled. I handle this by adding an 11th tuple when either a strike or spare is scored in the 10th frame, and scoring accordingly.

    [<TestCase(Result=38)>]
    member x.EndsOnASpare() =
        let rolls = 
            [(1,2); (1,2); (1,2); (1,2); (1,2); (1,2); (1,2); (1,2); (1,2); (5,5); (1, 0)]\\
        ScoreGame rolls

When a strike or spare occurs in an earlier frame the subsequent rolls are counted as a bonus, but they are also scored in their own right. This is different for the “11th frame”. This exists purely for the purposes of determining the bonus in the 10th frame, the rolls are not added to the score in their own right.

We need to keep track of what frame we’re on, so we handle the bonus for Strikes and Spares in the 10th frame correctly. One way to do this would be to turn the tuples into triples by adding a frame number to each one. I don’t like adding that burden to the input data, particularly when it’s relatively easy to have the code keep track itself.

let rec ScoreFromFrame thisFrame (frames: List<int * int>) =
    match frames with
    | [] -> 0
    | frame::rest when frame |> IsASpare && thisFrame < 10
        -> 10 + fst rest.Head + ScoreFromFrame (thisFrame+1) rest
    | frame::rest 
        -> ScoreFrame frame + ScoreFromFrame (thisFrame+1) rest

I’ve added a parameter ‘thisFrame’ that indicates which frame is being scored. For frames prior to the 10th frame we add the first roll of the next frame as a bonus, then score from the next frame onwards as normal. For frame 10 we just add the score for frame 11 (if it exists).

I’ve also renamed the function from ‘ScoreGame’ to ‘ScoreFromFrame’. These changes would break all of our tests. We could go back and change each test, but actually I quite like the way the tests are written. When we want the score of a game, we should be able to call ScoreGame and simply pass it a list of frames.

The following would obviously work as a way of preserving the interface that the tests rely on

let ScoreGame (frames: List<int * int>) = 
    ScoreFromFrame 1 frames

But, with a bit of currying there’s an even nicer solution

let ScoreGame = ScoreFromFrame 1

Time for another test, what happens if we score a Strike?

    [<TestCase(Result=40)>]
    member x.ContainsAStrike() =
        let rolls = 
            [(1,2); (1,2); (10,0); (1,2); (1,2); (1,2); (1,2); (1,2); (1,2); (1,2)]
        ScoreGame rolls

A strike is a frame where all 10 pins are knocked by the first ball. The bonus for a strike is the next two rolls.

let rec ScoreFromFrame thisFrame (frames: List<int * int>) =
    match frames with
    | [] -> 0
    | frame::rest when fst frame = 10
        -> 10 + fst rest.Head + snd rest.Head + ScoreFromFrame (thisFrame+1) rest
    | frame::rest when frame |> IsASpare && thisFrame < 10
        -> 10 + fst rest.Head + ScoreFromFrame (thisFrame+1) rest
    | frame::rest 
        -> ScoreFrame frame + ScoreFromFrame (thisFrame+1) rest

This doesn’t correctly calculate the bonus when we score two or more strikes in a row, as we can see from the next failing test.

    [<TestCase(Result=58)>]
    member x.TwoStrikesInARow() =
        let rolls = 
            [(1,2); (1,2); (10,0); (10,0); (1,2); (1,2); (1,2); (1,2); (1,2); (1,2)]
        ScoreGame rolls

The problem here is that after the first Strike we don’t calculate the bonus from the next two ‘Rolls’ which would be 10 and 1, we calculate from the two items in the next frame (10, 0), which isn’t correct. Let’s clarify exactly what we mean by “Next Two Rolls”

let IsAStrike (frame:int * int) =
    fst frame = 10

let NextTwoRollsFrom (frames: List<int * int>) =
    match frames with
    |this::next::rest when this |> IsAStrike && snd this = 0 ->
        10 + fst next
    |this::_ -> ScoreFrame this

let rec ScoreFromFrame thisFrame (frames: List<int * int>) =
    match frames with
    | [] -> 0
    | frame::rest when frame |> IsAStrike
        -> 10 + NextTwoRollsFrom rest + ScoreFromFrame (thisFrame+1) rest
    | frame::rest when frame |> IsASpare && thisFrame < 10
        -> 10 + fst rest.Head + ScoreFromFrame (thisFrame+1) rest
    | frame::rest 
        -> ScoreFrame frame + ScoreFromFrame (thisFrame+1) rest

We can wrap this all up with a test for a perfect game, which should pass with no further changes. For the record, here’s the full code, plus tests, including one or two minor readability tweaks.

module Bowling

let ScoreFrame (roll:int * int) =
    fst roll + snd roll

let IsAStrike (roll:int * int) =
    fst roll = 10

let IsASpare (frame:int * int) =
    ScoreFrame frame = 10

let NextTwoRollsFrom (frames: List<int * int>) =
    match frames with
    [] -> 0
    |this::next::rest when this |> IsAStrike && snd this = 0 ->
        10 + fst next
    |this::_ -> ScoreFrame this

let NextOneRollFrom (frames: List<int * int>) =
    fst frames.Head

let rec ScoreFromFrame thisFrame (frames: List<int * int>) =
    match frames with
    | [] -> 0
    | frame::rest when frame |> IsAStrike && thisFrame < 10
        -> 10 + NextTwoRollsFrom rest + ScoreFromFrame (thisFrame+1) rest
    | frame::rest when frame |> IsASpare && thisFrame < 10
        -> 10 + NextOneRollFrom rest + ScoreFromFrame (thisFrame+1) rest
    | frame::rest 
        -> ScoreFrame frame + ScoreFromFrame (thisFrame+1) rest

let ScoreGame = ScoreFromFrame 1


module BowlingTests

open NUnit.Framework
open Bowling

[<TestFixture>]
type BowlingTests() =

    [<TestCase(Result=30)>]
    member x.RegularGame() =
        let rolls = 
            [(1,2); (1,2); (1,2); (1,2); (1,2); (1,2); (1,2); (1,2); (1,2); (1,2)]
        ScoreGame rolls

    [<TestCase(Result=38)>]
    member x.ContainsASpare() =
        let rolls = [(1,2); (1,2); (1,2); (5,5); (1,2); (1,2); (1,2); (1,2); (1,2); (1,2)]
        ScoreGame rolls

    [<TestCase(Result=38)>]
    member x.EndsOnASpare() =
        let rolls = [(1,2); (1,2); (1,2); (1,2); (1,2); (1,2); (1,2); (1,2); (1,2); (5,5); (1, 0)]
        ScoreGame rolls

    [<TestCase(Result=40)>]
    member x.ContainsAStrike() =
        let rolls = 
            [(1,2); (1,2); (10,0); (1,2); (1,2); (1,2); (1,2); (1,2); (1,2); (1,2)]
        ScoreGame rolls

    [<TestCase(Result=58)>]
    member x.TwoStrikesInARow() =
        let rolls = 
            [(1,2); (1,2); (10,0); (10,0); (1,2); (1,2); (1,2); (1,2); (1,2); (1,2)]
        ScoreGame rolls

    [<TestCase(Result=40)>]
    member x.EndsOnAStrike() =
        let rolls = 
            [(1,2); (1,2); (1,2); (1,2); (1,2); (1,2); (1,2); (1,2); (1,2); (10,0); (1,2)]
        ScoreGame rolls

    [<TestCase(Result=300)>]
    member x.PerfectGame() =
        let rolls = 
            [(10,0); (10,0); (10,0); (10,0); (10,0); (10,0); (10,0); (10,0); (10,0); (10,0); (10,10)]
        ScoreGame rolls

It’s hardly worth mentioning but there’s one little thing that annoys me and that is the definition of a Spare. At the moment any frame with a score of 10 would elicit ‘true’ from the IsASpare function, this means that a Strike would get a true from that function.

Since we check for Strikes before Spares in the Pattern match, this issue doesn’t raise it’s head, but I’d like to make the definition of a Spare more water tight. This would have the added bonus of reducing the dependence of the pattern match on the order of the clauses.

We can modify the IsASpare function quite easily to express it accurately. This isn’t a hugely significant issue in a Kata, but in a business application where you are trying to express concepts in your domain, that little bit of ambuguity (and that isn’t a typo) could have serious implications.

let IsASpare (frame:int * int) =
    not(IsAStrike frame) && ScoreFrame frame = 10

C# to F# Interop – Sharing a Domain Model

This entry is part 4 of 11 in the series Learning to think Functionally
Download
One of the first things I wanted to do with F# was call it from C#. I wanted to be able to take collections of domain objects written in C# and use F# goodness to process them.

It’s actually reasonably easy to do as you’d imagine for two .Net languages. There are one or two speedbumps, we’ll cover those here.

The Assemblies
The attached sample solution includes three projects, a Console Application written in C#, a Domain Model DLL containing two very simple classes, also written in C#, and a Library written in F#. Both the Console App and the F# Library reference the Domain Model, so both are aware of the Domain Objects, and these can be passed between the App and the Library. The Console app also references the F# library, so that it can use its functions.

I don’t know if it’s a problem with Visual Studio (2010) or a problem with me, but to reference the F# library from the C# app, I needed to browse to the DLL. A simple project reference seemed to cause errors.

The Domain Model
The domain model is simply a Product, and a Transaction. A Transaction represents the sale of a Product.

namespace DomainModel
{
    public class Product
    {
        public long Id { get; set; }
        public string Name { get; set; }
        public long Price { get; set; }
    }

    public class Transaction
    {
        public long Id { get; set; }
        public Product Product { get; set; }
        public long quantity { get; set; }
    }
}

The Application is a Console App that creates a list of Transactions and passes it to functions in the F# library, and displays the results.

    class Program
    {
        static void Main(string[] args)
        {
            var transactions = GetTransactions();

            Console.WriteLine("PRODUCTS SOLD");
            var productsSold = Transactions.Stats.ProductsSold(transactions);
            foreach (var product in productsSold)
                Console.WriteLine(string.Format(product.Name));
            Console.WriteLine();

            Console.WriteLine("TOTAL REVENUE PER PRODUCT");
            var totalRevenuePerProduct = Transactions.Stats.TotalRevenuePerProduct(transactions);
            foreach (var productRevenueSummary in totalRevenuePerProduct)
                Console.WriteLine(string.Format("{0} : {1}", productRevenueSummary.Item1.Name, productRevenueSummary.Item2));
            Console.WriteLine();

            Console.WriteLine("TOTAL REVENUE");
            var totalCost = Transactions.Stats.TotalRevenue(transactions);
            Console.WriteLine(totalCost);
            Console.WriteLine();
        }

        private static IEnumerable<Transaction> GetTransactions()
        {
            var banana = new Product {Id = 1, Name = "Banana", Price = 2};
            var apple = new Product {Id = 2, Name = "Apple", Price = 1};
            var pear = new Product {Id = 3, Name = "Pear", Price = 3};

            var transaction1 = new Transaction {Id = 1, Product = banana, quantity = 5};
            var transaction2 = new Transaction {Id = 2, Product = apple, quantity = 10};
            var transaction3 = new Transaction {Id = 3, Product = pear, quantity = 6};
            var transaction4 = new Transaction {Id = 4, Product = apple, quantity = 5};
            var transaction5 = new Transaction {Id = 5, Product = pear, quantity = 7};
            var transaction6 = new Transaction {Id = 6, Product = pear, quantity = 8};
            var transaction7 = new Transaction {Id = 7, Product = apple, quantity = 4};

            return new List<Transaction>
                                   {
                                       transaction1,
                                       transaction2,
                                       transaction3,
                                       transaction4,
                                       transaction5,
                                       transaction6,
                                       transaction7
                                   };
        }
    }

Running the app, shows a distinct list of the products sold, the total sales revenue for each product, and an overall total revenue figures.

PRODUCTS SOLD
Banana
Apple
Pear

TOTAL REVENUE PER PRODUCT
Banana : 10
Apple : 19
Pear : 63

TOTAL REVENUE
92

There’s nothing Earth shattering here. You don’t need to use F# to get any of these figures. The point of this exercise is simply to demonstrate HOW to use F# to process your C# Domain Objects. You can figure out yourself WHEN it’s appropriate.

The F# Library

The F# library defines a namespace ‘Transactions’, and within that a module ‘Stats’. We open the DomainModel to get access to the Transaction and Product classes.

namespace Transactions

module Stats =

    open DomainModel

    let Revenue (t : Transaction) = 
        t.quantity * t.Product.Price

    let TotalRevenue (s : seq<Transaction>) = 
        s |> Seq.sumBy Revenue

    let TotalRevenuePerProduct (s : seq<Transaction>) =
        s |> Seq.groupBy(fun t -> t.Product)
          |> Seq.map (fun (key, values) -> (key, values |> TotalRevenue))

    let ProductsSold (s : seq<Transaction>) =
        s |> Seq.groupBy(fun t -> t.Product)
          |> Seq.map (fun (key, values) -> key)

I’ll take each of the functions in turn.

    let Revenue (t : Transaction) = 
        t.quantity * t.Product.Price

This simple little function calculates the revenue for an individual Transaction. Because we’re accessing properties, it’s important to specify the type. This function doesn’t get called directly from out C# code (although there’s no reason why it couldn’t be), it’s used by the TotalRevenue function.

    let TotalRevenue (s : seq<Transaction>) = 
        s |> Seq.sumBy Revenue

TotalRevenue is called from our C# app. Again, we use a type annotation to indicate that we’ll be receiving a Sequence of Transactions. Sequences are compatible with IEnumerable, so as long as our C# app is sending an IEnumerable this function will be able to work with the items. In the C# app we have a List which is of course compatible with IEnumerable.

The TotalRevenue function itself is very simple, it leverages the Revenue function described above to calculate the revenue for each Transaction. So, the TotalRevenue function really does exactly what it says on the tin. It sums the revenue for the Transactions. This highlights something that you should keep in mind when coding in F# (or indeed any language), it rarely hurts to break out a small specific piece of functionality and put it in it’s own function. It’s particularly true in Functional languages.

Breaking down the Revenue by product is a little trickier, but still pretty straightforward.

    let TotalRevenuePerProduct (s : seq<Transaction>) =
        s |> Seq.groupBy(fun t -> t.Product)
          |> Seq.map (fun (key, values) -> (key, values |> TotalRevenue))

Again we use a type annotation to indicate that the function receives a Sequence of Transactions. Our goal here is to return a sequence of tuples where the first value in the tuple is the Product, not just the name of the product, but the whole thing. The second item in the tuple will be a number indicating the total revenue for that product.

To produce the desired results we first group by the Product, we then take the Transactions grouped under each product and get the Total Revenue for that particular subset of Transactions.

The groupBy function takes a function that returns the key that we want to group by. The code here uses ‘fun t -> t.Product’ which means that for a Transaction t we take the product. The result of Seq.groupBy is a Sequence of tuples in which the first item is the key (the Product) and the second item is a Sequence containing the Transactions for that product.

Because the second item in the tuple is a Sequence of Transactions, it’s valid input for our TotalRevenue Function. It’s worth deconstructing the line of code that actually creates the sequence that we’re ultimately interested in.

Seq.map (fun (key, values) -> (key, values |> TotalRevenue))

It’s Seq.map which means it takes a sequence at applies the specific function to each item. In this case each item is a Tuple, so we assign the name ‘key’ to the first item in the tuple, and the name ‘values’ to the second item, which is itself a Sequence of Transactions. The function creates a tuple as it’s output, the first item of the output Tuple is ‘key’, which means it will be the Product.

The second item of the tuple shows ‘values’ being piped to TotalRevenue, which will return a number indicating the Total Revenue.

If you can get your head around the groupBy example above then you will have no problem with the final example.

    let ProductsSold (s : seq<Transaction>) =
        s |> Seq.groupBy(fun t -> t.Product)
          |> Seq.map (fun (key, values) -> key)

Again we use Type annotations, again we group by Product. This time we just want a distinct list of the Products that were sold. Out Seq.map function works like it did in the last example, except that instead of mapping to a tuple, we map to one value, which is the groupBy key, i.e. Product.

Learning to think functionally – Unfolding Sequences

This entry is part 2 of 11 in the series Learning to think Functionally

In my last post I worked through an example that finds the range of numbers that sum to a target value, or gets as close as possible without exceeding the target. I mentioned that the solution felt a little too like the loopy code I would have written in non-functional languages. I felt that there might be a more “functional” way of solving the problem, but I didn’t know what it was.

Ross McKinlay kindly added a comment to point out how the problem could be solved using the ‘unfold’ feature of sequences. When I first looked at the example, I felt like I often do when I see unfamiliar F# code. Utterly confused.

I eventually figured it out and thought it might be worth a further post. Let’s go back to where we left the code at the end of the last post.

let rec DoSumTo t currentNum currentSum =
    let nextNum = currentNum + 1
    match currentSum + nextNum > t with
    | false -> DoSumTo t nextNum (currentSum + nextNum)
    | true -> [1..currentNum]

let SumTo target =
    DoSumTo target 1 1

> SumTo 28;;
val it : int list = [1; 2; 3; 4; 5; 6; 7]

Let me say at the start, there’s a bug in this code. If you try SumTo 0, you get a wrong answer. We’ll address that bug in this post.

Here’s the alternative “unfold” solution that Ross provided.

let sumTo target =
    Seq.unfold(function
    | (current,total) when total >= target -> None
    | (current,total) -> Some(current,(current+1,total+current))) (1,0) 

Ross’ code has some issues too. For example…

> sumTo 2 |> ToList;;
val it : int list = [1; 2]

In this case the function returns a list of numbers that sum to more than the target. No biggie, a misplaced ‘=’, an easy fix. That aside, I really like the Seq.unfold feature. So, let’s step back for a second and explain some terminology, then we’ll continue.

The following is a very quick, incomplete, and probably inaccurate description of Ranges, Lists and Sequences. It will be just enough to allow you to understand the rest of the post, but I’d urge you to read up on these things yourself for a fuller picture.

Range
A Range Expression is simply a notation for defining a series of numbers from a low value to a high value. By default the increment is 1, but the Range notation also allows us to define a step size. For the purpose of this blog post we’re interested in using Range expressions to define the contents of Lists and Sequences.

List
A List is an ordered series of elements. Lists are immutable, and finite. To put it bluntly, lists actually contain stuff. All the elements in a list will be of the same type, but that can be pretty much anything. Numbers, words, tuples, types, or even other lists.

There are numerous ways of specifying the contents of a list. You can explicitly say what it contains…

let explicitList = [ 1; 2; 3 ]

You can also use a Range expression to define the contents of a list.

let rangeList = [ 1 .. 10 ]

If you want to change the increment size you can. The following range runs from 0 to 100 in steps of 5.

let skipList = [ 0..5..100 ]

Sequences
A Sequence is similar to a list. We can enumerate the items in the sequence, apply aggregate functions, etc. Sequences can be created using Range Expressions in much the same way that Lists can.

let rangeSequence = {1..10}

Note, that the only difference from Lists is that we use braces {} instead of the square brackets [].

The killer feature of Sequence is that the terms of the sequence are generated on an “as needed” basis. So, if a sequence defines a potential range of 1,000,000 items, but a particular function only accesses the first 10 terms, then only the 10 terms are generated. This allows for potentially infinite sequences.

Unfolding Sequences
And, with that very quick primer, we go back to the code from Ross and another much more interesting way to generate a Sequence, Unfolding.

Unfolding a sequence is actually a very simple notion. We use a function to generate the next term in the sequence based on the current term. An example is worth a thousand words, so let’s have one.

let TwoAtATimeFrom n =
    n
    |> Seq.unfold(function x -> Some(x, x+2))

val TwoAtATimeFrom : int -> seq<int>

> TwoAtATimeFrom 11;;
val it : seq<int> = seq [11; 13; 15; 17; ...]

The function accepts a number and pipes it into our unfold function. This value n is used only as the starting point for the sequence. Every subsequent term is calculated based on the previous term.

The key line of code is the unfold function, highlighted above. The result of this line of code is a sequence that starts at 11 (the value of n), and increases in steps of 2. But how? Let’s tear it apart.

It’s the ‘unfold’ method from the Seq module, so this bit is obvious enough.

Seq.unfold(...)

The interesting stuff is what goes on between those parenthesis.

function x -> Some(x, x+2)

We pass a function to unfold that accepts a number and generates the next number. To do that you might think (as I did) that it would be a simple function along the lines of

function x -> x + 2

But, the function actually contains ‘Some(x, x+2)’.
Why the ‘Some’ why both x and x + 2?

As with all things, it’s simple when you understand it, and it’s difficult until then.

‘Some’ indicates that we’re generating an Option value. By this I mean an item that may have a value, or may have none. In C# we’d call these Nullable. As long as the function produces some value the unfolding will continue. If it produces a ‘None’ value, the unfolding stops. Since the example above never produces a ‘None’ value, it is an infinite sequence.

Let’s modify it so there’s an upper limit of 1000.

let TwoAtATimeFrom n =
    n |> Seq.unfold(function 
    | x when x > 1000 -> None 
    | x -> Some(x, x+2))

We start with the value n, but now our unfold function has two options when generating the next term. If the term is greater than 1000, the function returns None, which stops the Sequence unfolding any further. As long as we’re less than 1000, new terms will be created.

Before we move on, let’s look at that “Some” syntax.

    x -> Some(x, x+2))

This says that as the sequence unfolds we take the value x (the first x), we add that value to the sequence (the second x) and then we generate the next value in the sequence by adding two to x (the x + 2). To really make this clear, lets generate another sequence.

let SeqFromTuple (x, y) =
    (x, y) |> Seq.unfold(function 
    (x, y) -> Some(y, (y, x+y)))

This function accepts a tuple, which is used as the starting value of the sequence that will be unfolded. As there is no provision to encounter a ‘None’ value this sequence has no set upper limit.

Each iteration creates a new tuple using the following transformation (x, y) -> (y, x+y). The following shows how that might look.

(1, 1) (1, 2) (2, 3), (3, 5), …

While these tuples are created, this does not reflect the actual sequence that is produced by the code. If you look at the first parameter of the ‘Some’, you’ll see it’s just ‘y’. So, while the unfold function produces a new tuple with each step, only the ‘y’ part of the tuple is actually realised into the Sequence. So the sequence actually looks like this.

> SeqFromTuple (1,1);;
val it : seq<int> = seq [1; 2; 3; 5; ...]

Before I finish let me return to the concept of Option types. These are used in situations where a value may or may not exist. An option will either have “Some” value or “None”. We’ve seen above how None can be used to flag the end of a process of unfolding a sequence. That’s not really a great example of the power of Option types.

Let’s go back to the exercise that started all of this. Given a number, find the range of numbers that sums to the target value. And recognising that not all values can be summed to exactly, we get as close as possible without exceeding the target.

Now, having learned about Option types we can improve this.

Given a number, find the range of digits that sum to the target number, and where no range sums exactly to the target, the function should indicate this by returning None.

Here’s the code.

let ThatSumClosestTo x =
    (0, 0)
    |> Seq.unfold(function 
        (total, num)-> if (total + num > x) 
                       then None 
                       else Some(num,(total + num, num + 1)))

let ThatSumsTo x =
    let closest = 
        ThatSumClosestTo x
        |> Seq.toList
    if closest |> List.sum = x 
    then Some(closest)
    else None

val ThatSumClosestTo : int -> seq<int>
val ThatSumsTo : int -> int list option

> 28 |> ThatSumsTo;;
val it : int list option = Some [0; 1; 2; 3; 4; 5; 6; 7]
> 29 |> ThatSumsTo;;
val it : int list option = None

Attempting to find a range of numbers, starting at 0 that sums to 28, gives 1 to 7, but for 29 there is no range of numbers that sums exactly, and so, the function indicates this by returning None.

I won’t go into detail about how this last version of the code works. I’ve presented enough explanation in this and previous posts for you to work it out, and it’s a worthwhile exercise. If you have any questions, feel free to leave a comment. If you can see opportunities to clean up the code, or simplify it, please leave a comment with suggestions.

“Getting” Functional with F# and The Game Of Life

One session at NDC that really kicked my grasp of functional programming up a few notches was Vagif Abilov’s discussion of Conway’s Game Of Life using F#.

I’m not going to rehash the rules of Game Of Life here, if you aren’t familiar with them then read this.

Vagif’s source code is on github and his slides are on slideshare. His stuff is well worth a look, but don’t look yet.

If you want to really play along with the spirit of this post, stop reading now, and go and code up Conway’s game of life in the object oriented language of your choice. I’ll be here when you get back.

Vagif opened his session with a brief discussion of what an Object Oriented/C# solution might look like. It might for example include a class to represent a cell, perhaps with a state (isAlive) property. It may contain references to it’s neighbours which would themselves be cells. It may even contain the rules for when a cell survives, dies or comes to life. He mentioned one or two very over engineered examples that can be found on the interwebs, those are also worth a look. A cautionary tale on being “Pattern Happy”.

I had recently toyed around with Game of Life for an hour or two in C# so I was hooked from the start. Within 5 minutes of the session starting, I recognised two very simple but fundamental flaws in the way I had approached the problem.

  1. I was thinking in terms of a preallocated board containing cells that are either alive or dead.
  2. I was thinking of a process that modifies the state of the board by killing existing cells and bringing new ones to life.

On the face of it it’s hard to argue with either of those ideas, and it’s hard to see how they could cause any serious problems.

Let’s take them in turn.

A preallocated board brings with it the inbuilt limitation of it’s dimensions (unless we also allow it to be resized). It also requires us to allocate memory for cells that only *might* come to life at some point. We could simply store a list of cells that are alive, and allow some mechanism for figuring out if two cells are neighbours.

A process that modifies the state of the board by killing cells or bringing them to life might work, but we probably don’t want to turn on and off cells while we’re still looking at whether others should live or die, so realistically we would create a copy of the board, use one to make decisions and the other to hold the new state.

Also, since we’re no longer holding on to Dead Cells, we don’t need to worry about killing cells, we simply don’t bother including them in the list of cells that will be in the next generation.

The algorithm for calculating the next generation from a given list of cells becomes trivial

  1. Take the existing list of cells and decide which should survive, we’ll call this list the ‘Survivors’.
  2. Determine the “Dead” neighbours of the existing list of cells and decide who should come to life, we’ll call this the ‘Newborns’

The next generation is created by concatenating the Survivors and the Newborns to create a new list.

I came away from Vagif’s session understanding his approach in about as much detail as I’ve described above. I didn’t know F# well enough to code it immediately, but I decided to see if I could figure it out without peeking at Vagif’s code.

I thought a quick comparison of my results and Vagif’s original code might prove useful to someone learning F# hence, this post.

In the immortal words of Gary Gilmore, “Let’s Do It!”

Representing the “Board”
Let’s start with how we’ll represent the pattern of cells. The way Game of Life is generally described conjures up images of something akin to a chess board, perhaps for this reason it’s not uncommon to find concepts like ‘Board’ in the code, often in the form of a two dimensional array. I preferred to follow Vagif’s lead and went with a list of tuples representing (x, y) coordinates.

We can have some fun here with how we lay out our code. Look at the following two lines, they are functionally identical, but the second one actually illustrates the relative positions of the coordinates we’re defining. We’ll see something similar to this a little later.

let liveCells = [(-1,0); (0, -1); (0,0); (0,1); (1,0)]

let liveCells = [            (-1,0); 
                    (0, -1); (0,0); (0,1); 
                             (1,0) ]

Now that we know what we’re dealing with, let’s write some functions to manipulate our pattern of cells.

To check if a specific cell (i.e. coordinate) is alive or dead, we just have to find out if it’s in our list of live cells.

let isAlive pattern cell = 
    List.exists (fun elem -> elem = cell) pattern

let isDead pattern cell =
    isAlive pattern cell |> not

isDead is just a negation of isAlive, so it’s not all that interesting. isAlive accepts a pattern (i.e. a list of cells) and a specific cell to check. We can call it as follows:

> isAlive liveCells (-1,0);;
val it : bool = true

Vagif’s isAlive is a little cleaner than mine, and he doesn’t bother with an isDead. We’ll see why later.

let isAlive pattern cell =
    pattern |> List.exists ((=) cell)

Find The Neighbours
A key part of The Game of Life is figuring out who are the neighbours of a given cell, and determining how many of those neighbours are alive. Let’s start with determining the neighbours for a specific cell. If you imagine the cell at the center of a 3X3 grid, you can see that any cell has 8 neighbours. Here’s my function for returning the 8 neighbours of a given cell.

let neighboursOf (x, y) =
    [
      (x-1, y-1);   (x-1, y);   (x-1, y+1);
      (x, y-1);                 (x, y+1);
      (x+1, y-1);   (x+1, y);   (x+1, y+1);
    ]

Note again, I could have laid this out as a simple list, but by splitting it over three lines and using a bit of creative whitespace, I can illustrate the relative positions of the 8 neighbours. I had originally been trying to use a nested loop, but couldn’t figure out the syntax and went with this instead. Vagif’s code uses the nested loop approach.

let neighbours (x, y) =
    [ for i in x-1..x+1 do 
      for j in y-1..y+1 do 
      if not (i = x && j = y) then yield (i,j) ]

He does need an if statement to stop a cell registering as a neighbour of itself. I don’t need that in my version. In his favour however is the fact that his approach is much easier to scale up to a third dimension.

That little exercise in finding the neighbours was the first glimpse I had of the power of functional programming. I couldn’t figure out the syntax to state HOW to figure out the neighbours of a cell, so I just stated what the end result should LOOK LIKE. And it worked.

How would we get a list of the neighbours of a cell that are alive? Simples…

let liveNeighbours pattern cell =
    neighboursOf cell |> List.filter (isAlive pattern)

We pipe (‘|>’) the list of neighbours for a cell to a List.filter operation, where we filter using the isAlive function we defined above. This function is basically identical to Vagif’s.

I wrote a separate function for counting the number of live neighbours for a cell, which just gets the length of the list created here. Vagif doesn’t bother with this step.

let numberOfLiveNeighbours pattern cell =
    liveNeighbours pattern cell |> List.length

Deciding whether a cell should remain alive for the next generation is just a question of seeing if it has either 2 or 3 neighbours that are alive.

let cellStaysAlive pattern cell = 
    numberOfLiveNeighbours pattern cell = 2 || numberOfLiveNeighbours pattern cell= 3

Once we’ve written that function for checking an individual cell, we can use it to filter all the existing live cells to create our ‘Survivors’ list.

let cellsThatSurviveFrom cells =
    cells 
    |> List.filter (cellStaysAlive cells) 

As we know finding out which of the existing cells that survive is one of the two things we need to figure out, all that remains is to find out which new cells will come to life. Unfortunately finding survivers is the easier of the two. Finding new cells involves a few steps.

  1. Find all neighbours for the existing live cells
  2. Filter the list of neighbours so that it excludes any cells that are already alive
  3. Count the number of existing live neighbours there are for each of the dead cells identified above
  4. Create a new list containing only dead neighbours of existing cells, that themselves have three existing neighbours

Let’s take this one step at a time, first lets find all the neighbours for all of the live cells. We do this by applying the neighbourOf function to each cell in whatever pattern is passed in.

let neighboursOfLiveCells pattern = 
    List.map (fun x -> neighboursOf x) pattern 
    |> flattenList 
    |> Set.ofList |> Set.toList

Mapping the neighbourOf function to the pattern results in a list of lists. We then flatten that list of lists, and remove duplicates. The flattedList method and then converting the list to a set and back to a list.

The code for flattenList is as follows:

let rec flattenList ls =
        match ls with
        | [] -> []
        | head::tail -> head @ flattenList tail

I did find a way of using the reduce feature of F# to accomplish the same thing, but I already had this way working and so didn’t change it.

The next step is to filter the neighbours so that the list only contains dead cells.

let potentialCells pattern =
    pattern 
    |> neighboursOfLiveCells 
    |> List.filter (isDead pattern)

Create a function that can determine if a specific cell comes alive.

let cellComesAlive pattern cell = 
    numberOfLiveNeighbours pattern cell = 3

Filter the list of Neighbours down to cells that should come alive. This is our list of newborns.

let cellsThatAreAddedTo existingCells =
    potentialCells existingCells 
    |> List.filter (cellComesAlive existingCells)

Vagif used the List.collect method to simplify this whole process. I wasn’t aware of List.collect when I dreamt up that slightly convoluted way of doing things. Note he also passes the isAlive filter through the ‘not’ operator to negate it. In my code I explicitly create an isDead function.

let allDeadNeighbours pattern =
    pattern
    |> List.collect neighbours
    |> Set.ofList |> Set.toList
    |> List.filter (not << isAlive pattern)

Now, back to our existing idea for an algorithm, we combing the cells that survive with the cells that come alive and that gives us the next generation.

let nextGenerationOf existingCells =
        cellsThatSurviveFrom existingCells
        @
        cellsThatAreAddedTo existingCells

Overall I’m reasonably happy that I managed to recreate something close to Vagif’s implementation with very little prior knowledge of F#. I’m still a little dubious about the language itself. It can take a bit of hoop jumping to get things done. However some of those problems are down to lack of familiarity with the language. I would be curious to see a similar implementation in another language like Clojure. I’m also keen to go back and try a C# version again, but done in a more functional way.

In the interests of completeness, here’s my full code listing. Vagif’s code is available from GiHub.

let rec flattenList ls =
        match ls with
        | [] -> []
        | head::tail -> head @ flattenList tail


let liveCells = [            (-1,0); 
                    (0, -1); (0,0); (0,1); 
                             (1,0) ]


let isAlive pattern cell = 
    List.exists (fun elem -> elem = cell) pattern

let isDead pattern cell =
    isAlive pattern cell |> not



let neighboursOf (x, y) =
    [
      (x-1, y-1);   (x-1, y);   (x-1, y+1);
      (x, y-1);                 (x, y+1);
      (x+1, y-1);   (x+1, y);   (x+1, y+1);
    ]

let liveNeighbours pattern cell =
    neighboursOf cell |> List.filter (isAlive pattern)
    
let numberOfLiveNeighbours pattern cell =
    liveNeighbours pattern cell |> List.length




let cellStaysAlive pattern cell = 
    numberOfLiveNeighbours pattern cell = 2 || numberOfLiveNeighbours pattern cell= 3

let cellsThatSurviveFrom cells =
    cells 
    |> List.filter (cellStaysAlive cells) 



let neighboursOfLiveCells pattern = 
    List.map (fun x -> neighboursOf x) pattern 
    |> flattenList 
    |> Set.ofList |> Set.toList

let potentialCells pattern =
    pattern 
    |> neighboursOfLiveCells 
    |> List.filter (isDead pattern)

let cellComesAlive pattern cell = 
    numberOfLiveNeighbours pattern cell = 3

let cellsThatAreAddedTo existingCells =
    potentialCells existingCells 
    |> List.filter (cellComesAlive existingCells)



let nextGenerationOf existingCells =
        cellsThatSurviveFrom existingCells
        @
        cellsThatAreAddedTo existingCells