All posts by Tom Prior

Memoizing Counting Change in F#

One of my favorite programming koans is the counting change problem. Its a good one for practicing solving a problem in a new language or just refreshing myself on some recursive algorithmic reasoning.

I’ve been coding in F# for almost a year now professionally and just over a year in my spare time coding. Previously, I had completed this koan in Scala but, until recently, I hadn’t tried it in F#. It came up as a challenge on hackerrank so I thought I’d give it a go in F#.

spoiler alert

the rest of this blog will contain code and links to my full solution on github so you might want to try it out yourself first if you’ve never done this coding koan before.

I went about solving the problem recursively and this was enough to make some of the hackerrank test pass but the solution timed out for a lot of tests – coming in at about 2 minutes for some test cases just didn’t cut it. To make it faster, I used memoization to store up any previously computed values so that I wasn’t duplicating work. This sped up the execution a lot – from around 2 minutes for some test cases to about 60 milliseconds!

The Problem

The problem is as follows:
Given an amount and a list of coin denominations, how many ways can the coin denominations be combined to make up the amount. A combination can use coin denominations more then once.
So, for example:
Amount is 4
Coin denominations are [ 1; 2; 3 ]

The answer is 4 combinations because the coins can be combined as follows:
[ 1; 1; 1; 1 ]
[ 1; 1; 2 ]
[ 1; 3 ]
[ 2; 2 ]

Solving the problem

I came up with a solution using recursion without memoization initially.

So lets say we have a function numberOfCombinations that gets the number of combinations for an amount, amount, out of denominations, denoms.

The numberOfCombinations function works as follows, taking our earlier example:

We take the first denominator – lets call this “main denominination” and subtract that from the amount 4 to get 1. So now we are trying to find the number of combinations that make up 1 from the rest of the denominators [ 2; 3 ]. However, in order to do that, we have to call our numberOfCombinations function recursively on amount, 1 and denoms [ 2; 3 ] – this starts off a recursion as this will itself continue on subtracting 2 from 1 and calling numberOfCombinations for amount -1 on denoms [3]. When we hit negative number, this inner recursive path stops and we return a 0 number of combinations back up the recursive calls.

Meanwhile back in the first numberOfCombinations call (the call we made for numberOfCombinations 4 [ 1; 2; 3 ]), we need to continue subtracting the denominator, 1 so we subtract 1 from 3 and get 2 and so on until we hit a 0 or negative number.

There is also a second recursion too. As we move through the denominations, each one gets a go at becoming the “main denomination” and a go at being the denomination that gets subtracted through a recursive run of the numberOfCombinations function.

All this means is that, we also start off recursive calls for
numberOfCombinations 2 [3]
and number of combinations 3 []

So how do we reach a point where we know we have hit a combination?

Well lets follow one path through the recursion starting with
numberOfCombinations 4 [ 1; 2; 3 ]
giving

numberOfCombinations (4 – 1) [ 2; 3 ]
giving

numberOfCombinations (3 – 2) [ 3 ]
giving -2 [ ]

but numberOfCombinations 3 [ 2; 3] also gives
numberOfCombinations (3 – 3) [] when 3 becomes the “main denominator”

So here we detect a combination because we have reached the amount, 0. the combination detected is [ 1; 3 ].

Below is the algorithm expressed in F# without any memoization optimization.

let rec private numberOfCombinationsNoMemoization (amount:int) (denominations: int list)  =
        match denominations with 
        | [] ->
            0L
        | d :: ds ->
            if amount = 0 then
                1L 
            elif amount < 0 then
                0L
            else 
                (numberOfCombinationsNoMemoization (amount - d) denominations) + 
                (numberOfCombinationsNoMemoization amount ds) |> int64
                

let countChangeNoMemoization (amount:int) (denominations: int list) =
    numberOfCombinationsNoMemoization amount denominations 

A test case for this which is taxing on performance is as follows:

[<Fact>]
let ``no memoization - number of combinations for amount 219 and denominations 36 10 42 7 50 1 49 24 37 12 34 13 39 18 8 29 19 43 5 44 28 23 35 26 should be 168312708`` () =
    countChangeNoMemoization 219 [ 36; 10; 42; 7; 50; 1; 49; 24; 37; 12; 34; 13; 39; 18; 8; 29; 19; 43; 5; 44; 28; 23; 35; 26 ] |> should equal 168312708L

This individual test clocks in at 2 minutes and 2 seconds.

What’s with this memoization stuff?!

Memoization is a way of storing the results of calls to a function for previous parameter values. With the recursive algorithm being used, there is a lot of duplicated work especially when there is a larger number of denominations as in the test case shown above. This is because with all the different paths through the recursion, the recursive function can be called multiple times for the same value for amount and denominations. So there is wasted work. Using memoization, we can store up all the results of previous calls to the recursive function in a Dictionary. So, each time it is called we can look up the Dictionary to see if we have already calculated a result for the amount and denominations in question.

In the new solution below, I have added in this mechanism:

let rec private numberOfCombinations (amount:int) (denominations: int list) (prevCalculatedSolutions:Dictionary<int * Set<int>, int64>) =
    if prevCalculatedSolutions.ContainsKey((amount, Set.ofList denominations)) then 
        prevCalculatedSolutions.[(amount, Set.ofList denominations)]
    else
        match denominations with 
        | [] ->
            0L
        | d :: ds ->
            if amount = 0 then
                1L 
            elif amount < 0 then
                0L
            else 
                let solution = 
                    (numberOfCombinations (amount - d) denominations prevCalculatedSolutions) + 
                    (numberOfCombinations amount ds prevCalculatedSolutions) |> int64
                
                prevCalculatedSolutions.Add((amount, Set.ofList denominations), solution) |> ignore
                solution

let countChange (amount:int) (denominations: int list) =
    numberOfCombinations amount denominations (new Dictionary<int * Set<int>, int64>())

The test case with the same input but using the memoized solution is below:

[<Fact>]
let ``number of combinations for amount 219 and denominations 36 10 42 7 50 1 49 24 37 12 34 13 39 18 8 29 19 43 5 44 28 23 35 26 should be 168312708`` () =
    countChange 219 [ 36; 10; 42; 7; 50; 1; 49; 24; 37; 12; 34; 13; 39; 18; 8; 29; 19; 43; 5; 44; 28; 23; 35; 26 ] |> should equal 168312708L

This now clocks in at 66 milliseconds.

Conclusion

Memoization is a great technique to dramatically increase performance especially in these sort of path finding recursive type problems. With F#’s pragmatic approach, it is quite straight forward to add in a simple memoization mechanism using a .NET Dictionary that can be mutated in place. To make this slightly more pure, an immutable map could be used which would need to be updated passed through all the recursions. However, as the recursive function, numberOfCombinations, is private and quite small, I believe controlled mutation is perfectly fine and a very effective mechanism for memoization.

The full solution with tests is available on my github here

Let’s Get Jammin’

One of my favorite things about F# is the ease and pleasure it brings to the otherwise tricky task of asynchronous programming. Using async workflows/computation expressions, mailbox processors (agents) and async combinators makes async, parallel and concurrent programming a total joy in F#.

Outside of programming and family life, another joy of mine is listening to and playing (albeit not so much these days) music. I played Double Bass on the Irish jazz scene up until about 7 years ago when I got back into software development.

That’s me on the Double Bass around 2004 looking a lot younger!

For a few years, music was my life and, when not practicing on my own, I would be rehearsing and playing gigs or just getting together with musician friends to have a jam session. A jam session would be when we would get together in someone’s house and just play music until the early hours or else it could be more official like an open session at a venue around town.

When I was thinking about what I would write about for my F# advent calendar post, I wanted to do something involving async but I also wanted a little app or toy project to use as a playground to show some async in practice. I got reminiscing on my music days and I was thinking wouldn’t it be cool to have an app that would help musicians get together for these jam sessions! Back then, I was living in Dublin and there were a lot of musicians moving to and from there all the time. So, what about an app that could track musician availability at different locations and suggest other musicians for them to meet up with for jam sessions. For this post, I built a prototype for this idea using two distributed processes,  CQRS (command query responsibility segregation), and Azure Service Bus to asynchronously propagate events from one process to the other. Who knows, maybe I’ll eventually build out the idea into a full production app!

Introducing the Social Music platform!

In order to set the stage (pardon the pun!), lets imagine that this app which gets musicians together for jam sessions is part of a bigger platform called “Social Music”.

One part of the system – SocialMusicLocations –  is a process (or multiple instances of this process) which is in charge of the being the source of truth on everything that happens with locations (or a subset of locations if we were to make this into multiple instances). It processes commands related to locations, transforms these commands into events related to these locations, stores them in an immutable event store and also propagates these events to other processes that use them in order to store and serve up a view/read model that their clients would be interested in. SocialMusicMatchMaker is one process which receives these event propagations. It generates its own current state based on events that it receives and this state is made available via an HTTP API for its consumers – e.g a consumer could be a web/mobile app, “LetsGetJammin”, suggesting possible other musicians for users to get together with to have a jam session!

The events propagation from SocialMusicLocations to SocialMusicMatchMaker is where async processing comes into play. Within SocialMusicLocations, there is an F# mailbox processor receiving events into its mailbox and asynchronously storing these events to an event store and also propagating them as messages to an Azure service bus queue.

To keep things simple, the events store in SocialMusicLocations is an in memory store using NEventStore. Also the locations read model within SocialMusicMatchMaker will just use in memory persistence with a .NET Dictionary.

Also, the code for each of these processes will live separate solutions each of which being a.NET Core 2.0 solution. So, when the Social Music platform takes off and there’s billions of users, we can just scale out these processes with docker containers or whatever the cool kid on the block is in container technology by then .

The code for these two solutions is available on my github here. For the rest of this blog post, I will go through some of the more interesting parts of the code and show some async, CQRS and domain modelling in action.

SocialMusicLocations

The Domain

The domain for this is very simple consisting of definitions for a musician, instrument, location, events, commands and a state that is an aggregation of previous events. In order to track changes in musician presence within locations over time, I’ve kept it really simple and just have two commands and associated events for musicians registering to a location or deregistering from a location that they are currently registered to. So from the Musician type down through the command and event types, there is the simple idea of a musician being one who is registered (or being registered through a command) to a location or one who is deregistered (or being deregistered through a command).

namespace SocialMusicLocations.Core.Domain


type Location = 
    | Tipperary
    | Limerick
    | Belfast
    | Galway
    | Dublin

type Instrument =
    | DoubleBass
    | ElectricBass 
    | Drums
    | Piano 
    | Guitar
    | Sax 
    | Trumpet
    | Trombone

type RegisteredMusician = {
    Name : string
    Location : Location
    Instrument : Instrument
}

type UnRegisteredMusician = {
    Name : string
    Instrument : Instrument
}

type Musician = 
    | RegisteredMusician of RegisteredMusician
    | UnRegisteredMusician of UnRegisteredMusician
    
module Commands =

    type Command =
        | RegisterMusician of UnRegisteredMusician * Location
        | DeregisterMusician of RegisteredMusician

module Events = 
    
    type Event =
        | MusicianRegistered of RegisteredMusician
        | MusicianDeregistered of PreviousLocation:Location * UnRegisteredMusician
        
module State = 
    
    type LocationDetails = {
        Location : Location
        MusicianCount : int
    }
    
    type State = 
        | EmptyLocation of Location
        | OccupiedLocation of LocationDetails
        
module Errors = 

    type Error = CannotDeregisterFromEmptyLocation
    
    let toString = function | CannotDeregisterFromEmptyLocation -> "Cannot deregister from an empty location"
    

 

I’m also representing errors with a DU which has just one case for the error that will arise if a command attempts to deregister a musician from an empty location.

Command handling

The command handing is two stage operation consisting of the functions above. First of all the CommandHandler.handle function takes a current state and a new command to either register or deregister a musician from a location. Based on these inputs, it generates a list of events as, if you like, a recording of the operation of applying the command. It then folds across these events calling StateGeneration.apply to transform the state along the way until it ends up with the final state. If everything is ok, the CommandHandler.handle function returns the events and final state wrapped in an F# Result.Ok. If there is an error in processing the command – for example if an attempt is made to deregister a musician from an empty location – the CommandHandler.handle function returns this error wrapped in an F# Result.Error.

The code for the CommandHandler.handle function is shown below:

let handle (state:State) (command:Command) =
    let eventsResult = 
        match command with
        | RegisterMusician (unRegisteredMusician, _) ->
            registerMusician unRegisteredMusician state
        | DeregisterMusician registeredMusician ->
            deregisterMusician registeredMusician state
    eventsResult 
    |> Result.map (fun events ->
        let newState = events |> List.fold StateGeneration.apply state
        newState, events)

The Event Store

All events generated by the command handling are stored per location. To get the current state of a location, it is a matter of starting with an initial empty location and applying all the events from that location using the StateGeneration.appy function again.

type Store = {
    SaveEvents : State -> Event list -> unit
    GenerateState : Location -> State
}

 

The event store is defined as a type with two functions to save events and generate state as shown above. For the purpose of this prototype, I used NEventStore which provides an in-memory event store as a stream of events corresponding to an ID. I used the location as the id in a simplistic way shown below so that events can be stored per location.

let private locationToId = function
    | Tipperary -> "tipperary"
    | Limerick -> "limerick"
    | Belfast -> "belfast"
    | Galway -> "galway"
    | Dublin -> "dublin"

The implementation details of calling out to NEventStore’s store and retrieve mechanism are hidden behind the Store type that I showed above (full source code is available on my github here).

Mailbox Processor to Propagate Events

A mailbox processor in F# is like a state machine. When a mailbox processor instance is created, a function is supplied with the type:
MailboxProcessor<‘Msg> -> Async<unit>.
Its within this function where the action happens usually in the form of a recursive function that the programmer defines usually called

loop

which loops with each loop running in an async block/computation expression. So with each loop, a thread from a .NET thread pool is supplied.
MailboxProcessor<‘Msg>
is essentially like an inbox and provides an inbox.Receive() function which blocks until a new message of type ‘Msg arrives. This allows you to write code in an async block which will wait for the next message, handle it and take action to possibly update state, and recursively call the loop function with this new state. The mailbox processor used to propagate the event messages for SocialMusicLocations doesn’t have state which is passed between calls to the loop function – it uses CommandHandler.handle shown earlier to generate events and new state and performs a side effect operation of saving to the in memory event store and sending a message for each event to an Azure service bus queue.

The ‘Msg type that a mailbox processor handles is defined by the programmer and, for SocialMusicLocations, it is defined as:

type private AgentMessage = 
    | PostCommand of Command * AsyncReplyChannel<AgentResponse>
    | Stop

 

The Stop message will be used to tell the mailbox processor to stop processing any more messages.

The PostCommand DU case above is a message consisting of the domain model Command along with an AsyncReplyChannel which can carry an AgentResponse.

AgentResponse is defined as:

type AgentResponse = 
    | Success of State * Event list
    | Failure of Error

 

The mailbox processor is encapsulated in a type which I called Agent. This is where the OO capabilities of F# work really well for encapsulating the fact that a mailbox processor is being used for async processing. The messages that I showed earlier, which can be sent to the mailbox processor, are encapsulated behind methods of the Agent class. This class is defined as follows:

type Agent(eventStore:Store, connectionString:string, queueName:string) = 
    
    let locationFromCommand = function
        | RegisterMusician (_, location) -> location
        | DeregisterMusician registeredMusician -> registeredMusician.Location
        
    let propagateEvent event = async {
        let queueClient = new QueueClient(connectionString, queueName);
        let (messageLabel, messageBody) = 
            match event with
            | MusicianRegistered registeredMusician ->
                    "musicianRegistered", JsonConvert.SerializeObject {
                        timestamp = DateTime.UtcNow.Ticks
                        musicianName = registeredMusician.Name
                        instrument = registeredMusician.Instrument |> Instrument.toString
                        musicianLocation = registeredMusician.Location |> Location.toString }
            | MusicianDeregistered (previousLocation, unRegisteredMusician) ->
                    "musicianDeregistered", JsonConvert.SerializeObject {
                        timestamp = DateTime.UtcNow.Ticks
                        musicianName = unRegisteredMusician.Name
                        musicianLocation = Location.toString previousLocation
                        instrument = Instrument.toString unRegisteredMusician.Instrument }

        let message = new Message(System.Text.Encoding.UTF8.GetBytes(messageBody))
        message.Label <- messageLabel
        try
            do! queueClient.SendAsync(message) |> Async.AwaitTask
        finally
            queueClient.CloseAsync() |> Async.AwaitTask |> Async.RunSynchronously
    }
    
    let propagateEvents = List.map propagateEvent
    
    let agent = MailboxProcessor<AgentMessage>.Start <| fun self ->
                
        let rec loop () = async {
            let! message = self.Receive()
            match message with
            | PostCommand (command, replyChannel) ->
                let currentState = eventStore.GenerateState(locationFromCommand command)
                let eventsResult = handle currentState command
                match eventsResult with
                | Ok (state, events) ->
                    eventStore.SaveEvents state events
                    events |> propagateEvents |> List.iter Async.Start
                    replyChannel.Reply (Success (state, events))
                | Error error -> replyChannel.Reply (Failure error)
                return! loop()
            | Stop -> return ()    
        }
        loop ()
    
    member x.Stop() = agent.Post Stop
    
    member x.HandleCommand(command:Command) = 
        let createMessage replyChannel = PostCommand (command, replyChannel)
        agent.PostAndReply(createMessage)

 

With

let! message = self.Receive()

the async computation being executed can wait in a non blocking fashion – the thread currently being used can be given back to the thread pool until a message is received – in which case, another available thread from the thread pool (or possibly the same thread again) can be used to process the next part of the async computation.

The helper function, propagateEvent, is used to serialize an event to json, add a timestamp and send it to the Azure service bus queue. The timestamp being added can be used by message receivers to maintain ordering across a location as, without using Azure service bus sessions, order is not guaranteed. In the code above, the pattern discussed earlier of using the recursive loop function to process mailbox messages  can be seen. Once a message is received, the Command it contains can be processed unless it is a Stop message – in which case, the recursive looping is stopped.

The Http Command API

An api to accept the commands to register or deregister musicians is provided by a simple Rest API implemented with Suave
Suave provides a really nice way of composing together a web application with the concept of Web Parts. There’s a lot of great documentation and tutorials on Suave out there – a really great one that I totally recommend is this course on FSharp TV.

The HTTP command API also acts as a boundary to make sure that any commands that get past it will be valid Commands according to the domain model shown earlier. For this I used the applicative pattern of wrapping a constructor function inside a Result type and applying this across its arguments which, themselves, are each pumped through their own validation function to decide if they are valid or not by outputting the same Result type.
This may sound a bit abstract and vague for anyone who hasn’t seen this before – I know it did for me. The best resources I found for learning these kind of patterns are the chapters on Functors, Applicatives and Monads from Haskell Programming from First Priciples and also Scott Wlaschin’s series on map, bind and apply.

The Result type, called ValidationResult is a wrapper type which has a case for wrapping a successfully validated command and also a case for wrapping a list of errors that have been collected along the way.

type ValidationResult<'a> = Success of 'a | Error of string list

 

The constructor function to create a domain Command type is as follows:

let toCommand (commandType:ValidCommandType) (name:string) (instrument:Instrument) (location:Location) = 
    match commandType with
        | Register ->
            RegisterMusician ({ Name = name; Instrument = instrument }, location)
        | DeRegister ->
            DeregisterMusician ({ Name = name; Instrument = instrument; Location = location })

 

In order for the applicative pattern to work, each of the parameters to this constructor function needs to be wrapped in the same ValidationResult type – in the case where no validation is required, wrapping the parameter in the Success DU case will suffice.
So for each parameter, I have an associated validation function, most of which, convert strings into appropriate DU types as follows:

type ValidCommandType = Register | DeRegister
    
let validateCommandType (commandType:string) = 
    match commandType with
    | "registerMusician" -> Success Register
    | "deRegisterMusician" -> Success DeRegister
    | _ -> Error <| [ sprintf "commandType, %s, is not a valid command type" commandType ]
        
let validateMusicianName (name:string) = 
    if String.IsNullOrWhiteSpace name then 
        Error [ "Musician name cannot be blank" ] 
    else 
        Success name
            
let validateInstrument (instrument:string) =
    match instrument with 
    | "DoubleBass" -> Success DoubleBass
    | "ElectricBass" -> Success ElectricBass 
    | "Drums" -> Success Drums
    | "Piano" -> Success Piano 
    | "Guitar" -> Success Guitar
    | "Sax" -> Success Sax 
    | "Trumpet" -> Success Trumpet
    | "Trombone" -> Success Trombone
    | _ -> Error [ sprintf "instrument, %s, is not a valid instrument" instrument ]
    
let validateLocation (location:string) =
    match location with
    | "Tipperary" -> Success Tipperary
    | "Limerick" -> Success Limerick
    | "Belfast" -> Success Belfast
    | "Galway" -> Success Galway
    | "Dublin" -> Success Dublin
    | _ -> Error [ sprintf "location, %s, is not a valid location" location ]

 

The little engine room of the applicative approach is defined in ValidationResult.apply as follows:

module ValidationResult =
    let apply (f: ValidationResult<'a -> 'b>) (validationResult: ValidationResult<'a>) =
        match f, validationResult with
        | Success f', Success validationResult -> 
            Success <| f' validationResult
        | Success _, Error errors -> 
            Error errors
        | Error errorsA, Error errorsB -> 
            Error <| errorsA @ errorsB
        | Error errors, Success validationResult -> 
            Error errors

 

The apply function takes two ValidationResult types :

  • f is a wrapper for a function and, at runtime, this wrapper will either be the Success ValidationResult case or it may be the Error case.
  • validationResult is a wrapper for a value – wrapping either the value or a list of errors associated with trying to produce this value. When Validation.appy is used with the toCommand constructor function, each time Validation.apply is called, this validatationResult will be the result of validating an individual argument to the toCommand function using one of the validation functions shown earlier, e.g validateInstrument.

In order to chain up successive calls to Validation.apply, I’ve add just a dash of ML soup to make things a bit cleaner with defining a local operator.

let (<*>) = ValidationResult.apply

 

So, now the whole validateCommand function is as follows:

let validateCommand unvalidatedCommand = 
    let (<*>) = ValidationResult.apply
    Success toCommand
    <*> validateCommandType unvalidatedCommand.command
    <*> validateMusicianName unvalidatedCommand.name
    <*> validateInstrument unvalidatedCommand.instrument
    <*> validateLocation unvalidatedCommand.location

 

Pattern matching withing the ValidationResult.apply function means that any errors that are encountered with successive calls to  ValidationResult.apply are appended together.

So, after calling the validateCommand function, you either end up with a ValidationResult which wraps a valid Command type or a list of errors collected along the way.

SocialMusicMatchMaker

SocialMusicMatchMaker  is an entirely separate .NET sln and separate process. It asynchronously consumes messages from the Azure service bus queue that SocialMusicLocations sends messages to. On consuming these messages, it updates a read model which is a representation of the current state of locations. It also uses Suave to expose an HTTP Rest Api to query this read model.

The Domain

SocialMusicMatchMaker has it’s own domain which is effectively a read model snapshot of the source of truth that it is consuming from Azure service bus queue in the form of messages sent by SocialMusicLocations. Its domain model is similar to that of SocialMusicLocations except for a few notable differences. For example, the Musician type is represented as a straight record instead of a DU because there isn’t the concept of a registered or deregistered musician in the read model – it is simply musicians keyed by location.

type Musician  = {
    Name : Name
    Instrument : Instrument
}

 

Also the Event type is slightly different in SocialMusicMatchMaker because the timestamp is added to each Event DU case. I will show shortly how this is used when updating the read model.

type Event = 
    | MusicianRegistered of Timestamp:int64 * Location * Musician
    | MusicianDeregistered of Timestamp:int64 * Location * Musician
    
module Event = 
    let createMusicianRegistered timestamp (name:Name) (instrument:Instrument) (location:Location) = 
        MusicianRegistered (timestamp, location, { Name = name; Instrument = instrument })
        
    let createMusicianDeregistered timestamp (name:Name) (instrument:Instrument) (location:Location) = 
        MusicianDeregistered (timestamp, location, { Name = name; Instrument = instrument })

Consuming Events

In the last section, you can see that the Event type has an associated module with constructor functions for each Event DU case. This is because I follow the same pattern for validation in SocialMusicMatchMaker that I have already shown for SocialMusicLocations using an applicative pattern.

In order to turn a service bus message into one of these Event DU cases, the message is first validated. This time round, since the likelihood of receiving an invalid message is very slim in this prototype system, I used the F# option type instead of using a ValidationResult type. So if there are any validation errors, a None will be produced and the message is effectively ignored.

I enhanced the Option module with an apply function like I showed earlier for ValidationResult.apply:

type module Option = 
    let apply (f: ('a -> 'b) option) (a: 'a option) =
        match f, a with
        | Some f', Some a' -> Some (f' a')
        | _, _ -> None 

 

Each part of the service bus message that needs to be validated has a validation function that returns an Option:

type Name = private Name of string

module Name = 
    let create (name:string) = 
        if String.IsNullOrWhiteSpace(name) then 
            None 
        else 
            Some (Name name)
    
    let toString (Name name) = name

 

This time round, for musician name I went a step further and created a single case DU with a private data constructor so that only the type is available outside the module SocialMusicMatchMaker.Core.Domain, and not the value/data constructor.

The constructor function, create, is a smart constructor which only allows valid Name values to be created.
We still need to be able to pattern match on a Name type outside of this module. This can be enabled with an active pattern:

let (|Name|) (Name name) = Name name

 

The other parts that make up a musician registered or deregistered event have similar validation functions which also return None for an invalid value:

module Instrument = 
    
    let fromString instrument =
        match instrument with
        | "DoubleBass" -> Some DoubleBass
        | "ElectricBass" -> Some ElectricBass 
        | "Drums" -> Some Drums
        | "Piano" -> Some Piano
        | "Guitar" -> Some Guitar
        | "Sax" -> Some Sax
        | "Trumpet" -> Some Trumpet
        | "Trombone" -> Some Trombone 
        | _ -> None 

module Location = 
    
    let fromString location = 
        match location with
        | "Limerick" -> Some Limerick
        | "Belfast" -> Some Belfast
        | "Galway" -> Some Galway
        | "Dublin" -> Some Dublin
        | _ -> None

 

A valid MusicianRegistered or MusicianDeregistered event can then be created by putting the applicative pattern into action again:

let convertToEvent (message:Message) =

    let (<*>) = Option.apply
    
    match message with
    | MusicianRegisteredEventMessage (MusicianRegistered propagationMessage) -> 
         Some (Event.createMusicianRegistered propagationMessage.timestamp)
         <*> (Name.create propagationMessage.musicianName)
         <*> (Instrument.fromString propagationMessage.instrument)
         <*> (Location.fromString propagationMessage.musicianLocation)
        
    | MusicianDeregisteredEventMessage (MusicianDeRegistered propagationMessage) ->
         Some (Event.createMusicianDeregistered propagationMessage.timestamp)
         <*> (Name.create propagationMessage.musicianName)
         <*> (Instrument.fromString propagationMessage.instrument)
         <*> (Location.fromString propagationMessage.musicianLocation)
    | _ -> None 

 

Again, I’ve added a dash of ML soup with (<*>) to make the chaining up of the Option.apply calls a bit easier.

So where are – MusicianRegistered propagationMessage – and – MusicianDeRegistered propagationMessage – coming from. They are types I added to enable deserializing of the service bus message. To enable the pattern matching above on – match message – I used active patterns which check for a messages that we are interested in by checking the message label and attempting to deserialize the message body:

type MusicianRegisteredPropagationMessage = {
    timestamp : int64
    musicianName : string
    musicianLocation : string
    instrument : string    
}

type MusicianDeregisteredPropagationMessage = {
    timestamp : int64
    musicianName : string
    musicianLocation : string
    instrument : string    
}

type PropagationMessage = 
    | MusicianRegistered of MusicianRegisteredPropagationMessage
    | MusicianDeRegistered of MusicianDeregisteredPropagationMessage

let (|MusicianRegisteredEventMessage|_|) (message:Message) = 
    match message.Label with
    | "musicianRegistered" -> 
        try
            JsonConvert.DeserializeObject<MusicianRegisteredPropagationMessage>(System.Text.Encoding.UTF8.GetString(message.Body)) 
            |> MusicianRegistered
            |> Some
        with _ -> None
    | _ -> None

let (|MusicianDeregisteredEventMessage|_|) (message:Message) = 
    match message.Label with
    | "musicianDeregistered" -> 
        try
            JsonConvert.DeserializeObject<MusicianDeregisteredPropagationMessage>(System.Text.Encoding.UTF8.GetString(message.Body)) 
            |> MusicianDeRegistered
            |> Some
        with _ -> None
    | _ -> None
The Azure Service Bus Consumer

To consume from the Azure service bus queue, I used a handy library, Microsoft.Azure.ServiceBus

This makes consuming messages very straight forward by creating a MessageReceiver and registering a message handler function:

type ServiceBusConsumer(connectionString, queueName, projectEvent: Event -> unit) =

    let messageReceiver = new MessageReceiver(connectionString, queueName, ReceiveMode.ReceiveAndDelete)
    do messageReceiver.RegisterMessageHandler(
        (fun message _ -> 
                System.Threading.Tasks.Task.Run (fun _ -> 
                        printfn "Event message received %s" (System.Text.Encoding.UTF8.GetString(message.Body))
                        let event = convertToEvent message
                        do event |> Option.iter projectEvent
                )),
        (fun _ -> System.Threading.Tasks.Task.Run (fun _ -> printfn "event consumer failure") )) 

 

The message handler above converts service bus messages that we are interested in into events and then projects these events to update the read model which is the last part I’ll talk about next.

Updating the Read Model

The read model is abstracted behind a simple interface representing a data store that allows for saving of a musician with a timestamp to a location, removing a musician from a location and also getting all musicians for a location – which facilitates the HTTP Rest api to get all musicians currently in a location.

type DataStore = {
    RemoveMusician : int64 -> Location -> Musician -> unit
    AddMusician : int64 -> Location -> Musician -> unit
    GetMusiciansForLocation : Location -> Musician list
}

 

For the purpose of the prototype, I implemented an in memory implementation of this interface with a simple Dictionary:

let private inMemoryDb = new Dictionary<Location, Set<Musician * Timestamp>>()

 

and a crude transaction implementation using locking:

let private performDbTransaction f = 
    
    Monitor.Enter inMemoryDb
    try
        f inMemoryDb
    finally
        Monitor.Exit inMemoryDb

 

The implementations of the functions from the DataStore interface use basic operations on a .NET Dictionary. The only extra bit is that the timestamps are checked so that only an event relating to a musician with a timestamp after the latest timestamp for this musician is considered.

The function that is used by the service bus consumer to call out to the data store is as follows:

let projectEvent (dataStore:DataStore) event =
    match event with
    | MusicianRegistered(timestamp, location, musician) -> 
        dataStore.AddMusician timestamp location musician
    | MusicianDeregistered (timestamp, location, musician) -> 
        dataStore.RemoveMusician timestamp location musician

 

There is not much to that function – it simply calls out to the relevant functions of the DataStore type that it is injected with.

Conclusion

I really enjoyed creating this little prototype system and its something I will expand upon – like adding a mobile UI to consume from SocialMusicMatchMaker in the form of a “Lets Get Jammin'” app! I would also like to explore using different technologies for distributed event propagation, for example Apache Kafka.

The full source code for this prototype is available on my github here.

I hope you have gotten something out of reading this. Thanks so Sergey Tihon for organizing the F# Advent Calendar and for all the great work he does with his regular updates on F# Weekly

Thanks for taking time to read this!

F# Xunit with .NET Core 2.0, VsCode and Ionide – Run all tests with keyboard shortcut

A while back I wrote a post about F# unit testing in vscode with ionide

With the release of .NET Core 2.0 this week, I was keen to explore it and, in the process, I found a really nice work flow for running Xunit tests in VsCode. Using a VsCode task and the .NET core CLI, I can simply run all Xunit tests with one simple keyboard shortcut. There’s a few steps to get it set up but really its very quick to set up and, once you do it once, its quicker for any subsequent solutions that you use it on.

To show this in action, I went through a set up of a new solution using .NET Core 2.0 today and documented all my steps below. Hopefully this helps others to get a nice work flow set up for their F# .NET Core 2.0 solutions.

This was done on a Windows 10 OS but the steps should be easily transferable to other platforms.

Firstly, my solution is called XunitTestDemo and the root directory that I am working from is also called XunitTestDemo.

So, create a new directory called XunitTestDemo and go to that directory in the command line.
Run the following commands.

dotnet new classlib -lang f# -o TestDemo.Core
dotnet new xunit -lang f# -o TestDemo.Tests
cd TestDemo.Tests
dotnet add reference ..\TestDemo.Core\TestDemo.Core.fsproj
code ..\

These set up a test project called TestDemo.Tests and a project for housing production code called TestDemo.Core. We also have now set up a reference from TestDemo.Tests to TestDemo.Core and opened VsCode in our XunitTestDemo directory.

In Vs Code, follow the steps below to create a new directory called .vscode

Next go into TestDemo.Core.fsproj. I found a slight issue with .NET Core 2.0 classlib projects in F# which means that the FsAutoComplete doesn’t work properly.This isn’t an issue with Ionide but, rather, other upstream services that it uses.
You can get more information about this here
To work around this, I had to change the TargetFramework in TestDemo.Core.fsproj to be netcoreapp2.0 as in the steps below.


With this done, lets add an F# module that we can later write a test for. Go into Library.fs and replace its contents with:

module TestDemo.Core.Calculator

let add x y = x + y

Now run the following in the command line from the XunitTestDemo\TestDemo.Core directory.

\TestDemo.Core>dotnet restore
dotnet build

And the same from the XunitTestDemo\TestDemo.Tests directory.

\TestDemo.Tests>dotnet restore
dotnet build

Back in VsCode reload the window


Now lets write a test that will fail. Go into Tests.fs in the TestDemo.Tests project and replace its contents with below:

module TestDemo.Tests.CalculatorTest
open System
open Xunit
open TestDemo.Core

[]
let ``test add`` () =
    Assert.Equal(5, Calculator.add 3 10)

Now we need to set up our VsCode test task. So, create a file called tasks.json in the .vscode folder that you created earlier.

Add the below content to it:

{
    "version": "2.0.0",
    "tasks": [
        {
            "taskName": "Tests",
            "command": "dotnet",
            "type": "shell",
            "args": [
                "test"
            ],
            "presentation": {
                "reveal": "silent"
            },
            "problemMatcher": "$msCompile",
            "group": {
                "kind": "test",
                "isDefault": true
            }
        }
    ]
}

This task calls out to .NET Core 2.0 CLI to run our tests. The above configuration also makes it the default testing task for our solution. (“isDefault”: true)

To make things easier, lets create a keyboard shortcut to run the default testing task. So go into Keyboard Shortcuts preferences:

Click into keybindings.json and add the following custom key binding.

.....
{   "key": "ctrl+shift+r",              
    "command": "workbench.action.tasks.test" 
}
...

Save everything and now ctrl+shift+r will run the default testing task which we have configured to be our testing task earlier which will run all tests in our solution.

In order for the .NET CORE 2.0 CLI to look for and run all our xunit tests including future ones that you may add, we need to create a Solution and add our two projects to it. This is done with the following commands, again from the XunitTestDemo directory on the command line.

XunitTestDemo>dotnet new sln
XunitTestDemo>dotnet sln XunitTestDemo.sln add TestDemo.Core\TestDemo.Core.fsproj
XunitTestDemo>dotnet sln XunitTestDemo.sln add TestDemo.Tests\TestDemo.Tests.fsproj

Back in VsCode, reload the window again as before from the command palette, ctrl+shift+p


Open up the integrated terminal that will show our test results.

Now go back into Tests.fs and hit ctrl+shift+r to run all our tests. This command can actually be run from anywhere within the VsCode instance that is open for our solution.

Our test will be discovered and run and we can see the results in the integrated terminal.

Lets fix our broken failing test so it is asserting the correct result – not the correct TDD approach but it serves as an example.

 Assert.Equal(13, Calculator.add 3 10)

Then without doing any building our reloading of the window or anything, we can hit ctrl+shift+r again and see our successful test run in the integrated terminal.

We are now set up for a nice work flow to run our tests with ease as we make changes.

The source code for this demo is available on my Github here

Two Tetromino Tetris with Fable and F#

In my last post, I talked about my early adventures Fable and building a memory tiles game.

Recently I have been exploring Fable further and, in particular, using it to interact with the Javascript canvas API. I’ve been wanting to try out building a version of Tetris for a while now. I used to love playing it on the Gameboy many years ago. Fable afforded me the perfect tool to build this game in the beautiful language of F#.

There is a video snippet above of my implemented game in action. This blog won’t go into every detail of the code as it is available here but I wanted to go through a few code snippets here that may help other people looking to build a game involving game animation frames and using the canvas API with Fable and F#.

What’s a tetromino and why two tetrominoes and not the full thing?

A tetromino is the name given to each of the shapes in the Tetris game. Each tetromino also has a number or rotations that it can go through. There are more details about Tetris tetrominoes here.

I think of this version as a version 1. I wanted to get as much of a fully featured game implemented as I could in a pretty short time frame – while I had some summer vacation time. I hope to return to this at some point and add more shapes and also improve the rotation algorithm – unlike the original game, my rotation algorithm simply prevents rotations when blocks are in the way although it does handle wall kicks. I chose the I-Block along with its rotations and the T-Block along with its rotations as the two tetrominoes that I would use in this initial Tetris implementation.

The domain modelling

I modeled the gameboard as a map of row indexes to rows with each row itself being a map of the block left X position indexes to blocks. Blocks are the primitives that tetrominoes are built from. I wanted to capture the states that a gameboard can be in using the F# type system. A gameboard that is in a resting state has no moving tetromino and a gameboard in motion has a moving tetromino. The main game engine processes these gameboard states so I made them distinct using a Discriminated Union – a DU.

60   type LeftBlockPosition = float 
61    
.......
65   and RowData = Map<LeftBlockPosition,Block> 
66    
67   type RowBottomPosition = float 
68    
69   type GameboardInMotion = { 
70       Height : float 
71       Width : float 
72       BlockSize : float 
73       MovingTetromino : Tetromino 
74       Rows : Map<RowBottomPosition, RowData> 
75   } 
76    
77   type RestingGameboard = { 
78       Height : float 
79       Width : float 
80       BlockSize : float 
81       PlacedTetromino : Tetromino 
82       Rows : Map<RowBottomPosition, RowData> 
83   } 
84    
85   type Gameboard =  
86   | GameboardInMotion of GameboardInMotion 
87   | RestingGameboard of RestingGameboard 
88    

A block is modeled as a an F# record.

3    type Block = { 
4        BottomX : float 
5        BottomY : float 
6        Color : string 
7    } 

The tetrominoes are modelled as a DU also with each case representing a tetromino rotated in a particular direction. Each tetromino also has tetromino detail about the rows of blocks that it comprises of.

19   type TetrominoRow = { Blocks : Block list } 
...........
36   type TetrominoDetail = { TetrominoRows : TetrominoRow list } 
37    
38   type Tetromino =  
39   | StraightUp of TetrominoDetail 
40   | StraightRight of TetrominoDetail 
41   | StraightDown of TetrominoDetail 
42   | StraightLeft of TetrominoDetail 
43   | TShapeUp of TetrominoDetail 
44   | TShapeRight of TetrominoDetail 
45   | TShapeDown of TetrominoDetail 
46   | TShapeLeft of TetrominoDetail 

Valid key presses are also modeled using a DU and using designing with capabilities to prevent the creation of an invalid key press. I learned about designing with capabilities from Scott Wlaschin – Designing with Capabilities and from reading Scott’s new book:
Domain Modeling Made Functional

89   type KeyCode = float 
90    
91   type GameControl =  
92       | Up 
93       | Left 
94       | Right 
95    
96   type ValidKeyPress = private ValidKeyPress of GameControl * KeyCode  
97    
98   let (|ValidKeyPress|) validKeyPress =  
99       match validKeyPress with  
100      | ValidKeyPress(control,keyCode) -> ValidKeyPress (control, keyCode) 
101   
102  module ValidKeyPress =  
103       
104      let toValidKeyPress keyCode = 
105          match keyCode with 
106          | 37. -> Some <| ValidKeyPress (Left, 37.) 
107          | 38. -> Some <| ValidKeyPress (Up, 38.) 
108          | 39. -> Some <| ValidKeyPress (Right, 39.) 
109          | _ -> None

Working with the canvas API

The Fable.Import namespace provides a thin wrapper over the Javascript DOM API.

I get a reference to my actual canvas div with the following:

9    let tetrisView = Browser.document.getElementById("tetris-view") :?> Browser.HTMLCanvasElement 
10   let ctx = tetrisView.getContext_2d() 

To render rows of blocks, I used fillRect as follows:

27       let renderRow blockSize (blocks:Map<LeftBlockPosition,Block>) =  
28           blocks |> Map.toSeq |> Seq.map snd |> Seq.iter (fun block ->  
29               ctx.fillStyle <- U3.Case1 block.Color 
30               ctx.fillRect(block.BottomX, block.BottomY - blockSize, blockSize, blockSize)) 

To clear the canvas area before each re-render of the gameboard, I used clearRect:

 ctx.clearRect(0., 0., tetrisView.width, tetrisView.height) 

Getting the game in motion!

Using .Net events and also the Javascript interval API (wrapped nicely by Fable), I was able to set up a repeating game frame clock. So, each time the time interval passes, an event is triggered causing a new gameboard to be evaluated from the current gameboard and from any user game control input and this new game board is then rendered.

46   let frameChangeEvent =  new Event<Gameboard>() 
47    
48   let mutable private frameClockId = 0. 
49    
50   let startFrameClock() =  
51       frameClockId <- Browser.window.setInterval((fun() ->  
52               match lastRenderedGameBoard with  
53               | GameboardInMotion _ 
54               | RestingGameboard _ -> frameChangeEvent.Trigger lastRenderedGameBoard 
55               )  
56           , 150.) 

I handle user input in a separate UserGameController module using the wrapper that Fable gives over DOM event handling:

1    module Tetris.UserGameController 
2     
3    open Fable.Core 
4    open Fable.Import 
5    open Tetris.Definitions 
6     
7    Node.require.Invoke("core-js") |> ignore 
8     
9    let private keyPressed= ref (None:ValidKeyPress option) 
10    
11   let private handleKeyDown keyCode =  
12       match ValidKeyPress.toValidKeyPress keyCode with 
13       | Some (ValidKeyPress _ as vkp) -> 
14           keyPressed := Some vkp 
15       | None -> () 
16    
17   let private handleKeyUp keyCode =  
18       match !keyPressed with 
19       | Some (ValidKeyPress(_, currentlyPressed)) when keyCode = currentlyPressed ->  
20           keyPressed := None 
21       | _ -> () 
22     
23     
24   Browser.window.addEventListener_keydown (fun e -> handleKeyDown e.keyCode :> obj) 
25   Browser.window.addEventListener_keyup (fun e -> handleKeyUp e.keyCode :> obj) 
26    
27   let getKeyPressed() = !keyPressed 
28           

The game engine

The game engine is essentially a state machine. From the gameboard it is given and the current user input (if any), it works out what the next gameboard should be. There is a fair bit of logic in there around things like:
– whether a rotation is allowed,
– what the next rotation is for the current tetromino,
– whether the tetromino can move left or right,
– whether the tetromino should rest on blocks below
etc.

With the domain modeled using the F# type system and immutable DUs and records, these transitions became simpler to reason about. As an example, after it is determined if a rotation is possible (if the up arrow is currently pressed), the engine works out which way the tetromino can move. I created what I called a TransitionReferee for this. This is somewhat verbose but I wanted the logic and rules to be self documenting as much as possible. The snippet from the TransitionReferee is below to give an example of what I mean.

21   module TransitionReferee =  
22    
23       type RefereeDecision =  
24           | MoveHorizontallyAndVertically of GameboardInMotion 
25           | MoveVerticallyOnly of GameboardInMotion 
26           | MoveVerticallyOnlyAndRestOnBottom of GameboardInMotion 
27           | MoveVerticallyOnlyAndRestOnBlockBelow of GameboardInMotion 
28           | MoveAndRestOnBlockBelow of GameboardInMotion 
29           | MoveAndRestOnBottom of GameboardInMotion 
30           | CheckForCompletedRowsAndReleaseAnotherBlock of RestingGameboard 
31            
32       let blocksOverlapHorizontally block1XPos block2XPos blockSize = 
33           block1XPos > block2XPos - blockSize && block1XPos < block2XPos + blockSize 
34        
35       let tetrominoRowOverlapsWithExistingBlocks (horizontalTransitionDirection:HorizontalTransitionDirection) blockSize (tetrominoRow:TetrominoRow) row =  
36            
37           tetrominoRow.Blocks 
38           |> List.exists (fun tetrominoBlock -> 
39               row  
40               |> Map.exists (fun existingX  _ ->  
41                   blocksOverlapHorizontally existingX (tetrominoBlock |> nextXPosition horizontalTransitionDirection) blockSize)) 
42    
43       let otherRowsInRangeContainingBlocksInTheWay direction (gameboard:GameboardInMotion)  =  
44           //compare gameboard rows when all tetromino blocks have been removed 
45           gameboard.MovingTetromino.TetrominoRows 
46           |> List.fold (fun gameboardRows tetrominoRow -> 
47                gameboardRows 
48                |> Map.tryFind tetrominoRow.BottomY  
49                |> Option.map (fun gameboardRow ->  
50                   tetrominoRow.Blocks 
51                   |> List.fold (fun row b -> row |> Map.remove b.BottomX) gameboardRow) 
52                |> function | Some gameboardRowWithTetrominoBlocksRemoved -> gameboardRows |> Map.add tetrominoRow.BottomY gameboardRowWithTetrominoBlocksRemoved | None -> gameboardRows 
53           ) gameboard.Rows 
54           |> fun gameboardRows -> 
55               gameboardRows 
56               |> Map.toSeq 
57               |> Seq.exists (fun (rowY, gameboardRow) -> 
58                   gameboard.MovingTetromino.TetrominoRows  
59                   |> Seq.exists (fun tetrominoRow ->  
60                       (rowY > ((tetrominoRow.TopY gameboard.BlockSize) + transitionDistance) &&  
61                        rowY < (tetrominoRow.BottomY + transitionDistance) + (tetrominoRow.Height gameboard.BlockSize) && 
62                        tetrominoRowOverlapsWithExistingBlocks direction gameboard.BlockSize tetrominoRow gameboardRow))) 
63    
64       let decideTransition (direction:HorizontalTransitionDirection) (gameboard:Gameboard) =  
65           match gameboard with 
66           | GameboardInMotion gameboard -> 
67               let otherRowsInRangeContainingBlocksInTheWay direction  = otherRowsInRangeContainingBlocksInTheWay direction gameboard                     
68                
69               let tetrominoShouldMoveToRestOnBlocksBelow direction (gameboard:GameboardInMotion) =  
70                   gameboard.MovingTetromino.TetrominoRows 
71                   |> Seq.exists (fun tetrominoRow -> 
72                       gameboard.Rows 
73                       |> Map.tryFind (tetrominoRow.BottomY + transitionDistance + gameboard.BlockSize)  
74                       |> Option.map (fun row ->  
75                           tetrominoRowOverlapsWithExistingBlocks direction gameboard.BlockSize tetrominoRow row)  
76                       |> function | Some b -> b | None -> false 
77                   ) 
78                    
79               if otherRowsInRangeContainingBlocksInTheWay direction then 
80                   if (gameboard.MovingTetromino.TetrominoRows.[0].BottomY + transitionDistance) = gameboard.Height then  
81                       MoveVerticallyOnlyAndRestOnBottom gameboard 
82                   elif tetrominoShouldMoveToRestOnBlocksBelow NoHorizontalTransition gameboard then 
83                           MoveVerticallyOnlyAndRestOnBlockBelow gameboard 
84                   else MoveVerticallyOnly gameboard 
85               else  
86                   if (gameboard.MovingTetromino.TetrominoRows.[0].BottomY + transitionDistance) = gameboard.Height then  
87                       MoveAndRestOnBottom gameboard 
88                   elif tetrominoShouldMoveToRestOnBlocksBelow direction gameboard then     
89                       MoveAndRestOnBlockBelow gameboard 
90                   else MoveHorizontallyAndVertically gameboard 
91                    
92           | RestingGameboard gameboard -> CheckForCompletedRowsAndReleaseAnotherBlock gameboard 

Conclusion

I hope the code snippets that I have shown here can be of some help to others who are exploring Fable. The full source code is available here:
Also, the current version of this Two Tetromino Tetris game can be played here.

Early Fable Adventures – Building A Memory Tiles Game

Getting aquianted with fable

Just about a month ago, I had the great pleasure of attending F# eXchange 2017 in London. It was 2 days of wonderful F# indulgence with fantastic talks and workshops. It was also a great experience meeting some of the people who have pretty much been virtual mentors to me on my F# journey like Kit Eason and Scott Wlaschin. I did Kit’s pluralsight F# courses and Scott’s fsharp for fun and profit site is a constant source of learning for me so to get chatting with these guys in person was really cool.

Among all of these great talks and workshops was a talk by Alfonso García-Caro, about his Fable compiler. This is an F# to javascript compiler that hooks in really well with the javascript ecosystem. I’m lucky that in my job I am coding in F# across the full stack currently using websharper for our F# to javascript needs. So Alfonso’s talk about Fable really caught my attention. I couldn’t wait to get a bit of free time to dive in and try it out.

Getting up and running with Fable was very quick and easy thanks to this extremely helpful blog post by Krzysztof Cieslak. I started by simply trying out simple dom event handling. Out of the box, Fable has an API that appears to be a light F# wrapper around the javascript dom API.
This is accessed simply with

open Fable.Import

From here, the dom is at your finger tips through the eyes of F# through the module Fable.Import.Browser.

A little game to get my teeth into Fable

After playing around with some dom operations through Fable, I wanted something a bit more substantial to get my teeth into. Recently I was playing this common memory game with my 3 year old daughter. Its a game where you have a grid of cards with pictures on them where every picture will appear on exactly 2 cards. You lay them out randomly upside down. Then you take turns turning 2 cards over at a time. If you get matching pictures, you keep the cards but if there is no match, you turn the cards upside down again. At the end, the player with the most mathed cards wins.

I thought this would be a great game to implement with Fable so I could get started properly with this wonderful F# to javascript compiler. I simplified the game for my first version and built just a one player game. You get a grid of blacked out tiles which have hidden colors where every color will exist twice on the grid. Then you click (or tap if on a mobile device) on 2 tiles to uncover their colors. If they match, the tiles stay open permently until you start a fresh game. If they are not a match, the tiles are blacked out again the next time you click a new tile. This first version was enough to get me building something with Fable. In future versions, I plan to make it a bit more interesting by adding time challenges and levels with bigger grids among other ideas.

Dom operations through Fable to get up and running

There are a few basic things that I wanted to do with the dom for my game interaction. The following were enough for the first version of the game.

Creating a dom element with attributes

let tileDiv = Browser.document.createElement("div")
             tileDiv.className <- "col-3"
             let bc = match tile.Status with
                      | UnMatched -> tile.CoverColor
                      | AttemptingMatch -> tile.HiddenColor
                      | Matched -> tile.HiddenColor
             tileDiv.style.backgroundColor <- bc
             tileDiv.style.border <- "white solid 4px"

In the above, the Browser module is coming from the earlier Fable.Import. From this module, there is a wealth of dom related functions closely matching the standard javascript document API. Here I’m creating a div, setting its class name and a couple other properties including its border and also its background color which is a result of a pattern match to check the status of the corresponding tile in the backing model.

Adding a click event

Adding events is straight forward too. I found if I got stuck because of not knowing the function or type to use from Fable.Import.Browser, I could just look up the corresponding javascript dom function/element on the Mozilla Dom API reference and the corresponding Fable module/type/function was named similarly.
For the memory tiles game, I needed a way to add a click event to a, “Start Fresh Game” button to refresh the grid with new randomized tiles. This is shown below:

let startNewGameButton = Browser.document.createElement("button")
      startNewGameButton.addEventListener_click(fun _ -> startNewGameCallback() :> obj)
      startNewGameButton.innerText <- "Start Fresh Game"
      gameContainer.appendChild startNewGameButton |> ignore

Here, I create the button to start a new game of randomized tiles. I then add a click event which can take a regular F# function as a parameter. Here I’m passing a lambda which, when executed, will call a function called startNewGameCallback. The block of code shown here exists inside a render function in my View module and this render function takes the startNewGameCallback function as a parameter. The full source code for this is on my github MemoryTiles.fsx

I use the same Fable addEventListener_click function for handling the click event on each tile as shown below.

let eventHandler r c d = Func<Browser.MouseEvent, obj>(fun _ -> tileClickCallback r c gameBoard :> obj)
        tileDiv.addEventListener_click(eventHandler rowIndex cIndex tileDiv)

This takes a lambda wrapping another callback which has been passed to the render function in my View module. This eventually calls back to the main driver of the game – the tileClick function in my Controller module, but first let me just show the data modelling from the Model module to put this tileClick function in context.

F# typing goodness with Fable

Fable supports the standard F# data modelling constructs bringing us the F# type safety that we love so much!
For the games’ backing model, I used standard F# records and disciminated unions to represent the immutable game board which serves as a point in time state to render a point in time view and also to enable the generation of a another game board depending on user input and the value of its tiles. A tile itself is modelled as a record and the status of a tile along with the the current selection of tiles are modelled as DUs. So even though this is a game running as javascript, I have still been able to use F# types and F# immutability to express the domain and behaviour of the game. This is shown below. I added a GameBoard helper module for the state transistions of updating tiles and the selection. There is some localized mutability within the updateTile function but the function is still pure with an immutable game board going in and another one coming out. The updateSelected is also returning a new immutable game board.

type GameBoard = {
    Selection : Selection
    Board : Tile list list
}
and Tile = {
    Row : int
    Col : int
    HiddenColor : string
    CoverColor : string
    Status : TileStatus
}
and TileStatus = UnMatched | AttemptingMatch | Matched
and Selection = NoneSelected | OneSelected of Tile | TwoSelected of Tile * Tile
 
module GameBoard = 
    let updateTile r c t gb = 
        let updatedRow = gb.Board.[r] |> List.toArray |> (fun arr -> arr.[c] <- t; arr) |> List.ofArray
        {
            gb with
                Board = gb.Board |> List.toArray |> (fun arr -> arr.[r] <- updatedRow; arr) |> List.ofArray
        }
 
    let updateSelected s gb = { gb with Selection = s}

Using standard .Net events for to trigger view rendering

.Net event handling is one of my favourite features of the .Net platform and, in particular, the way it is implemented in F#. Fable allows us to use standard .Net event triggering and handling. I designed the game using a version of the model, view, controller pattern. I wanted to keep my view decoupled from the model but I still needed a way for it to be rendered whenever the game board changed. I also wanted it to remain as decoupled as possible from the controller module. The controller module passes the main engine of the game, its tileClick function, as a function parameter to the view but the view doesn’t know anything about its implementation. This is similar for the callback to start a fresh game. In order for the view to be rendered and re-rendered, I set up a an event in the in the Model module as follows.

let modelChangeEvent = (new Event<GameBoard>())

In the Controller module, there is a an initialise function which starts everything off. It publishs an observation to the above event and adds a listener, which takes a game board as a parameter and which will call render on the View whenever the a modelChangeEvent is triggered.
A startGame() function, called by initialise, simply triggers a modelChangeEvent to trigger the initial rendering of the game.

let startGame() = modelChangeEvent.Trigger (Model.generateRandomModel 4)
 
let initialise() = 
    Model.modelChangeEvent.Publish.Add(fun gameBoard -> View.render tileClick startGame gameBoard)
    startGame()

Main game logic with F# pattern matching

The main game logic is in the tileClick function of the Controller module. It receives a game board and a row and column for the clicked tile and, based on these, it determines a new game board to be created and triggers the modelChangeEvent so that the View.render function is called to re-render with the new game state.For some cases, no event is triggered and the view is not re-rendered e.g. if the same tile is clicked multiple times in succession. Standard F# pattern matching can be used here and the full function is below.

let tileClick tileRow tileCol (gameBoard: GameBoard) = 
    let board = gameBoard.Board
    let tile = board.[tileRow].[tileCol] 
    let lastSelection = gameBoard.Selection
    if tile.Status = Matched then ()
    else
        match lastSelection with
        | TwoSelected(t1, t2) when t1.Status = Matched && t2.Status = Matched && tile <> t1 && tile <> t2->
            gameBoard
            |> GameBoard.updateTile tile.Row tile.Col { tile with Status = AttemptingMatch }
            |> GameBoard.updateSelected (OneSelected { tile with Status = AttemptingMatch })
            |> modelChangeEvent.Trigger
        | TwoSelected(t1, t2) when t1.Status = Matched && tile <> t1 && tile <> t2 -> 
            gameBoard
            |> GameBoard.updateTile tile.Row tile.Col { tile with Status = AttemptingMatch }
            |> GameBoard.updateTile t2.Row t2.Col { t2 with Status = UnMatched }
            |> GameBoard.updateSelected (OneSelected { tile with Status = AttemptingMatch })
            |> modelChangeEvent.Trigger
        | TwoSelected(t1, t2) when t2.Status = Matched && tile <> t1 && tile <> t2 -> 
            gameBoard
            |> GameBoard.updateTile tile.Row tile.Col { tile with Status = AttemptingMatch }
            |> GameBoard.updateTile t1.Row t1.Col { t1 with Status = UnMatched }
            |> GameBoard.updateSelected (OneSelected ({ tile with Status = AttemptingMatch }))
            |> modelChangeEvent.Trigger
        | TwoSelected(t1, t2) when tile <> t1 && tile <> t2 -> 
            gameBoard 
            |> GameBoard.updateTile t1.Row t1.Col { t1 with Status = UnMatched }
            |> GameBoard.updateTile t2.Row t2.Col { t2 with Status = UnMatched }
            |> GameBoard.updateTile tile.Row tile.Col { tile with Status = AttemptingMatch }
            |> GameBoard.updateSelected (OneSelected ({ tile with Status = AttemptingMatch }))
            |> modelChangeEvent.Trigger           
        | OneSelected t1 when t1.HiddenColor = tile.HiddenColor && tile <> t1 -> 
            gameBoard
            |> GameBoard.updateTile t1.Row t1.Col { t1 with Status = Matched }
            |> GameBoard.updateTile tile.Row tile.Col { tile with Status = Matched }              
            |> GameBoard.updateSelected (TwoSelected ({ t1 with Status = Matched },{ tile with Status = Matched }))
            |> modelChangeEvent.Trigger
        | OneSelected t1 when tile <> t1 -> 
            gameBoard
            |> GameBoard.updateTile tile.Row tile.Col { tile with Status = AttemptingMatch }              
            |> GameBoard.updateSelected (TwoSelected (t1, { tile with Status = AttemptingMatch }))
            |> modelChangeEvent.Trigger 
        | NoneSelected when tile.Status <> Matched -> 
            gameBoard
            |> GameBoard.updateTile tile.Row tile.Col { tile with Status = AttemptingMatch }              
            |> GameBoard.updateSelected (OneSelected ({ tile with Status = AttemptingMatch }))
            |> modelChangeEvent.Trigger
        | _ -> ()

Conclusion

I had loads of fun making this game and definitely want to add more to it. My daughter has been playing away with it and having great fun!
I’ll definitely be continuing on my Fable journey.
The full source code for this game is on my github:
MemoryTiles.fsx
Also the current version of the game can be played here

F# Unit Testing Simplified – Expecto with Visual Studio Code

This post is a slightly shorter follow on post to my last one, F# Has Won Me Over: Coming to .Net World from Outside .Net

In that post, I showed how to set up a basic F# development workflow using Visual Studio Code. It probably seemed a little overkill just to get simple tests up and running.I’m glad I took this longer approach though as, coming into .NET world, it made me aware of how the tools and F# projects fit together under the hood – something that wouldn’t be as clear if I went the all out IDE approach.

Since publishing that blog, I have gotten a lot of really helpful feedback from others in the F# community and I have taken a look at an F# testing tool called Expecto

The Ionide plugin for Visual Studio Code has a really nice integration for running tests using Expecto – it’s a whole lot simpler then the workflow I showed in my last post!

Following from my last post, lets add a different test project to test the MusicLibrary project and we’ll use Expecto this time to run our test.
Again, I’m running Visual Studio Code on Mac OSX in this example but the steps should be more or less the same for other operating systems.

So, back in Visual Studio Code, type cmd-shift-p to open the command palette
Type F# and select F#:New Project

Choose a console as this will give us a main entry point for Expecto to run tests.

You will be prompted for the name of the project directory.

Lets just call it MusicLibraryExpectoTests

You will then be prompted for the name of the project.

Again, MusicLibraryExpectoTests will be grand.

Now we need to add our Expecto dependencies with Paket.

So open up the newly creted MusicLibraryExpectoTests directory and open MusicLibraryExpectoTests.fsproj

Open the command palette again, cmd-shift-p
Type Paket and select Paket:Add NuGet Package (to current project)

Then type Expecto and Enter.

You will see, info in the Paket output terminal.

Afterwards, you should be able to search Expecto in the MusicLibraryExpectoTests.fsproj file and find something like

   
 ..\..\packages\Expecto\lib\net40\Expecto.dll
               

Repeat for
Expecto.BenchmarkDotNet
Expecto.FsCheck

After all this, our paket.references file within the MusicLibraryExpectoTests project should contain

FSharp.Core
Expecto
Expecto.BenchmarkDotNet
Expecto.FsCheck

Lets try out a hello world expecto test. So, open up MusicLibraryExpectoTests.fs which will have automatically been created for us when we created our MusicLibraryExpectoTests project.

Replace the contents of that file with the following:

module MusicLibraryExpectoTests

open Expecto

[<Tests>]
let tests =
  testCase "yes" <| fun () ->
    let subject = "Hello World"
    Expect.equal subject "Hello world"
                 "The strings should equal"


[<EntryPoint>]
let main args =
  runTestsInAssembly defaultConfig args

and save.
Here we have added one test case and a main function as an entry point for expecto to run our tests.
We can easily run our test simply as follows:
Open command palette, cmd-shift-p
Type Ex and choose Expecto:Run

In the expecto output terminal, we can see our failing test!

We can fix our failing test by changing that ‘w’ to upper case so our MusicLibraryExpectoTests.fs becomes:

module MusicLibraryExpectoTests

open Expecto

[<Tests>]
let tests =
  testCase "yes" <| fun () ->
    let subject = "Hello World"
    Expect.equal subject "Hello World"
                 "The strings should equal"

[<EntryPoint>]
let main args =
  runTestsInAssembly defaultConfig args

This time to run the tests, lets just use a shortcut, ctrl-f6
Now, our test passes and you should see this along with other output in the Expecto terminal output in Visual Studio Code:

[21:28:12 INF] EXPECTO?! Summary...
Passed:  1
	yes 
Ignored: 0
	Failed:  0
	Errored: 0

Now, we can use Expecto to test our addSongToLibrary function from the MusicLibrary project that I went through in my last post.
We need to link our MusicLibraryExpectoTests project to this library first. So, open the MusicLibraryExpectoTests.fsproj file again.

Then we can use the command palette, cmd-shift-p to add a project reference.

Choose MusicLibraryExpectoTests for the project to edit

and MusicLibrary as the project to reference

Your MusicLibraryExpectoTests.fsproj should now contain something like

    
ProjectReference Include="../../MusicLibrary/MusicLibrary/MusicLibrary.fsproj"

We can add our test for addSongToLibrary to MusicLibraryExpectoTests.fs as follows:

module MusicLibraryExpectoTests

open Expecto
open MusicLibrary

[<Tests>]
let tests =
  testList "test group" [
    testCase "yes" <| fun _ ->
        let subject = "Hello World"
        Expect.equal subject "Hello World"
                    "The strings should equal"

    testCase "addSongToLibrary adds song to library" <| fun _ ->
        let expected = ["Sir Duke";"Superstition"]   
        Expect.equal expected (addSongToLibrary ["Superstition"] "Sir Duke")
                    "The library list should contain the new song"
    ]

[<EntryPoint>]
let main args =
  runTestsInAssembly defaultConfig args

Now, we can run the tests with ctrl-F6

And in the Expecto terminal output in Visual Studio code,
you should see something like this along with other output

Passed:  2
	test group/yes ....
       ....
	test group/addSongToLibrary adds song to library [/Users/tom/Dropbox/software-
Ignored: 0
	Failed:  0
	Errored: 0

Conclusion

There is a lot more you can do with Expecto. I have just scratched the surface here but, even with the basics here, you can very quickly create and run test cases from within Visual Studio Code. It’s definitely a tool that I will be using a lot!

F# Has Won Me Over: Coming to .Net World from Outside .Net

F# is a language that was sitting in the corner calling to me for a long time tempting me to go take a look at it. I watched Scott Wlaschin’s fantastic talk on Functional Programming Design Patterns some time ago. This talk is a walk through of common FP design patterns with the example code being in F#. Scott put together this talk so well that it is not a blocker to getting the most from the talk if you don’t have any previous knowledge of F#. At the same time, coming from mostly programming in Scala professionally, I couldn’t help but admire the beauty of the F# code in his examples. So I had a quick look further at some F# code out there. Things like a simple syntax using whitespace, automatic currying, nice concise representations of Algebraic Data Types caught my eye immediately.

Over the Christmas holidays I dived into F# by taking courses on FSharp TV and by going through content from Scott’s wonderful blog Fsharp For Fun And Profit.

F# has quickly become my favourite language to code in along with Haskell. Along the way though, there were some stumbling blocks getting used to the .Net world. Most of these could have been avoided if I just used the Xamarin Studio IDE. However, I’m glad I didn’t and took a little pain along the way as it made be explore the .Net and F# ecosystem. I did start to use Visual Studio Code which is really a text editor with a load of great plugins out there for different languages. Its lightweight enough that you still have to find out what’s happening under the hood a bit with your F#  .Net projects but, at the same, it does make things like creating projects with common templates, building and adding references to existing projects a lot less painful. Incidentally, there is now a Haskell plugin for Visual Studio Code which uses Intero. This is very exciting indeed and I can’t wait to try it out!

How do I code in F# on a mac?!

Yep this is a question I had for a while too. That is until I discovered Mono, an open source .Net framework which is cross platform.
I found the best way to get F# set up on OSX was to install Mono but to actually use the installer that can be downloaded here. I tried installing the homebrew way first but this seems to be missing some .Net libraries. For example, one that is needed for System.Drawing. I uninstalled my homebrew mono installation and installed from the Mono download that I linked to above, and I was then able to build and draw lovely spirographs from the FSharp TV, Introduction to F# course.

How do I create an F# project?

This was a question I had too. I wanted to simply create a project with a common folder structure. I was looking for something similar to lein new in Clojure or stack new in Haskell. A great tool for this is Forge. The Visual Studio Code ionide plugin integrates with Forge to make it really easy to create new projects through the command palette in Visual Studio Code. I demo this further down.

How do I manage dependencies?

The tool for this is Paket which uses the Nuget package manager under the hood. Again, Visual Studio Code has a plugin to integrate with Paket, Ionide-Paket

How do I build an F# project

FAKE is a very popular build tool for F# and allows you to specify your build tasks through a build.fsx file using and F# DSL. Visual Studio Code has a plugin to integrate with this too as part of its ionide suite, Ionide FAKE This is demoed further down in this blog too.

How do I run a .exe on Mac!

Some of these tools I have mentioned along with the nunit testing tool (which I demo further down) require the running of a .exe to perform tasks. If the .exe is one that doesn’t run directly on Mac OS or Linux, usually it can be run using

mono name-of-your-executable.exe

once mono is installed and on your path and once name-or-your-executable.exe is actually a file that can be executed. It may seem like a simple thing but it is important to know as there are resources out there that describe how to use .Net tools assuming you are on a Windows machine.

Demo Time: TDD with F#

As there are resources out there about setting up F# with Mono and Visual Studio Code, there’s no need to re-iterate them here so I will assume that you managed to get those set up. If you have questions, feel free to comment on this blog.
My main stumbling block coming from outside the .Net world was simply setting up a unit test project and linking this to a production code project (by production code, I mean implementation code).
Lets go through that here:

So in Visual Studio Code, from an empty directory, open command palette with shift-command-p and type F#.

Then select New Project.

You will be prompted to select the type of project.

Choose classlib for our production code.
You will then be prompted to choose the project directory.

Lets specify a directory called MusicLibrary. So type in MusicLibrary, hit enter and you will be prompted to provide a project name. Lets call this MusicLibrary too.

After a second or so, you should eventually see that the ionide plugin has created three directories, .packet, MusicLibrary and packages. It will have also created a build.fsx file and a build.sh file so that we can build our new MusicLibrary project with FAKE.

In the MusicLibrary directory, you will find a newly created MusicLibrary.fs file.

This is where we are going to put our production code after we write a test for it.
For now, delete everything from there and we are going to add a function to test called addSongToLibrary which will eventually take a list of existing song titles and a new song title and return a list of song titles containing our the existing ones and our new title. For now, it just returns an empty list until we have our test ready. The contents of the MusicLibrary.fs file can be replaced with:

module MusicLibrary

let addSongToLibrary existingSongs newSong = []

Now, we should be able to build this right?. Lets give it ago.

Open the Visual Studio command palette again and type FAKE.

Select Build

You will be prompted for a FAKE build task to run.

Select build.

Now we get an error:

If you look down at the output window in Visual Studio Code, you will see something like
build.sh: line 34: syntax error: unexpected end of file

We need to convert the dos .sh file to into unix format. There is a tool for this on the Mac App Store dos2unix.

Install that.
In the terminal go into the parent directory of your MusicLibrary directory where build.sh exists and run dos2unix on the build.sh file.

dos2unix build.sh
dos2unix: converting file build.sh to Unix format...

Now follow the steps earlier to try and do a FAKE build in visual studio code.
In the output in visual studio code, you should see output about using paket to get any needed dependencies and also about the creation of dlls.
From my understanding Dlls in .Net are like jar files in the jvm world and they are the binaries created as a result of compiling F# code. The FAKE build will now have created a build directory and put the dlls in there.

You will see a MusicLibrary.dll in there.

Back in the MusicLibrary directory there is also a MusicLibrary.fsproj file which FAKE uses to find out things it needs for the build. When we write our test, we will see how we can add a reference to the MusicLibrary.dll into our .fsproj file for our unit test project. If you look in build.fsx, you will see a reference to these .fsproj files for FAKE.

let appReferences  =
    !! "/**/*.csproj"
    ++ "/**/*.fsproj"

Lets set up our test project so we can test our addSongToLibrary function!

To test our addSongToLibrary function we can set up a MusicLibraryTest project. Follow the same steps as we did for creating the MusicLibrary project in visual studio code except for the prompt to choose library type, choose fsunit

After, you should see a newly created MusicLibraryTest directory.

If you go into that directory, you will see that there has been a MusicLibraryTest.fs file created for us containing:

module MusicLibraryTest

open NUnit.Framework
open FsUnit

[<Test>]
let ``Example Test`` () =
    1 |> should equal 1

There are 2 libraries imported here for unit testing, NUnit.Framework and FsUnit.
This is where paket comes in for our test dependencies. If you go into the paket.references file within the MusicLibraryTest directory you will see

FSharp.Core
FsUnit

So, we need to link our MusicLibraryTest project to our MusicLibrary.fsproj so that we can test our addSongToLibrary function. This is taken care of by add a reference to the MusicLibrary.fsproj in the MusicLibraryTest.fsproj.

Open up the MusicLibraryTest.fsproj file.
Now, open visual studio command palette again.

Select Add Project Reference.
Then choose MusicLibraryTest as the project that you want to edit

Then choose MusicLibrary as the reference

Now, somewhere in the MusicLibraryTest.fsproj, there will be a newly created reference to the MusicLibray.fsproj. Search the MusicLibraryTest.fsproj for MusicLibrary.fsproj.

Now we can reference our MusicLibrary module and call the addSongToLibrary function.
Back in the MusicLibraryTest.fs file, we can import the MusicLibrary module which contains our addSongToLibrary function and lets write a test to test adding a song title.

Replace the contents of MusicLibraryTest.fs with:

module MusicLibraryTest

open NUnit.Framework
open FsUnit

open MusicLibrary

[<Test>]
let shouldAddASong () =
    ["Sir Duke";"Superstition"] 
    |> should equal (addSongToLibrary ["Superstition"] "Sir Duke")

How do I run my test!

First of all lets create our MusicLibraryTest.dll. This is done the same way that we created MusicLibrary.dll before by running the FAKE build in visual studio code. After running the build, there should be a MusicLibraryTest.dll in your build directory.


Actually getting tests to run was a stumbling block for me. To run tests, a FAKE task can be created in build.fsx. I will show how to do that in a little bit. First I will show how to run more manually using an nunit test runner.
The NUnit3 test runner can be downloaded as a zip file here.
To make this work with a FAKE task a bit later, first create a directory tools/Nunit in the root folder in visual studio code that you have your MusicLibrary and MusicLibraryTest projects in.
Then download NUnit.Console-3.5.0.zip into there.


Then unzip it.

Now we can use the nunit3-console.exe to run our test.
In the terminal, go into the tools/NUnit folder.
Make the nunit3-console.exe executable:

chmod 755 nunit3-console.exe

We can run our test with the command:

mono nunit3-console.exe ../../build/MusicLibraryTest.dll

This should output our failing test result:

NUnit Console Runner 3.5.0
Copyright (C) 2016 Charlie Poole

Runtime Environment
   OS Version: MacOSX 16.1.0.0
  CLR Version: 4.0.30319.42000

Test Files
    ../../build/MusicLibraryTest.dll


Errors and Failures

1) Failed : MusicLibraryTest.shouldAddASong
  Expected is <Microsoft.FSharp.Collections.FSharpList`1[System.Object]>, actual is <Microsoft.FSharp.Collections.FSharpList`1[System.String]>
  Values differ at index [0]
at FsUnit.TopLevelOperators.should[a,a] (Microsoft.FSharp.Core.FSharpFunc`2[T,TResult] f, a x, System.Object y) [0x0004e] in :0
at MusicLibraryTest.shouldAddASong () [0x0003d] in :0

Run Settings
    DisposeRunners: True
    WorkDirectory: /Users/tom/Dropbox/software-development/fsharp/NUnitDemo/tools/Nunit
    ImageRuntimeVersion: 4.0.30319
    ImageRequiresX86: False
    ImageRequiresDefaultAppDomainAssemblyResolver: False
    NumberOfTestWorkers: 8

Test Run Summary
  Overall result: Failed
  Test Count: 1, Passed: 0, Failed: 1, Inconclusive: 0, Skipped: 0
    Failed Tests - Failures: 1, Errors: 0, Invalid: 0
  Start time: 2017-01-08 13:40:33Z
    End time: 2017-01-08 13:40:33Z
    Duration: 0.142 seconds

Now lets integrate this into FAKE.

In the build.fsx file, add the following near the top underneath
open Fake

add

open Fake.Testing

so you now have

open Fake
open Fake.Testing

Add our NUnitTest task underneath the Target “Deploy” block.

let testDlls = !! (buildDir + "*Test.dll")

Target "NUnitTest" (fun _ ->
  testDlls
    |> NUnit3 (fun p -> p)

)

So we have:

Target "Deploy" (fun _ ->
    !! (buildDir + "/**/*.*")
    -- "*.zip"
    |> Zip buildDir (deployDir + "ApplicationName." + version + ".zip")
)

let testDlls = !! (buildDir + "*Test.dll")

Target "NUnitTest" (fun _ ->
  testDlls
    |> NUnit3 (fun p -> p)

)

Also add NUnitTest to the build order so the end of your build.fsx file should be

// Build order
"Clean"
  ==> "Build"
  ==> "NUnitTest"
  ==> "Deploy"

// start build
RunTargetOrDefault "Build"

Open Visual Studio Code command palette and type FAKE as before

Choose FAKE: Build

Now you should see our new NUnitTest task so select that.

This will fail because of our failing test.

The output pane in visual studio code will have the results of the nunit3-console.exe runner

1) Failed : MusicLibraryTest.shouldAddASong
  Expected is <Microsoft.FSharp.Collections.FSharpList`1[System.Object]>, actual is <Microsoft.FSharp.Collections.FSharpList`1[System.String]>
  Values differ at index [0]
at FsUnit.TopLevelOperators.should[a,a] (Microsoft.FSharp.Core.FSharpFunc`2[T,TResult] f, a x, System.Object y) [0x0004e] in :0
at MusicLibraryTest.shouldAddASong () [0x0003d] in :0

Lets make the test pass!!

Go back to the MusicLibrary.fs file and make the test pass by replacing its contents with:

module MusicLibrary

let addSongToLibrary existingSongs newSong = newSong :: existingSongs

In Visual Studio Code, use the command palette to run FAKE: Build selecting build as before and then  FAKE: Build selecting NUnitTest.

Looking through the output in visual studio code we can now see our passing test report:

Test Run Summary
  Overall result: Passed
  Test Count: 1, Passed: 1, Failed: 0, Inconclusive: 0, Skipped: 0
  Start time: 2017-01-08 13:46:29Z
    End time: 2017-01-08 13:46:29Z
    Duration: 0.132 seconds

Conclusion

Hopefully this has helped people to get started with the F# and .Net ecosystem and get up and running quickly in this amazing language.

Setting Up A Haskell Development Environment (Mac OS)

Since I started developing in Haskell, I have experimented with a few different setups. I started with Vim with no plugins and that, together with GHC in the terminal was my vanilla setup as I spent my first couple of months learning the basics of Haskell. I like to start off this way when learning a new language as it really forces me to commit the basics of the language and its syntax to memory.

As I learned more about the language and moved on to more advanced topics and more complex problems, I needed to take advantage of Haskell tooling to increase my productivity. Sometimes I find the tooling for Haskell can get a bad rep but I actually find it very good. Tools like ghc-mod,  hlint and stylish-haskell provide a lot of key features that you may be used to from working with IDEs – code completion, documentation, compile error and warnings and even suggestions to make your Haskell code more idiomatic. The tricky thing can be getting these tools integrated into your favourite editor or IDE.

I started with VIM plugins to integrate these tools with VIM and also played around with the Haskforce plugin for Intellij which is an excellent plugin. I finally settled on the Atom editor which makes integrating Haskell tools very simple and it also has a load of really great plugins to enhance your Haskell development experience.

In this post, I’m going to go through step by step how to set up a Haskell development environment using Stack (a Haskell build tool), ghc, ghc-mod and other wonderful Haskell tools, and integrating all this with the Atom editor.

To make this a bit more realistic and to make sure that I don’t miss anything, I’m stripping my laptop of any Haskell, Stack, ghc and other installations related to Haskell tooling. I will leave Atom installed but I’ll remove all my Haskell plugins and start from scratch. As I set up my environment from scratch, I will document everything with command line commands and screenshots. I am using a Mac with macOS Sierra.

Okay here goes…
Firstly, I use Homebrew for installing Stack.

Setting up Stack, Ghc and other Haskell tools

➜  ~ brew install haskell-stack
➜  ~ stack setup

This may take about 10 minutes and you will see something like the following output.

Using latest snapshot resolver: lts-7.13
Writing implicit global project config file to: /Users/tom/.stack/global-project/stack.yaml
Note: You can change the snapshot via the resolver field there.
Downloaded lts-7.13 build plan.
Fetched package index.
Populated index cache.
Preparing to install GHC to an isolated location.
This will not interfere with any system-level installation.
Downloaded ghc-8.0.1.
Installed GHC.
stack will use a sandboxed GHC it installed
For more information on paths, see 'stack path' and 'stack exec env'
To use this GHC and packages outside of a project, consider using:
stack ghc, stack ghci, stack runghc, or stack exec

We can now start up the Haskell compiler, ghc, in interactive mode, ghci
In other words lets crank up a Haskel REPL and try a Haskell expression:

➜  ~ stack ghci
Configuring GHCi with the following packages:
GHCi, version 8.0.1: http://www.haskell.org/ghc/  :? for help
Loaded GHCi configuration from /Users/tom/.ghci
Loaded GHCi configuration from /private/var/folders/tj/mtvt3dv57cq6kbzw8809_gs00000gn/T/ghci78459/ghci-script
ghci>  1 + 1
2

We can quit back out of ghci now

ghci>  :q

We can now use stack to set up the tools that will be the engine behind a lot of our Haskell development experience.

➜  ~ stack install ghc-mod hlint stylish-haskell

You will see something like

[1 of 2] Compiling Main             ( /Users/tom/.stack/setup-exe-src/setup-mPHDZzAJ.hs, /Users/tom/.stack/setup-exe-src/setup-mPHDZzAJ.o )
[2 of 2] Compiling StackSetupShim   ( /Users/tom/.stack/setup-exe-src/setup-shim-mPHDZzAJ.hs, /Users/tom/.stack/setup-exe-src/setup-shim-mPHDZzAJ.o )
Linking /Users/tom/.stack/setup-exe-cache/x86_64-osx/tmp-Cabal-simple_mPHDZzAJ_1.24.0.0_ghc-8.0.1 ...
ghc-paths-0.1.0.9: download

It will continue on and download all the packages it needs. This can take a while.

comonad-5: download
comonad-5: configure
polyparse-1.12: copy/register
cpphs-1.20.2: download
comonad-5: build
...
Progress: 54/71
...

You should eventually see something like

Copying from /Users/tom/.stack/snapshots/x86_64-osx/lts-7.13/8.0.1/bin/hlint to /Users/tom/.local/bin/hlint
Copying from /Users/tom/.stack/snapshots/x86_64-osx/lts-7.13/8.0.1/bin/stylish-haskell to /Users/tom/.local/bin/stylish-haskell

Copied executables to /Users/tom/.local/bin:
- ghc-mod
- ghc-modi
- hlint
- stylish-haskell

Stack has now added executables in /Users/tom/.local/bin (/Users/tom being my home directory or ~)

You can add this to your PATH environment variable. I do this by editing ~/.zshrc as I use Zsh for my shell. If you are using bash, you can edit .bashrc

In the line for export PATH=
add this to the start of your path
“/Users/tom/.local/bin:
except the /Users/tom part needs to be replaced with the path to your home directory.

Setting up Atom

Download and install the Atom editor. It can be downloaded from here

So lets crank up this beautiful and highly configurable editor!

To start adding our Haskell Atom packages, click “Install a Package” and then “Open Installer”

Search for haskell

Click “Install” on the following
language-haskell
haskell-ghc-mod
ide-haskell
autocomplete-haskell

These should be all you need to get going but there are also other great packages that are worth exploring.
For example, haskell-hoogle lets you get documentation from Haskell Hoogle through a context menu.

There shouldn’t be any other configuration needed.
Lets set up a Haskell Stack Hello World project and edit it in Atom.

Close Atom for now.

back in the terminal, we can create a Stack project called hello.

➜  ~ stack new hello

This will show something like this

Downloading template "new-template" to create project "hello" in hello/ ...

The following parameters were needed by the template but not provided: author-email, author-name, category, copyright, github-username
You can provide them in /Users/tom/.stack/config.yaml, like this:
templates:
  params:
    author-email: value
    author-name: value
    category: value
    copyright: value
    github-username: value
Or you can pass each one as parameters like this:
stack new hello new-template -p "author-email:value" -p "author-name:value" -p "category:value" -p "copyright:value" -p "github-username:value"

Looking for .cabal or package.yaml files to use to init the project.
Using cabal packages:
- hello/hello.cabal

Selecting the best among 9 snapshots...

* Matches lts-7.13

Selected resolver: lts-7.13
Initialising configuration using resolver: lts-7.13
Total number of user packages considered: 1
Writing configuration to file: hello/stack.yaml
All done.

You’ll see there that it prints out info about .cabal. Cabal is a Haskell build tool that Stack is built on top of.

So lets open this up in Atom and see what it looks like. My main pain point with Haskell and Atom was getting Atom to play nicely with ghc-mod through Stack. The following way of opening a Stack project in Atom is officially deprecated but I still find it the simplest way to open a Stack project in Atom and have it work with no hassle.

Go into the hello directory.

➜  ~ ls -l hello

Open Atom through Stack

➜  hello stack exec atom

Click on “Open a Project” and the the “Open a Project” button

Select your hello directory and click open.

To open the main.hs file that stack has generated for us:
cmd-p
and type in “main”

Select main.hs
You will see a haskell-ghc-mod warning appear.

This seems to be a side effect of using stack exec to open the Stack project in atom. This warning popup can be closed and ignored. I have found no bad effects of ignoring this warning anyway.

We can now see the main.hs open with our nice Haskell syntax highlighting.
I have gone ahead and typed “i” under the module declaration for and you can see the code complete for importing a module.

If I type “im” and tab, it inserts a template for module import. There a lot of these handy templates including data declarations do syntax, if then else etc

If I start typing out an import for Data.List, you can see auto complete of ghc-mod giving me my options.

I can also go ahead and start typing “put” into main and I get auto complete options again.

If I make a mistake and save, ghc-mod gives me my compile error in the bottom pane and also when I hover over the place where the error occurs.

So lets fix that and print “Hello World”

Now we can go back to our terminal and build this.

➜  hello stack build
Warning: File listed in hello.cabal file does not exist: README.md
hello-0.1.0.0: build (lib + exe)
Preprocessing library hello-0.1.0.0...
[1 of 1] Compiling Lib              ( src/Lib.hs, .stack-work/dist/x86_64-osx/Cabal-1.24.0.0/build/Lib.o )
Preprocessing executable 'hello-exe' for hello-0.1.0.0...
[1 of 1] Compiling Main             ( app/Main.hs, .stack-work/dist/x86_64-osx/Cabal-1.24.0.0/build/hello-exe/hello-exe-tmp/Main.o )
Linking .stack-work/dist/x86_64-osx/Cabal-1.24.0.0/build/hello-exe/hello-exe ...
Warning: File listed in hello.cabal file does not exist: README.md
hello-0.1.0.0: copy/register
Installing library in
/Users/tom/hello/.stack-work/install/x86_64-osx/lts-7.13/8.0.1/lib/x86_64-osx-ghc-8.0.1/hello-0.1.0.0-2MDzoFPW8yDJLgrpJYcMkC
Installing executable(s) in
/Users/tom/hello/.stack-work/install/x86_64-osx/lts-7.13/8.0.1/bin
Registering hello-0.1.0.0...

Stack creates an executable for us called hello-exe. This name is configured in hello.cabal in our hello directory.

We can run this executable now.

➜  hello stack exec hello-exe
hello world

Finally, that ghc-mod warning that was coming up in Atom:
cmd-, will bring up the settings pane.
Go into packages, haskell-ghc-mod and Settings and scroll down and check “Suppress GHC Package Path Warning”. However, due to the warning there, it might be better not to do this and to just close out of the ghc-mod warning popup with you open up a project.

Hopefully this guide has been useful. Enjoy playing with Atom and its packages for Haskell!

Additional Note

For existing projects, if they were built with stack that had a different lts-resolver, you can get problems with atom.Easiest thing there is to delete the .stack-work directory in the root directory of your project. In terminal run this command from the project root directory:

stack init --solver --force

this creates a new stack.yaml file with the lts-resolver for your installed stack. Removing .stack-work may cause a lengthy rebuild if the existing project has a lot of dependencies.
My projects have small numbers of dependencies at the moment so it hasn’t been a problem for me.
Then rebuild your project with

stack build

and open atom with

stack exec atom

from your project’s root directory as before.

Haskell div mod – Cyclical Division, Modulus Visualised

Reading Time: 8 mins
When I first came to integer division and the modulus operation in Haskell, I was thrown a bit of a curve ball, but a good curve ball at that. While Haskell does have two forms of integer division, one of those is a lot different from how I was used to thinking about integer division in other languages like Java and Scala. This actually comes in very handy for algorithms that cycle through ranges of values either left to right or right to left. However, as I was more used to the way it is done in Java and Scala, it took a bit of a mind-shift when I came to Haskell and saw another way to handle integer division and modulus.

One way of doing integer division in Haskell is with the quot and rem functions. They can be put together with the function quotRem and giving a tuple of the result and the remainder and this works like many would be used to from Java or some other languages.

ghci> let x = 8 :: Integer
ghci> let y = 3 :: Integer
ghci> quotRem x y
(2,2)
ghci>
ghci> let x = (-8) :: Integer
ghci> let y = 3 :: Integer
ghci> quotRem x y
(-2,-2)
ghci> let x = (-8) :: Integer
ghci> let y = (-3) :: Integer
ghci> quotRem x y
(2,-2)

ghci> let y = -3 :: Integer
ghci> quotRem x y
(-2,2)
ghci>

I’ve put together  a visualisation and a set of rules that I use to reason about another way that Haskell provides for integer division and along with its modulus operation. First, lets take 8 div 3 and show the results of the different combinations of positive and negative numerators and denominators.
Haskell has a handy function called divMod which returns a tuple with the first element being the integer division result and the second being the remainder (the result of the mod operation).

8 div 3

ghci> let x = 8 :: Integer
ghci> let y = 3 :: Integer
ghci> divMod x y
(2,2)
ghci>

-8 div 3

ghci> let x = (-8) :: Integer
ghci> let y = 3 :: Integer
ghci> divMod x y
(-3,1)
ghci>

-8 div -3

ghci> let x = (-8) :: Integer 
ghci> let y = (-3) :: Integer
ghci> divMod x y 
(2,-2)
ghci>  

8 div -3

ghci> let x = 8 :: Integer
ghci> let y = (-3) :: Integer
ghci> divMod x y
(-3,-1)
ghci>

These can be surprising results especially when compared to, say, Scala. For example, if we take -8 mod 3 in Scala, we get -2 unlike the 1 modulus result we got in our Haskell result (-3,1)

scala> -8 % 3
res2: Int = -2

Visualising Cyclical Integer Division And Modulus

The visualisation works as follows:

  • We have a denominator block in blue which has a length equal to the denominator.
  •  We have a denominator range that we are trying to move the block into which ranges from the denominator , inclusive, to the 0 boundary, exclusive.
  •  We move the denominator block until it partially or completely enters the denominator range.
  •  We have a Divisions accumulator which gets incremented or decremented.
  • If our block moves so that it approaches the denominator range without passing through the 0 boundary, we increment our Divisions accumulator with each move.
  •  Otherwise, the denominator block passes over the 0 boundary and we decrement our Divisions accumulator with each move.
  •  The final Divisions accumulator is the division result and the difference between the top of the denominator block and the 0 boundary gives the remainder.

8 div 2

0 Boundary

1
2
3
4
5
6
7
8

Divisions 0

0 Boundary

1
2
3
4
5
6
7
8

Divisions 1

0 Boundary

1
2
3
4
5
6
7
8

Divisions 2

0 Boundary

1
2
3
4
5
6
7
8

Divisions 3

0 Boundary

1
2
3
4
5
6
7
8

Divisions 4

Our last move brings the denominator block fully into the denominator range so we have no remainder.
So, 8 div 2 is 4 remainder 0.

8 div 3

0 Boundary

1
2
3
4
5
6
7
8

Divisions 0

0 Boundary

1
2
3
4
5
6
7
8

Divisions 1

0 Boundary

1
2
3
4
5
6
7
8

Divisions 2

Our last move brings the denominator partially into the denominator range. Our Divisions accumulator is 3 and the difference between the top of the denominator block and the 0 boundary is 2.
So, 8 div 3 is 2 remainder 2.

Changing division direction -8 div 3

Our Divisions accumulator gets decremented this time because we will be crossing the 0 boundary.

-8
-7
-6
-5
-4
-3
-2
-1

0 Boundary

1
2
3

Divisions 0

-8
-7
-6
-5
-4
-3
-2
-1

0 Boundary

1
2
3

Divisions -1

-8
-7
-6
-5
-4
-3
-2
-1

0 Boundary

1
2
3

Divisions -2

-8
-7
-6
-5
-4
-3
-2
-1

0 Boundary

1
2
3

Divisions -3

Our last move brings the denominator partially into the denominator range. Our Divisions accumulator is -3 and the difference between the top of the denominator block and the 0 boundary is 1.
So, -8 div 3 is -3 remainder 1.

Making the denominator negative, -8 div -3

We can visualise the integer division in the same way. Except, this time the denominator range that we move the denominator block into is -3, inclusive to -1, inclusive.

-8
-7
-6
-5
-4
-3
-2
-1

0 Boundary

1
2
3

Divisions 1

-8
-7
-6
-5
-4
-3
-2
-1

0 Boundary

1
2
3

Divisions 2

Our last move brings the denominator partially into the denominator range. Our Divisions accumulator is 2 and the difference between the top of the denominator block and the 0 boundary is -2.
So, -8 div -3 is 2 remainder -2.

8 div -3

-3
-2
-1
1
2
3
4
5
6
7
8

Divisions 0

0 Boundary


-3
-2
-1
1
2
3
4
5
6
7
8

Divisions -1

0 Boundary

-3
-2
-1
1
2
3
4
5
6
7
8

Divisions -2

0 Boundary

-3
-2
-1
1
2
3
4
5
6
7
8

Divisions -3

0 Boundary

Our last move brings the denominator partially into the denominator range. Our Divisions accumulator is -3 and the difference between the top of the denominator block and the 0 boundary is -1.
So, 8 div -3 is -3 remainder -1

Conclusion

So integer division, when treated like it is with div and mod in Haskell, is different to what many developers would be used to from Java or Scala. The modulus operation is really a way to restrict elements to a certain range as dictated by the denominator. This is why the denominator blocks in the above visualisation are always trying to get into the denominator range without moving past it. It also makes sense to me that, when the denominator block arrives in the denominator range, the remainder is the difference between its top and the 0 boundary.

There are a lot of ways to visualise and think about these cyclical division and modulus operations. I hope this blog may help others reason about the these operations and explore other ways of thinking about them.

Dip your toes in some Haskell, the water is warm here!

Reading Time: 15 mins
Reading Time with hands on trying of the examples: 30 mins approx

Haskell Warm Water

So, Haskell sounds quite daunting right? All this talk of monads and functors when all you want to do is just try out some simple problems and see what it’s like to play around with this language! Monads and functors are actually not that scary once you get into functional programming but, for today, I won’t mention them again. So, lets dip our toes in and see what it’s like.

I often hear newcomers to functional programming sighing to themselves about how difficult it is to retrain their brains to read and write code in this paradigm that is new to them. Don’t get me wrong, the sighing is understandable especially when we have spent years wrapped in our imperative, object oriented comfort blankets with for loops and mutable variables. The sighing is usually witnessed when watching an experienced OO programmer getting to grips with a new codebase written in a functional language and seeing something like this:

5 isPalindrome (x1 : xs)  = x1 == last xs && isPalindrome (init xs)

Yep, there is a bit in there especially when you may be more used to the imperative way of writing such an algorithm.

 2 
 3 public class Palindrome {
 4 
 5     public static boolean isPalindrome(String str) {
 6 
 7         int strEndIndex = str.length() - 1;
 8 
 9         for(int i = strEndIndex; i > (strEndIndex/2); i--)
10             if(str.charAt(i) != str.charAt(strEndIndex - i))
11                 return false;
12 
13         return true;
14     }
15 }

Ah, that’s better. Our old reliable Java for loop with our mutable counter. Let me take you on a small journey to give you a taster for Haskell. We’ll go from Haskell code that actually looks quite similar to that imperative Java code and gradually work towards that previous Haskell code snippet. We’ll use the good old palindrome kata to take us on that journey. The palindrome kata is a task to write a function which checks if a String is the same going from left to right as it is going right to left. Yes, I know, most languages have a library function, reverse, meaning we can simply reverse the String and compare with the original. But lets suspend our disbelief for a while so I can take you on a journey!

Quick setup to follow along

To start dipping your toes in, why not follow along with the Haskell examples in the rest of this post. Haskell quick installers for most types of OS can be found here:
After that, all you need is a text editor and your terminal.
Make a new file called DipYourToesIn.hs and add the declaration for the Haskell module where we will put our functions:

 1 module DipYourToesIn where

Now crank up your favourite command line terminal and go to the directory where you created that file.
Now, simply type: ghci and this will start up the Haskell compiler in interactive mode allowing you to enter and evaluate Haskell expressions. We will use it to simply load and compile our DipYourToesIn.hs Haskell source so that we can call our Haskell functions as we create them to see it them working.

ghci> :l DipYourToesIn.hs
[1 of 1] Compiling DipYourToesIn    ( DipYourToesIn.hs, interpreted )
Ok, modules loaded: DipYourToesIn.
ghci> isPalindromeWithRecursion "hello"
False
ghci> isPalindromeWithRecursion "racecar"
True
ghci>

The Haskell source can be loaded and compiled using :l DipYourToesIn.hs
Once it is compiled, we can now execute functions within that file by simply calling them.
In the next section, we will be creating the function, isPalindromeWithRecursion, but the above just shows how quick it is to start interacting with Haskell code as you write it. In saying that though, this shouldn’t be a substitution for tests. I would still write tests first, and use this interactive approach to experiment with the code that I am writing to make the tests pass.

Imperative Looking Haskell – looks can be deceiving!

So, lets start off with some Haskell that models the above Java solution quite closely.

 2 
 3 isPalindromeWithRecursion :: String -> Bool
 4 isPalindromeWithRecursion str =
 5   loop strEndIndex where
 6 
 7   strEndIndex = length str - 1
 8   loop i =
 9     if (i <= (div strEndIndex 2)) then True
10     else if (str !! i) /= str !! (strEndIndex - i) then False
11     else loop (i - 1)
12 

A note about function type signatures

Line 3 in the above example contains the type signature for our function right after the :: after the function name. This specifies that the function takes a String parameter and returns a Bool (a boolean). Parameters and return types are separated by the -> symbol. If there are multiple parameters, they are all separated by -> with the last type being the return type. This is because every function in Haskell is actually a one parameter function. So, when we see a multiple parameter type signature, under the hood we have a series of outer to inner functions – a concept called currying. It is not important to know all about that just yet though if you are just dipping your toes in.

In Haskell there are no mutable variables or for loops but that doesn’t stop us from writing code that looks almost like the imperative Java solution. We define an inner loop function which is called recursively acting like our for loop.

  • On line 5, the where syntax there is a way to give bindings to local values or functions – essentially creating local immutable variables.
  •  On line 8, we define the loop function which takes an immutable counter, i, meaning that the counter is “updated” by passing a new version of the counter value into the loop function every time it is called.
  •  On line 5, the loop function is called with an initial counter, i, argument being the last index of the String – just like we initialised i in the Java solution.
  • The algorithm remains the same. We check the first and last characters. If they are equal, we continue checking the next 2 inner characters and so on. If we find two that are not equal, we can return False straight away and if we get down to only one or no characters remaining, we know we have a palindrome and return True.
  • This divides the end index of the String by 2 so that we can tell we have gotten to a point of 1 or 0 characters left.
  • (div strEndIndex 2)

     

  • This gets the i’th element of a list, in this case, the i’th character in the String str.
  •  (str !! i)

     

  • This is how we compare a character going right to left with its corresponding character going left to right. /= meaning not equal to
  • (str !! i) /= str !! (strEndIndex - i)

     

As shown previously, we can load this into our GHCI and look at it in action.

ghci> :l DipYourToesIn.hs
[1 of 1] Compiling DipYourToesIn    ( DipYourToesIn.hs, interpreted )
Ok, modules loaded: DipYourToesIn.
ghci> isPalindromeWithRecursion "hello"
False
ghci> isPalindromeWithRecursion "racecar"
True
ghci>

Guard those if then elses!

Instead of building up multiple if then elses, Haskell has this lovely construct called Guards. Using, the | symbol, we can build up boolean conditional expressions with corresponding expressions, one of which will be evaluated if its corresponding boolean expression evaluates to true.

13 isPalindromeWithRecursionAndGuard :: String -> Bool
14 isPalindromeWithRecursionAndGuard str =
15   loop strEndIndex where
16 
17     strEndIndex = length str - 1
18     loop i
19       | i <= (div strEndIndex 2) = True
20       | (str !! i) /= str !! (strEndIndex - i) = False
21       | otherwise = loop (i - 1)
22  

Nothing has changed in our underlying algorithm. Also, not much has changed in the code but it is easier to read right? We still have the same set of conditions and corresponding expressions, one of which will be evaluated.

 | i <= (div strEndIndex 2)
| (str !! i) /= str !! (strEndIndex - i)

and

 | otherwise =

otherwise is the default case and its corresponding expression will be evaluated if none of the other boolean expressions have evaluated to True.

A bit about Haskell lists

A List in Haskell is a recursive data structure. A List can be empty and is simply represented as

[]

A List can also be non empty and, in this case, it is represented as a cell containing a value and a link to another List which itself can be empty or contain another cell with a value and a link to a further List. This recursive structure continues until we get an empty list. This is shown in the diagram below.

beginning-haskell-2-001

The cons function in Haskell, represented with a

:

is used to create one of these list cells by joining a value together with an existing List which may or may not be empty. Using this function, we can create the List in the above diagram as follows:

1 : 2 : 3 : []

Haskell has a nicer way though with syntactic sugar allowing us to do the same thing with this bit of code:

[1, 2, 3]

A couple of List operations to help the palindrome cause

Haskell like other functional programming languages has very nice high level operations that we can use on lists. Lets try a couple with GHCI.

First lets create a List and bind it to a name, l. This is done in GHCI using the let keyword but, in Haskell source code, the let isn’t required.

ghci> let l = [1,2,3,4,5]
ghci> l
[1,2,3,4,5]
ghci>

We’re going to need to be able to get the last element in the list so we can compare it to the first element. This is no problem though, we can simply use a function called last.

ghci> last l
5
ghci>

We will also need to get the first element in a list. We will be doing this later by refining the code with pattern matching. However, just for completeness, we do this by using a function called head.

ghci> head l
1
ghci>

Be careful though, calling head on an empty list will give an exception.

ghci> head []
*** Exception: Prelude.head: empty list
ghci>

For reasons that will become apparent soon, we will also need to use a handy function called init. This creates a new list from everything in an existing list except the last value.

ghci> init l
[1,2,3,4]
ghci>

Polishing it off with pattern matching

Pattern matching is a concept very prevalent in functional programming. It allows you specify patterns to match against a data structure, its value type and by the structure and values of its elements. This allows the data structure to be deconstructed and parts of it extracted.

Function arguments are one place where pattern matching can be used very effectively. This is done in Haskell by redefining the function multiple times to deal with the different possible argument value patterns that can be passed in when the function is called.

52 
53 isPalindrome :: String -> Bool
54 isPalindrome [] = True
55 isPalindrome (x : []) = True
56 isPalindrome (x1 : x2 : []) = x1 == x2 -- this line is not necessary, thanks Szymon 
57 isPalindrome (x1 : xs)  = x1 == last xs && isPalindrome (init xs)
58 

  • The final example above uses a mixture of pattern matching and the functions we saw earlier that we can use on lists. A String is a list of characters so we can pattern match on a list argument to the isPalindrome function.
  • Line 54 matches on the empty list. So, if an empty list is passed as an argument to the isPalindrome function, we return True straight away.
  • Line 55 pattern matches on a list with one element. We use the cons function, : , to match on a list structure which contains one cons cell with a value and a link to an empty list. The value of the cons cell can be anything and is bound to the value, x, in the pattern. So, with this pattern, we are checking if the list has only one element and, if it does, we can again return True.
  • Correction, line 56 is not necessary. Thanks for pointing this out Szymon. If a 2 element list has 2 equal values, the init on line 57 will be called on a one element List, xs, returning an empty list and on the next recursive call, line 54 will return True. Line 56 is pattern matching to check if the list argument has only 2 values. We again use the cons function to match against the list structure that we are looking for. We can also bind the first 2 values of the list to the names, x1 and x2. This allows us to check these for equality to determine if the 2 element list is a palindrome.
  • Finally, on line 57, we are back to that piece of code that is likely to make an experienced imperative programmer sigh when trying to get to grips with a functional programming codebase. When pattern matching, the first function expression with a matching pattern for the argument being passed in is the function expression that gets executed. So, if we have gotten this far, there has been no other pattern match so we know that our list argument has more then 2 values. So, now we simply use one cons function to match on a list that has a first element, x1, and a link to the rest of the list, xs. Now we can use our trusty last function to compare x1 to the last element of the list. If they are not equal, we return false as we don’t have a palindrome.
  • However, it they are equal, we need to evaluate the right hand side of the boolean &&. In this case, we literally create a new list made up of all elements of the list minus the first and last element. By calling init on xs, we are omitting the first element, x1, and getting all elements except the last. Then we recursively call isPalindrome on this newly created list so that we can continue checking further and further into the original list until we get to 2 values that are not equal or an empty or 1 element list (after all other outer elements have been “chopped off” so to speak).

Conclusion

I hope all this might encourage more developers to delve into the beautiful language of Haskell. I started dipping my toes in a while back and, pretty quickly, I took the plunge and absolutely love coding in Haskell. I feel at my most relaxed as a developer when I am writing Haskell code. Building up small composable Haskell functions with a type system that protects you but never gets in your way really does lead to a joyful coding experience for me. I will follow up this post with some more dipping of the toes in Haskell to show how we can use the type system to make our isPalindrome function handle lists of any type…well almost any type.