Two Tricky Routines Using C# 3.0

I received a rather difficult puzzle for Christmas, and decided to cheat by writing a program to solve the puzzle. I decided to write two different C# programs to solve the puzzle, one imperative and one functional, and then compare in Python and Scheme. I wanted to see how easy functional programming is in C# 3.0.

I was able to easily solve using both styles in C#, and Python is even easier, but before I write a post detailing my findings, I wanted to document the two trickiest parts of my “functional” solution. The code is much tighter and more elegant than the imperative version, but I am not satisfied with it. I was forced to use the yield keyword for both routines in both C# and Python, and this bothers me. I know that I have done routines like this in Lisp and Scheme in the distant past, and I didn’t need yield then. I need to think this through some more before porting to Scheme.

The two routines I needed to implement are very generic, I am sure I have seen implementations in college textbooks and maybe even standard libraries. I invented my own implementations anyway, since they were the only interesting parts of the program:

Routine 1: Shuffle

Define a function, named Shuffle, that takes a list of unique objects and returns all possible orderings of those unique objects. If there are n objects in the list, there will be n factorial lists returned. For example,
var cards = new List { “K”, “Q”, “J”};

foreach (var deck in shuffle(cards))
Print(deck);

will return a list:

[K,Q,J]
[K,J,Q]
[Q,K,J]
[Q,J,K]
[J,K,Q]
[J,Q,K]

I’m aware the “shuffle” isn’t the most appropriate name. Don’t let the name confuse you, just focus on what the function does.

Routine 2: Rotate

Define a function, named Rotate, that takes two lists and returns a list of tuples having cardinality of the first (outer) list and expressing all possible combinations of the two lists. This is sort of like a cross-product. Perhaps an example will explain better:
var cards = new List { “K”, “Q”, “J”};
var sides = new List { 0, 1 };

foreach (var deck in rotate(cards, sides))
Print(deck);

will return a list:

[ (K,0) , (Q,0) , (J,0) ]
[ (K,0) , (Q,0) , (J,1) ]
[ (K,0) , (Q,1) , (J,0) ]
[ (K,0) , (Q,1) , (J,1) ]
[ (K,1) , (Q,0) , (J,0) ]
[ (K,1) , (Q,0) , (J,1) ]
[ (K,1) , (Q,1) , (J,0) ]
[ (K,1) , (Q,1) , (J,1) ]

Note that we are returning a list of tuples this time, and the order of the outer object list (”cards”) remains constant in this function. The point of this function is to create tuples from all combinations of the inner list (”sides”). Also note that the inner list here can have duplicates — for example, in the first row, all cards are turned to side 0, and in the last row all cards are turned to side 1. This function must support inner lists with more than 2 items; I simply used a 2 item list here to save space.

Implementation: Helper Functions

I hacked two simple extension functions to make my code more readable. I’ve pasted it here in case the implementation is not obvious enough from usage:
static class MyExtensions
{
public static List Append(this List arg, T val)
{
var newList = new List(arg);
newList.Add(val);
return newList;
}

public static List Tail(this List arg, int pos)
{
var newList = new List();
foreach (int i in Enumerable.Range(pos, arg.Count – pos))
newList.Add(arg[i]);
return newList;
}
}

Implementation: Shuffle

I just walk through the list of cards, recursing on the unused items at each level to get the unique cards. Very simple implementation. The “list” parameter starts out as an empty list (initialized by the helper overload below), and is built up recursively to the output.
static IEnumerable> shuffle(IEnumerable list, List cards)
{
var copy = new List(list);

var unusedItems = from card in cards
where !copy.Contains(card)
select card;

foreach (var item in unusedItems)
{
if (copy.Count == cards.Count – 1)
yield return copy.Append(item);
else
foreach (var cardList in shuffle(copy.Append(item), cards))
yield return cardList;
}
}

static IEnumerable> shuffle(List cards)
{
return shuffle(new List { }, cards);
}

You can see where I got into trouble by requiring yield. I started out well enough, using the “from … where” syntax that is composable. But I couldn’t figure out how to use the “from … where” syntax to test my recursion exit condition (copy.Count == cards.Count – 1), while still maintaining the nesting. So I was forced to switch to an “if … else” block with nested “foreach”. Is it possible to nuke the foreach and thus the yield, while still doing recursion? I will think about it…

Implementation: Rotate

The implementation of rotate is pretty simple, too. It uses the exact same recursion pattern, but needn’t check to validate that the item is unused this time. It builds up the list of tuples by passing recursively, starting with an empty list of tuples that is initialized by the helper method below again. We track the recursion exit more simply this time: we just keep popping items off of the outer list and when we run out of items we know we’re done.
static IEnumerable> rotate(IEnumerable outer, IEnumerable inner, IEnumerable result)
{
var olist = new List(outer);
var o = olist[0];

foreach (var i in inner)
{
var newResult = new List(result);
newResult.Add(
new Tuple
{
outer = o,
inner = i
}
);
if (olist.Count == 1)
yield return newResult;
else
{
var f = rotate(olist.Tail(1), inner, newResult);
foreach (var foo in f)
yield return foo;
}
}
}

static IEnumerable> rotate(IEnumerable outer, IEnumerable inner)
{
return rotate(outer, inner, new List { });
}

I ran into the same complication with checking the recursion exit condition here, so ended up using nested “foreach” and “yield” again. Once I figure out how to express this in “from … where” syntax, it should look cleaner.

My biggest annoyance about this routine was the need to define a Tuple class. I couldn’t figure out how to use a generic type here, and it just looks ugly. I couldn’t make it work with an anonymous type either. I should be able to define the function with and just return a list of anonymous types, and let the code figure it out — but since I needed to also pass in the arguments (because of recursion), the compiler insisted on precision. This kind of crap is not necessary in Python.

FWIW, the implementation of Tuple is very simple:
class Tuple
{
public object outer;
public object inner;
public override string ToString()
{
return ” (” + outer.ToString() + “,” + inner.ToString() + “) “;
}
}

Programming with the new functional syntax of C# is a complete joy. It feels a lot like programming Python and gives me flashbacks to Lisp and Scheme. But there are still a couple of areas where Python syntax is still easier. Additionally, I kept thinking in terms of Lisp, where I can just combine nested lists without worrying about type; or where I can split, head, and tail. C# may have similar List routines, but I couldn’t find them. Having to deal with type on the recursion is confusing to me (just merge the freekin’ lists!), but that is probably some stupidity on my part since I was unable to implement in Python without using yield either.

Leave a Reply

Your email address will not be published. Required fields are marked *