Sunday, January 24, 2016

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

Monday, January 18, 2016

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.

Sunday, January 10, 2016

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.

Saturday, January 2, 2016

Discoveries in 2015

"So Jove, the Olympian Lord of Thunder, hied him to the bed in which he always slept; and when he had got on to it he went to sleep, with Juno of the golden throne by his side."
-- The Iliad, Homer
Book 1

My discoveries in 2015 of things that I've enjoyed (idea from Michael Fogus' Best Things and Stuff of 2015).   Order is just ordered of discovery.

Programming Languages

Non-Fiction Books

Fiction Books

White Papers


My Top 5 Most Popular Blog Posts of 2015

Most Enjoyable Conferences

Presented at:
Attended: Strange Loop
Location (Portland): Clojure/West