Unquote, App.config, and You

"What curious eye doth quote deformities?"
-- Shakespeare, Romeo and Juliet
Act I, Scene IV, Line 31

I've started using Unquote for my assertions with F# xUnit tests.  I find that its step-by-step failure messages really help in figuring out what is going on.

One thing that really throw me when I first used it was the System.MissingMethodException exception that Unquote was throwing at runtime.  Luckily I was able to find this StackOverflow answer.  It seems that you need to do a binding redirect for FSharp.Core, so you'll need to set up an App.config file in your test project like this example of the Coin Changer kata (using MapFold).



Happy coding.

Item and Slice F#

"Slice, I say. Pauca, pauca. Slice! That's my humour."
-- Shakespeare, The Merry Wives of Windsor
Act I, Scene I, Line 125

I've been working my way through Dave Fancher's excellent Book of F# and found an interesting example of indexing and slicing arrays in F#.  Since programming is a full contact sport, here is my take on indexing and slicing in F#.



We have a constructor for a type called Word which takes a string and separates it into words.

type Words(sentence : string)

We implement an index with the Item member.

member x.Item(i) = words.[i]

This allows us to access the words of the string given.

Words(sentence).[1]

We also implement an array slice with the GetSlice member.

member x.GetSlice(s : int option, e : int option)

This allows us to slice the array (substring it) of words in the string given.

Words(sentence).[1..2]

We can go one better than built in slice by allow for range in the slice to be bigger than the number of words.

let longer = 100
Words(sentence).[0..longer]

In order to allow for this we have to check to see if the end is greater than the number of words.

if e > words.Length then words.[s..] else words.[s..e]

and

if e > words.Length then words else words.[..e]

I hope I have shown that F# has some very nice support for objects.

FizzBuzz and the Roman Numeral Kata are the Same Thing!

"The same, sir."

-- Shakespeare, Coriolanus

Act IV, Scene III, Line 7

As Homer Simpson pointed out, "Coke and Pepsi are the same thing!"


Similarly I plan to show that the FizzBuzz and Roman Numeral katas are the same thing! 

First let's look at the rules of FizzBuzz.

f(x : int) : string

  if 3 | x and 5 | x then "FizzBuzz"
  if 3 | x then "Fizz"
  if 5 | x then "Buzz"
  default string x

*note, 3 | x reads 3 divides x, in other words x / 3 does not have a remainder

 In general we see that we have two (or three) rules and a default value, we are translating from the domain into the codomain following a set of rules, in other words we have a function.

How about the Roman Numeral kata?

f(x : int) : string

  fold

    roman-numerals : (int, string)

    lambda((x : int, m : string),

           (k : int, v : string)) : (int, string)

      while k | x then (x / k, concat m v)

    (x, default string) : (int, string)

Again we see a list of rules for translation.

The only real difference to FizzBuzz is the fold across the rules, but we've hinted at this in the FizzBuzz description above.  We stated that FizzBuzz has two (or three) rules, we can rewrite it using a fold with just the two rules using the fold to cover the "and" case.

We see the FizzBuzz and Roman Numeral as having the same shape which we use in the generalization in the "2 version".  Thus using the same function with a set of rules, a defaulting function, and a seed we create both the FizzBuzz and Roman Numeral kata from the same general function!

MapFold OR Set Phasers to Fun

"Back to our brother of England."
-- Shakespeare, Henry V
Act II, Scene IV, Line 115.1

One of the things I love about functional programming is you can tell a lot about how a function works by just looking at its type signature.  In F# 4.0 there is a new function to work with collections, here is it type signature:

('State -> 'T -> 'U * 'State) -> 'State -> C<'T> -> C<'U> * 'State

What do you think it does?

That's right this is a MapFold.  Looking at its full definition we see the following:

let mapFold<'T,'State,'Result> 
  (f:'State -> 'T -> 'Result * 'State) acc list =

How does this work?

Looking at F#'s unit tests we see the following test name:

let ``mapFold works like map + fold`` () =

MapFold works like a map with a fold to maintain state.  I know what you are thinking maintaining state is bad, that's why functional programming is easier to reason about.  This is very true, but this is not a mutable state, this is an evolving state.

Let us look at an example, the Coin Changer kata:



The Coin Changer kata simulates one of those machines which give you back coins at a store.  It takes a list of coin values and the amount of change to be given.

The Coin Changer kata is interesting since it has two things going on at the same time: 1) state and 2) list processing.  In the Coin Changer kata you must maintain the amount of change you have left to give along with the amount of each coin to be given back.  An example would be 99 cents with an US register, you would get back 3 quarters, 2 dimes, 0 nickels, and 4 pennies.

How would this example of 99 cents with an US register work with MapFold?

changeFor [25; 10; 5; 1] 99

We'll use s to hold the state, r to hold the result, and x to hold the current coin value we are looking at .

Processing the first value: x = 25, s = 99, r = [] resulting in s = 24, r = [3]
Second value: x = 10, s = 24, r = [3] resulting in s = 4, r = [3; 2]
Third: x = 5, s = 4, r = [3; 2] resulting in s = 4, r = [3; 2; 0]
Last: x = 1, s = 4, r = [3; 2; 0] resulting in s = 0, r = [3; 2; 0; 4]

There you have it, step-by-step through the Coin Changer kata using MapFold.

Guess what the source code to MapFold looks for the most part like what we just experienced.  Here it is:



We see that it loops through each member of the collection, applying the function given against the state and current member.  Once there are no more members it returns a tuple of the result along with the state.  For the Coin Changer kata we do not care about the state (maybe we could use it verify that we have 0 cents) so we just drop it and get the result using fst.

There you have it the Coin Changer kata and MapFold seem to be made for each other.

Data Structures Matters

"I see thee yet, in form as palpable"
-- Shakespeare, Macbeth
Act II, Scene I, Line 31 

One of the katas we like to use at work while interviewing candidates is the Roman Numeral kata.  It is a simple kata in which you create a function which takes an integer and gives you back a string representing the roman numeral representation of the number.  It is fairly simple to explain but is deep enough to get a good idea of how the person works.

Here is a possible solution to the Roman Numeral kata in C#.



Looking at this solution we see a few things.  The solution is using C# 6.0 syntax but beyond that we see three major things.

1. translation are being applied using the higher order function Fold (in C# Aggregate)
2. mutation of the input value is used to maintain state through iterations
3. translations are held in a Dictionary

Let us look at the Dictionary data structure which is the main focus of this post.  In general a Dictionary is not ordered, now some implementations are ordered in the order in which the key value pairs are inserted (this is the case with the C# implementation), but this is not a property of the Dictionary data structure (see also the NIST entry).

Here is a possible solution to the Roman Numeral kata in Clojure.

Looking at this solution we see a few things.

1. translations are being applied using the higher order function Fold (in Clojure reduce) 
2. hash maps are used to maintain state through iterations
3. translations are held in a vector of vectors

We see that we cannot use a Dictionary (called maps in Clojure) to hold the translation.  Clojure's HashMap uses Phil Bagwell's Hash Array Mapped Trie which makes no claim about order, in fact we see that maps (and sets) are unordered while vectors (lists and seq) are ordered.  Since our algorithm requires that the translations be in the order we insert them we must use a data structure which preserves this order.  Thus we must used something that is ordered like a vector.

How about F#?  Here is a possible solution to the Roman Numeral kata in F#.

Looking at this solution we see a few things.

1. translations are being applied using the higher order function Fold (using F#'s List.fold)
2. tuples are used to maintain state through iterations
3. translations are held in a List

For the same reasons that we found in the Clojure solution we cannot use a Dictionary (called a Map in F#) since they are ordered by F#'s generic comparison and not in the ordered in which they were inserted.  Luckily we can use a List which is ordered.

There you have it, the Roman Numeral kata in three different languages.  Despite being a simple kata we have learned something about the Dictionary data structure, mainly that it does not have an order and thus should not be used in cases in which order matters.

Bird Watching with Clojure -- The Thrush(y)

"With heigh, with heigh, the thrush and the jay,
Are summer songs for me and my aunts"
Shakespeare, The Winter's Tale
Act IV, Scene III, Lines 10-11

The Thrush

As the wind gently rustles the leaves in the combinator forest.  You sing DO RA and hear sung back to you RA DO.  You sing RA ME and hear ME RA, you sing DO DO and hear DO DO back.  You have just heard the Thrush.

The Thrush or T combinator basically flips your parameters.

T x f = f x

In the Data Aviary Bird package for Haskell it is defined in the following way:

-- | T combinator - thrush.
-- Haskell @(\#)@ in Peter Thiemann\'s Wash, reverse application.
thrush :: a -> (a -> b) -> b
thrush x f = f x

We see that when we call it we pass a value as our first parameter followed by the function we wish to apply the value against.  This is useful when you want to pipe your data through a bunch of functions.

Thrush in F#

In fact in F# this is exactly what the |> (forward pipe) does.  It is defined in the following way:

let (|>) x f = f x

Yep, the forward pipe is nothing more than a Thrush!

Thrush in Joy

In Joy the Thrush goes by the name swap, which makes perfect sense.  It is defined in the following way:

[B] [A] swap == [A] [B]

Thrush in JavaScript

Reg Braithwaite of allong.es fame has a JavaScript library which is perfect for learning combinators called oscin.es.  The Thrush is defined in the following way in oscin.es:

  function Thrush (a, b) {

    return b.call(this, a)

  }

  function T (a) { return function _T (b) {

    return b(a)

  }}

This exactly what we would expect looking at the Haskell and F# code above.

This is very similar to how Reginald defined the Thrush in Ruby in his excellent book, Kestrels, Quirky Birds, and Hopelessly Egocentricity:

thrush.call(a_value).call(a_proc)
  => a_proc.call(a_value)

Thrush(y) in Clojure

Clojure has two macros which are Thrushy (Michael Fogus has an excellent post on why they are Thrushy) the -> and ->> macros.

Say we wanted to do the following:

get the sum of the even integers from 1 to 100

We can break this requirement down into a few steps.

1. get the integers from 1 to 100
2. get the even integers from 1
3. sum the integers from 2

What we see happening is a linking or piping of the results of a step down to the next step.

1 to 100 => evens => sum

Here are two ways to write this in Clojure:



The first way looks like a waterfall, but in order to understand it we need to go all the way to the bottom and work are way back up.  In this example we would start with the (range 101) then move up to the (filter even?) and lastly end at the (reduce +).  We find that reading this, we are going against the left to right flow of the code.

The second, Thrush(y) way, the first thing we see is our (range 101), next we find the (filter even?), and last we find the (reduce +).  This way seems very natural as the flow of data agrees with the reading from left to right.

I personally find the pipeline style used in the second way easier to read and use it as often as I can.  Martin Folwer has written an excellent article which goes into collection pipelines in more detail.  Debasish Ghosh has also written about the Thrush in Clojure (which help me a lot when I was trying to understand the -> and ->>macros).

Leap Year in the Key of C#, F#, Haskell, and Scala

"Shall be their father's bail, and bane to those"
-- Shakespeare, Henry VI Part 2
Act V, Scene I, Line 120

Leap Year

Leap year, one of the time based banes of a programmers' existence.

The rules around if a year is a leap year are simple enough.

if year is divisible by 400 then

   is_leap_year

else if year is divisible by 100 then

   not_leap_year

else if year is divisible by 4 then

   is_leap_year

else

   not_leap_year

Most languages do have a built in check for Leap Years, but the point of the kata is to implement your own in order to learn something.  With that in mind let's look at few ways to solve this problem and see what we can learn.

C#

Note, if we want to do it the most efficient way possible we could just use the built in DateTime.IsLeapYear, but the point of the kata is to implement the algorithm yourself in order to learn something.



Here is an example using C# with NUnit for the testing.

We see that we can just implement the algorithm as a series of conditional statements.  We also see that with NUnit we can use the TestCase attribute which allows us to just give the input along with the expected result.  This kind of testing I feel leads to more readable test cases which focus on the data and not the steps needed.  Having a test case which focuses on the data is the right approach in my opinion for testing a pure calculation based function like this.

Haskell

Note, this looks a lot like the code on Rosetta Code for the TDD Haskell implementation of Leap Year, because it is the same code that I contributed there for that entry.



This Haskell solution uses pattern matching.  If you are new to pattern matching you can think of it as a switch statement.

With this style of pattern matching in Haskell we would get an error message if we call the function without a value which was covered, but the otherwise keyword at the end covers everything else so getting an exception would not happen.  Comparing this to the C# solution with a series of conditional statements the Haskell caller knows that every input is covered by the function whilst the C# call will have to hope that all input cases are covered.

Scala

Note, this is my third Scala kata ever, as such I need to look at this gist form Kingsley Davies in order to do the kata.



With the Scala solution we are again using pattern matching, but this time we are doing all of the testing in a tuple which we are matching against (note, we could have done this in the Haskell and below in the F# solution).  Using this style of pattern matching we are matching against a pattern but in this case I feel that the algorithm is hidden, as such for this function I do not think this is an improvement over the Haskell solution above (note, I did this on purpose to try out this approach with this solution to see what it would look like).

F#

This last solution using F# uses Active Pattern Matching.  Personally I find the Active Pattern Matching with a Maybe Monad very readable.  We can see that the algorithm states if the year is divisible by 400 we have leap year, but if it is divisible by 100 we do not.

Note, you can do this pattern in Scala and Haskell.

Conclusion

We see above 4 somewhat different ways to find if a year is a Leap Year.  All these approaches used unit testing frameworks along with TDD.  None of the solutions are the way to do it, but each look at the problem from a different point-of-view.

Roman Numerals and FsCheck

"Friends, Romans, countrymen, lend me your ears;
I come to bury Caesar, not to praise him."
-- Shakespeare, Julius Caesar
Act III, Scene II, Lines 74-75

Testing is Hard

Lets face it, testing is hard.  In fact be able to test something in which you are unsure even how it is suppose to work is very hard.  Luckily we have a bit more tools today than when people wrote assembler.  One such tool is property based testing.

With property based testing you test for properties of the result of your system under test.  Also unlike traditional unit testing, with property based testing your test data is generated for you.  With this style of testing you can enhance your unit testing by finding more edge cases with property based testing.  I believe an example would be nice about now.

Property of Roman Numerals

The Roman Numerals kata is an interesting exercise in which you take a number in its arabic form and convert it into its roman numeral form.  This kata is fairly realistic if you do a lot of ETL type working in your day-to-day job.  Let's take a look at some of the rules for the Roman Numeral kata.

Given an arabic number it will be converted to a string representing its value as a roman numeral.

roman(   1) => I
roman(   2) => II
roman(   3) => III
roman(   4) => IV
roman(   5) => V
roman(   6) => VI
roman(   7) => VII
roman(   8) => VIII
roman(    9) => IX
roman(  10) => X
...
roman(  29) => XXIX
roman(  30) => XXX
...
roman(  49) => XLIX
roman(  50) => L
...
roman(  99) => XCIX
roman( 100) => C
...
roman( 499) => CDXCIX
roman( 500) => D
...
roman( 999) => CMXCIX
roman(1000) => M

Looking at the examples above we see that we only really need to test 1-10 and special values like 40, 50, 90, 100, 400, 500, 900, and 1000.  We also see that roman numerals have properties like, at most we have one of the values like V, L, and D in the roman numeral string.  We also see that we have a property of only have up to three of the same letter in a row.  With these tests and properties in mind we can write some C# code to provide the functionality and test it with some F# code using xUnit and FsCheck.

Unit Testing

With our Unit Testing we only really need to test 1-10 and special values like 40, 50, 90, 100, 400, 500, 900, and 1000.

We can do this with one simple test (lines 8-38 in the gist above).

module ``Roman Numeral Unit tests`` =



[<Fact>]

let ``For this input it will produce this output`` () =

let testpairs = [

(0, "")

(1, "I")

(2, "II")

(3, "III")

(4, "IV")

(5, "V")

(6, "VI")

(7, "VII")

(8, "VIII")

(9, "IX")

(10, "X")

(20, "XX")

(30, "XXX")

(40, "XL")

(50, "L")

(90, "XC")

(100, "C")

(400, "CD")

(500, "D")

(900, "CM")

(1000, "M")

]

for (number, expected) in testpairs do

let romanizer = RomanNumeraler ()

let actual = romanizer.Translate number

Assert.Equal<string>(expected, actual)

With one simple collection of pairs we can easily add test cases as we add functionality.  This is a big boost for productivity.

I got the idea for this from Scott Wlaschin's blog excellent blog post.

Property Based Testing

Unit Testing is great for driving out what we already know, but how do we really put our code through the wringer?  This is were property based testing comes into play.  For our property based testing we will use FsCheck.

The first property we'll look at is that we have at most one V, L, or D in the roman numeral string.

let ``max number of V is 1`` =

``max number of letter is 1`` "V"



let ``max number of L is 1`` =

``max number of letter is 1`` "L"



let ``max number of D is 1`` =

``max number of letter is 1`` "D"

We see that this uses very similar functionality to test so we come up with a general function.

let ``max number of letter is 1`` letter number =

let romanNumerals = ((RomanNumeraler()).Translate number)

let numberOf = match romanNumerals with

| "" -> 0

| _ -> (romanNumerals.Length - romanNumerals.Replace(letter, "").Length) / romanNumerals.Length

match numberOf with

| 0 | 1 -> true

| _ -> false

We get the count of the number of letters repeating using a function I found on Rosetta Code that I thought was very slick.

Next we see that this property is also true for the values of IV, IX, XL, XC, CD, and CM.

let ``max number of CM is 1`` =

``max number of letter is 1`` "CM"



let ``max number of CD is 1`` =

``max number of letter is 1`` "CD"



let ``max number of XC is 1`` =

``max number of letter is 1`` "XC"



let ``max number of XL is 1`` =

``max number of letter is 1`` "XL"



let ``max number of IX is 1`` =

``max number of letter is 1`` "IX"



let ``max number of IV is 1`` =

``max number of letter is 1`` "IV"

Now we can actual test the properties.

[<Property>]

let ``for all valid inputs there is a maximum of one V`` (x:int) =

normalize x |> ``max number of V is 1``



[<Property>]

let ``for all valid inputs there is a maximum of one L`` (x:int) =

normalize x |> ``max number of L is 1``



[<Property>]

let ``for all valid inputs there is a maximum of one D`` (x:int) =

normalize x |> ``max number of D is 1``



[<Property>]

let ``for all valid inputs there is a maximum of one CM`` (x:int) =

normalize x |> ``max number of CM is 1``



[<Property>]

let ``for all valid inputs there is a maximum of one CD`` (x:int) =

normalize x |> ``max number of CD is 1``



[<Property>]

let ``for all valid inputs there is a maximum of one XC`` (x:int) =

normalize x |> ``max number of XC is 1``



[<Property>]

let ``for all valid inputs there is a maximum of one XL`` (x:int) =

normalize x |> ``max number of XL is 1``



[<Property>]

let ``for all valid inputs there is a maximum of one IX`` (x:int) =

normalize x |> ``max number of IX is 1``



[<Property>]

let ``for all valid inputs there is a maximum of one IV`` (x:int) =

normalize x |> ``max number of IV is 1``

To limit the value which are passed to our tests we can a normalize function which will limit values to be between 1 and 3999.

let normalize x = (abs x % 3999) + 1

Now we can look at testing the max number of repeating letters for I and X.

let ``has max number of repeating letter is 3`` letter number =

let romanizer = RomanNumeraler ()

not ((romanizer.Translate number).Contains(String.replicate 4 letter))



let ``has max number of repeating I is 3`` =

``has max number of repeating letter is 3`` "I"



let ``has max number of repeating X is 3`` =

``has max number of repeating letter is 3`` "X"

[<Property>]

let ``for all valid inputs, there is a max of three repeating I`` (x:int) =

normalize x |> ``has max number of repeating I is 3``



[<Property>]

let ``for all valid inputs, there is a max of three repeating X`` (x:int) =

normalize x |> ``has max number of repeating X is 3``

Last we can look at testing every number which is divisible by 5 ends with a V.

let ``divisible by 5 will have a V`` number =

let romanizer = RomanNumeraler ()

(romanizer.Translate number).Contains "V"

[<Property>]

let ``for all valid inputs divisible by 5, there is a V`` (x:int) =

x % 2 <> 0

==> ``divisible by 5 will have a V`` (abs x * 5)

We can continue in this format but I believe we have a good foundation at this point.