Sunday, March 1, 2015

Roman Numeral Kata in One Line with C#

"When in one line two crafts directly meet."
-- Shakespeare, Hamlet
Act III, Scene IV, Line 211

The idea of the Roman Numeral kata is that given a number between 1 and we'll say 4999, the number will be converted into the Roman numeral form.

f(1) = "I"
f(2) = "II"
f(3) = "III"
f(4) = "IV"
f(5) = "V"
...
f(4999) = "MMMMCMXCIX"

You can test a value using Google's search by typing the number and "to roman".  Try searching for "299 to roman" to test it out.

At work, we have been using the Roman Numeral kata for interviewing candidates.  The idea is that we get an idea of what it is like to work with the person and they get an idea of what it is like to work with us.  As an added bonus there is a good chance that we will learn something new from each other in the process.

On one such interview recently, we had a candidate do something rather interesting.  Typically a candidate will just start with a series of if statements, some candidates will replace the ifs with an associative data structure (called dictionary in C#), but most will not.  This candidate did a transformation of the input into a string of "I"s and then replace those with the Roman numeral.  They did not ended up finishing or even coming to a general pattern, but I found this idea interesting and ran with it coming up with a C# one liner.



We see in the code above a few different things.

To make this a REPL one liner we create a Func which takes an integer and returns a string, we then start the lambda expression with the bond variable of number.  (In the refactoring done on the candidates code this was all in a single return statement in a method not a Func variable, but when I redid it for this post I did it on the Mono REPL as a Func variable.)

Func<int, string> toRoman = (number) =>

After that we have our associative array, which allows us to look up each of the transformation that we will be doing, this is very useful since to add another transformation we just need to add an entry to the associative array.  (I've done this kind of thing in real world application but I normally will make the look up be a private member of the class.)

new Dictionary<int, string>
{
{1000, "M"},
{ 900, "CM"},
{ 500, "D"},
{ 400, "CD"},
{ 100, "C"},
{ 90, "XC"},
{ 50, "L"},
{ 40, "XL"},
{ 10, "X"},
{ 9, "IX"},
{ 5, "V"},
{ 4, "IV"},
{ 1, "I"}
}
**Note, you do not need the "I" entry in the associative array do the the seed value of the fold, but we'll leave it in there since it is from the more general way of doing this kata.**

We then take this and run it through a fold (called Aggregate in C#).

.Aggregate(

In the seed value to the Aggregate we create a transformation string of the "I"s equal to the value given by the caller.

t(1) = "I"
t(2) = "II"
t(3) = "III"
t(4) = "IIII"
...
t(20) = "IIIIIIIIIIIIIIIIIIII"

To do this we use the string constructor that takes a character and the number of times you wish that character to repeat.

new string('I', number),

We then have the lambda of the Aggregate in which we simply take the current Key and Value from the associative array and call Replace on the transformed string replacing the number of "I"s given in the Value with the Roman numeral given in the Key.

(m, _) => m.Replace(new string('I', _.Key), _.Value));

This is not the "best" implementation of the Roman Numeral kata, but it is a one liner!



"The one I'll slay; the other slayeth me."
-- Shakespeare, A Midsummer Night's Dream

Sunday, February 15, 2015

Customs in Coding Style

"What's in a name? That which we call a rose
By any other word would smell as sweet.
So Romeo would, were he not Romeo called,
Retain that dear perfection which he owes
Without that title. Romeo, doff thy name;
And for thy name, which is no part of thee,
Take all myself.
"
-- Shakespeare, Romeo and Juliet
Act II, Scene II, Lines 43-49.1

Recently for a lunch and learn at work my team re-watched Clean Coders episode 2: Names++.  As with all Uncle Bob videos I highly recommend it.  Being a developer who programs a bit in C# I do have to disagree with his statements about bucking the convention of starting interfacing with an "I", the example he gives is IAccount vs Account.  I agree with most of what he said and having programed in many other language I completely agree that the "I" does not add any additional information but I still use it when I program in C#.  Why?

"Pindar was right, in my judgment, when he said, '[Custom] is the king [over] all.' "
-- Herodotus, The Histories
Translated by George Rawlinson
Book III

Custom is king of all.  I strongly believe that if there is a current naming standard in a language you should just follow it.  When I am doing C# in Visual Studio whatever ctrl+k ctrl+d does is the standard I follow (for the most part).

Why?  Source code is for humans to read and understand, all groups, peoples, languages, ... have customs.  These customs are often built into the communications patterns that are followed and are implied by parties taking part in the communication.

Do not believe me, how would I order a Coca-Cola where you are from?  I grew up in the Chicago area, my whole life people referred to all soft-drinks as pop.  I currently work in Milwaukee guess what they call soft-drinks?  In Milwaukee a soft-drink is called soda.  As a kid I vacationed in the Ozarks, what do you think they would call a soft-drink?  All soft-drinks in the southern part of Ozarks were referred to as coke.  There is a whole website which covers all this pop VS soda VS coke.

What is my point?  When coding in a language if you want other people who program in that language to understand what your code is doing with the minimal amount of effort you should just follow the existing standards of the language you are coding in.

There are lots of other place in software development to have a style and flair, bucking current language naming standards is not the place to do it.

"[I]f one were to offer men to choose out of all the customs in the world such as seemed to them the best, they would examine the whole number, and end by preferring their own; so convinced are they that their own usages far surpass those of all others."
-- Herodotus, The Histories
Translated by George Rawlinson
Book III

Sunday, February 8, 2015

The LISP Connection

"There is a history in all men's lives"
-- Shakespeare, Henry IV Part 2
Act III, Scene I, Line 76


Questions not asked


Why are there so many conference sessions about things to come and how things will get better?

Why are there so many blog posts about what is new and the 5 to 10 things you should know about them?

How many sessions are there that reflect upon the past and what we've learned along the way?

How many blog posts are there about the history of programming and the important lessons we've learned along the way?

What I like about Lisp


LISt Processing is one of the oldest computer languages (FORTRAN is older by a year).  Using LISP or one of its dialects you feel a connection to those programmers and scientist that came before you.

Randall Munroe's xkcd, Lisp Cycles

This sense of connection is an old but very important idea.

What Lisp has taught me thus far


Over the past few months I've been learning Clojure from the Joy of Clojure and now Programming Clojure, here are the things I've learned thus far:


  • homoiconic leads to fewer syntax errors and easier to read code
  • compose functionality from smaller well tested functionality
  • separate assignment of values from actions upon values
I look forward to continuing my path along the Lisp way.

Unlikely credits


Questions not asked and titled inspired by the Rainbow Connection, written by Paul Williams.



Sunday, February 1, 2015

Reducing Filter to Reduce OR All You Need is Fold

"All springs reduce their currents to mine eyes"
-- Shakespeare, Richard III
Act II, Scene II, Line 68

Intro


Last time we look at using the ideas presented in Graham Hutton's paper "A tutorial on the universality and expressiveness of fold" around mapping map to a fold.  This post will look at filtering filter down to a fold.

Filter


Filter goes by many different names, to those who speak Clojure, Haskell, and Underscore.js it is called Filter, to others that speak C# it is know as Where, while those that speak C++ know it as Remove, ... we could go on like this for a bit.



The point is that this is the same idea called by different names.  With a Filter what you are doing is taking a collection and applying a predict which state which members of the collection to let into the resulting collection and which members to not allow.  Think of it as a bouncer at a club, some of the people looking to get in will be admitted to the club others will be turned away, the bouncer is the predict, the people are the collection, and those few that get into the club are the resulting collection.

An easy example is to filter out all members of a collection of integers which are not odd.  In Clojure and C# we could use the following code to do this.



We see in both languages that we can use a higher order function to filter our collection down to the resulting collection with the property of oddness that we are looking for.  Clojure has a built in predicate function to check for oddness of a number while in C# we have to roll our own with a lambda function.

Fold


We talk about Fold last time, but we'll review it really quick.


When we are talking about Fold we are talking about taking a collection and applying a function against each member of the collection resulting in a result of a single "value".

Hmm, this sounds kind of similar to what we are doing with Filter...

Folding Filter into a Fold


When we looked at Filter we saw some similarities to Fold.

  1. apply a function to each member of a collection
  2. building a result

In fact we could look at Filter in the following way:


If we take a Fold (aka Reduce), a predicate function, and a collection to hold the resulting collection, we end up with a Filter.  We can looking at the following examples in Clojure and C# using our friend isOdd with a Fold to produce a Filter



In the Clojure code we see that we have a predicate function testing if a value is odd and if it is we conj it to a memorized resulting collection else we just pass along the memorized result collection.  We seed the Reduce (aka Fold) with an empty vector was is used to hold the memorized result collection.  Note, the memorized result collection is %1 in the lambda function while the current member we are looking at is %2, this pattern is typical in Folds across different languages (I cannot think of one which does not have this as the order, but maybe one exist).

In the C# code we new up a List to hold our resulting collection and in our lambda we test the current member we are looking at, if it passes we add it to the memorized result collection, then we always pass the memorized result collection along to the next call of Aggregate (aka Fold).  Since we had an array of integers as our input, we need to reshape the result collection with a call to ToArray.

By looking at this simple example we see that all we really need is Fold.  :)

Sunday, January 25, 2015

Reducing Map to Reduce OR All You Need is Fold

"That would reduce these bloody days again"
-- Shakespeare, Richard III
Act V, Scene V, Line 36

Intro


Have you heard the tale of the madman who came running into the town late at night, screaming that all you need is fold?

In Graham Hutton's paper "A tutorial on the universality and expressiveness of fold" it is shown that we can reduce recursive functions into a definition using fold.  Let's take a look reducing map to a fold.

(O-the tale of the madman is about me and not Dr. Hutton.)

Map


Map goes by a few different names, to those who speak Clojure, Haskell, or Underscore.js it goes by the name Map, to those which speak C# it goes by the name Select, those who speak C++ call it Transform, ... we could go on like this for a bit.


The point is that idea of the higher order function Map goes by different names in different language but performs the same function of taking a collection and applying a function against each member and placing it into the resulting collection.


The easiest example that actual does something is to apply an increment function with a Map.  Looking above we see that when we Map the increment function against a collection with the members of 1, 2, 3, 4 we get a resulting collection with the members of 2, 3, 4, 5.

In Clojure and C# it would look like this:



Fold


Fold goes by a few different names too, to those that speak Clojure or Underscore.js it goes by the name Reduce, to those which speak C# it is known as Aggregate, in Haskell it is known as Fold, in C++ it goes by the name Accumulate, ... we could go on like this for a while.  Again the point is that these names are all for the same idea of the higher order function Fold.


A Fold takes a collection and applies one function against each member of the collection and an accumulated result (also known as a memorize).

A very simple example of Fold would be summing.


We see in the image above that we are taking the collection 1, 2, 3, 4 and summing it up to the value of 10.  We do this by taking member 1 and the seed value of 0 and adding them together to get 1.  Next, we take the accumulated value of 1 and add the next member 2 to it giving us 3.  Then, we take the accumulated value of 3 and the member 3 add them and get 6.  Last, we take the accumulated value of 6 and the member of 4 giving us the final result of 10.

In Clojure and C# this would look like the following:



Mapping Map to Fold


... and birds go tweet, what is the point?  Glad you asked, we see with both Map and Fold some similarities.

  1. applying a function against each member of a collection
  2. building a resulting collection
Let's look at the first Map example again.  We see that we applying a function against each member of a collection and are accumulating a resulting collection, this sounds very similar to Fold.


In fact I would say that if we had an empty collection in which we accumulated the results of applying the function against the members of the collection we would have the same functionality.  That was a lot of words lets have some code.

In Clojure and C# we would have the following:


We see that both Map and the Fold give the exact same result.  In both the Clojure and C# code we see that we need an initial empty collection to store the resulting collection in and place the result of applying the function against a member into the resulting collection (using conj in Clojure and Add in C#).  For the C# code since we are using a List to accumulated the resulting collection instead of an array we need to reshape the resulting collection using the ToArray method.

By looking at this simple example we see that we can reduce Map to a Fold and thus all we need is Fold.  :)