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.