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.

	namespace FizzBuzz
	module FizzBuzz =
	let fizzbuzzer (n : int) =
	[(3, "Fizz");
	(5, "Buzz")]
	|> List.fold (fun m (x, s) -> m + if n % x = 0 then s else "") ""
	|> (fun s -> if s = "" then string n else s)

view raw FizzBuzz.fs hosted with ❤ by GitHub

	namespace FizzBuzz.Tests
	module FizzBuzzTests =
	open FizzBuzz.FizzBuzz
	open Xunit
	open FsUnit.Xunit
	[<Theory>]
	[<InlineData(3, "Fizz")>]
	[<InlineData(5, "Buzz")>]
	[<InlineData(15, "FizzBuzz")>]
	[<InlineData(2, "2")>]
	let ``Multiples of given value should contain expected`` (given : int) (expected : string) =
	fizzbuzzer given |> should haveSubstring expected

view raw FizzBuzzTests.fs hosted with ❤ by GitHub

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.

	namespace RomanNumerals
	module RomanNumerals =
	let translate n =
	[(40, "XL");
	(10, "X"); (9, "IX");
	(5, "V"); (4, "IV");
	(1, "I")]
	|> List.fold
	(fun (x, m) (k, v) ->
	if x >= k then (x - (k * (x / k)), m + String.replicate (x / k) v)
	else (x, m))
	(n, "")
	|> snd

view raw RomanNumerals.fs hosted with ❤ by GitHub

	module RomanNumerals.Tests.Translate
	open RomanNumerals.RomanNumerals
	open Xunit
	open FsUnit.Xunit
	[<Theory>]
	[<InlineData(1, "I")>]
	[<InlineData(2, "II")>]
	[<InlineData(3, "III")>]
	[<InlineData(4, "IV")>]
	[<InlineData(5, "V")>]
	[<InlineData(6, "VI")>]
	[<InlineData(7, "VII")>]
	[<InlineData(8, "VIII")>]
	[<InlineData(9, "IX")>]
	[<InlineData(10, "X")>]
	[<InlineData(11, "XI")>]
	[<InlineData(29, "XXIX")>]
	[<InlineData(40, "XL")>]
	[<InlineData(49, "XLIX")>]
	let ``given 1 it must return I``
	(value : int, expected : string) =
	translate value |> should equal expected

view raw RomanNumeralsTests.fs hosted with ❤ by GitHub

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.

	namespace Translate
	module Translate =
	let translate folding defaulting translations seed n =
	translations
	|> List.fold folding (n, seed)
	|> snd
	|> defaulting
	let fizzbuzzer (n : int) =
	[(3, "Fizz");
	(5, "Buzz")]
	|> List.fold
	(fun (n, r) (x, s) -> (n, r + if n % x = 0 then s else ""))
	(n, "")
	|> snd
	|> (fun s -> if s = "" then string n else s)
	let fizzbuzzer2 (n : int) =
	translate
	(fun (n, r) (x, s) -> (n, r + if n % x = 0 then s else ""))
	(fun s -> if s = "" then string n else s)
	[(3, "Fizz");
	(5, "Buzz")]
	""
	n
	let romanize (n : int) =
	[(5, "V");
	(4, "IV");
	(1, "I")]
	|> List.fold
	(fun (n, r) (x, s) ->
	(n % x, r + if n >= x then String.replicate (n / x) s else ""))
	(n, "")
	|> snd
	|> (fun s -> s)
	let romanize2 (n : int) =
	translate
	(fun (n, r) (x, s) ->
	(n % x, r + if n >= x then String.replicate (n / x) s else ""))
	(fun d -> d)
	[(5, "V");
	(4, "IV");
	(1, "I")]
	""
	n

view raw Translate.fs hosted with ❤ by GitHub

	namespace Translate.Tests
	module TranslateTests =
	open Translate.Translate
	open Xunit
	open FsUnit.Xunit
	[<Theory>]
	[<InlineData(3, "Fizz")>]
	[<InlineData(5, "Buzz")>]
	[<InlineData(15, "FizzBuzz")>]
	[<InlineData(2, "2")>]
	let ``Given value fizzbuzzer should contain expected`` (given : int) (expected : string) =
	fizzbuzzer given |> should haveSubstring expected
	[<Theory>]
	[<InlineData(3, "Fizz")>]
	[<InlineData(5, "Buzz")>]
	[<InlineData(15, "FizzBuzz")>]
	[<InlineData(2, "2")>]
	let ``Given value fizzbuzzer2 should contain expected`` (given : int) (expected : string) =
	fizzbuzzer2 given |> should haveSubstring expected
	[<Theory>]
	[<InlineData(1, "I")>]
	[<InlineData(2, "II")>]
	[<InlineData(4, "IV")>]
	[<InlineData(5, "V")>]
	let ``Given value should romanize to expected`` (given : int) (expected : string) =
	romanize given |> should equal expected
	[<Theory>]
	[<InlineData(1, "I")>]
	[<InlineData(2, "II")>]
	[<InlineData(4, "IV")>]
	[<InlineData(5, "V")>]
	let ``Given value should romanize2 to expected`` (given : int) (expected : string) =
	romanize2 given |> should equal expected

view raw TranslateTests.fs hosted with ❤ by GitHub

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:

	namespace CoinChanger
	module Changer =
	let changeFor (coins : int list) (amount : int) =
	coins
	|> List.mapFold (fun amount coin -> (amount / coin, amount % coin)) amount
	|> fst

view raw Changer.fs hosted with ❤ by GitHub

	namespace CoinChangerTests
	module ChangerTests =
	open CoinChanger.Changer
	open Xunit
	open FsUnit.Xunit
	[<Theory>]
	[<InlineData(0)>]
	[<InlineData(1)>]
	[<InlineData(42)>]
	[<InlineData(99)>]
	let ``given pennies it must return amount in pennies`` (amount : int) =
	let pennies = [1]
	changeFor pennies amount |> should equal [amount]
	[<Theory>]
	[<InlineData(0)>]
	[<InlineData(1)>]
	[<InlineData(42)>]
	[<InlineData(99)>]
	let ``given nickels and pennies it must return nickels equal to amount % 5`` (amount : int) =
	changeFor [5; 1] amount |> List.head |> should equal <| amount / 5
	[<Theory>]
	[<InlineData(0)>]
	[<InlineData(1)>]
	[<InlineData(42)>]
	[<InlineData(99)>]
	let ``given full register result should add back up to amount`` (amount : int) =
	let register = [25; 10; 5; 1]
	changeFor register amount
	|> List.fold2 (fun m number value -> m + number * value) 0 register
	|> should equal amount
	[<Fact>]
	let ``given full register it must return proper amount`` () =
	changeFor [25; 10; 5; 1] 99 |> should equal [3; 2; 0; 4]

view raw ChangerTests.fs hosted with ❤ by GitHub

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

	using System.Collections.Generic;
	using System.Linq;
	namespace RomanNumerals
	{
	public class Romanize
	{
	private Dictionary<int, string> RomanNumerals { get; }
	= new Dictionary<int, string>
	{
	{100, "C"}, {90, "XC"},
	{50, "L"}, {40, "XL"},
	{10, "X"}, {9, "IX"},
	{5, "V"}, {4, "IV"},
	{1, "I"}
	};
	public string Translate(int value) =>
	RomanNumerals.Aggregate("", (m, l) =>
	{
	while (value >= l.Key)
	{
	m += l.Value;
	value -= l.Key;
	}
	return m;
	});
	}
	}

view raw Romanize.cs hosted with ❤ by GitHub

	using Xunit;
	namespace RomanNumerals.Tests
	{
	public class RomanizeTests
	{
	[Theory]
	[InlineData("I", 1)]
	[InlineData("II", 2)]
	[InlineData("III", 3)]
	[InlineData("IV", 4)]
	[InlineData("V", 5)]
	[InlineData("VI", 6)]
	[InlineData("VII", 7)]
	[InlineData("IX", 9)]
	[InlineData("X", 10)]
	[InlineData("XXIX", 29)]
	[InlineData("XL", 40)]
	[InlineData("L", 50)]
	[InlineData("XC", 90)]
	[InlineData("C", 100)]
	public void GivenNumberItMustReturnExpected(string excepted, int number)
	{
	var sut = new Romanize();
	var actual = sut.Translate(number);
	Assert.Equal(excepted, actual);
	}
	}
	}

view raw RomanizeTests.cs hosted with ❤ by GitHub

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.

	(ns romannumeral)
	(defn romanize [n]
	(:result
	(reduce
	(fn [{value :value result :result :as orginal} [digit letter]]
	(if (>= value digit)
	{:value (rem value digit) :result (apply str result (repeat (quot value digit) letter))}
	orginal))
	{:value n :result ""}
	[[100 "C"]
	[90 "XC"]
	[50 "L"]
	[40 "XL"]
	[10 "X"]
	[9 "IX"]
	[5 "V"]
	[4 "IV"]
	[1 "I"]])))

view raw RomanNumeral.clj hosted with ❤ by GitHub

	(ns romannumeral.tests
	(require
	[clojure.test :refer :all]
	[romannumeral :as sut]))
	(deftest roman-numeral-value-tests
	(testing "Given a valid number it must give the correct roman numeral"
	(is (= "I" (sut/romanize 1)))
	(is (= "II" (sut/romanize 2)))
	(is (= "III" (sut/romanize 3)))
	(is (= "IV" (sut/romanize 4)))
	(is (= "V" (sut/romanize 5)))
	(is (= "VI" (sut/romanize 6)))
	(is (= "IX" (sut/romanize 9)))
	(is (= "X" (sut/romanize 10)))
	(is (= "XXIX" (sut/romanize 29)))
	(is (= "XLIX" (sut/romanize 49)))
	(is (= "LXXXIX" (sut/romanize 89)))
	(is (= "XCVIII" (sut/romanize 98)))
	(is (= "CCCXCIX" (sut/romanize 399)))
	))
	(run-tests 'romannumeral.tests)

view raw RomanNumeralTests.clj hosted with ❤ by GitHub

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

	namespace RomanNumerals
	module RomanNumerals =
	let translate n =
	[(40, "XL");
	(10, "X"); (9, "IX");
	(5, "V"); (4, "IV");
	(1, "I")]
	|> List.fold
	(fun (x, m) (k, v) ->
	if x >= k then (x - (k * (x / k)), m + String.replicate (x / k) v)
	else (x, m))
	(n, "")
	|> snd

view raw RomanNumerals.fs hosted with ❤ by GitHub

	module RomanNumerals.Tests.Translate
	open RomanNumerals.RomanNumerals
	open Xunit
	open FsUnit.Xunit
	[<Theory>]
	[<InlineData(1, "I")>]
	[<InlineData(2, "II")>]
	[<InlineData(3, "III")>]
	[<InlineData(4, "IV")>]
	[<InlineData(5, "V")>]
	[<InlineData(6, "VI")>]
	[<InlineData(7, "VII")>]
	[<InlineData(8, "VIII")>]
	[<InlineData(9, "IX")>]
	[<InlineData(10, "X")>]
	[<InlineData(11, "XI")>]
	[<InlineData(29, "XXIX")>]
	[<InlineData(40, "XL")>]
	[<InlineData(49, "XLIX")>]
	let ``given 1 it must return I``
	(value : int, expected : string) =
	translate value |> should equal expected

view raw RomanNumeralsTests.fs hosted with ❤ by GitHub

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.

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

• Idris

Non-Fiction Books

• Zhuangzi: The Essential Writings by Zhuangzi
• Mastering Clojure Macros: Write Cleaner, Faster, Smarter Code by Colin Jones
• Against Method by Paul Feyerabend
• Type Theory and Formal Proof: An Introduction by Rob Nederpelt and Herman Geuvers

Fiction Books

• The Adventures of Sherlock Holmes by Arthur Conan Doyle
• David Copperfield by Charles Dickens
• Dracula by Bram Stoker
• La Cousine Bette by Honoré de Balzac
• La Chartreuse de Parme by Stendhal

White Papers

• "A tutorial on the universality and expressiveness of fold" by Graham Hutton
• "Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire" by Erik Meijer, Maarten Fokkinga, Ross Paterson

Music

• Balzac
• Dave Hause
• Masked Intruder
• The Menzingers
• GOD Is an Astronaut
• maybeshewill

My Top 5 Most Popular Blog Posts of 2015

• Intro to Higher Order Functions
• Think About Length OR How Fold Can Do Everything, Even Count
• Always Bet on Math
• Bro, Do You Even FizzBuzz?!?
• One Data Structure to Rule Them All

Most Enjoyable Conferences

Presented at: Midwest.io

Attended: Strange Loop

Location (Portland): Clojure/West