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
foreach (var deck in shuffle(cards))
will return a list:
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
var sides = new List
foreach (var deck in rotate(cards, sides))
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
var newList = new List
public static List
var newList = new List
foreach (int i in Enumerable.Range(pos, arg.Count – pos))
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.
var copy = new List
var unusedItems = from card in cards
foreach (var item in unusedItems)
if (copy.Count == cards.Count – 1)
yield return copy.Append(item);
foreach (var cardList in shuffle(copy.Append(item), cards))
yield return cardList;
return shuffle(new List
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…
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.
var olist = new List
var o = olist;
foreach (var i in inner)
var newResult = new List
outer = o,
inner = i
if (olist.Count == 1)
yield return newResult;
var f = rotate(olist.Tail(1), inner, newResult);
foreach (var foo in f)
yield return foo;
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
FWIW, the implementation of Tuple is very simple:
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.
Nearly half of the kid’s at my child’s school have parents who work at Microsoft, but otherwise it is quite diverse. There are a couple of families from Palestine, one from Tibet, and the bulk coming from China, South and Central Asia, Middle East or Eastern Europe (in about that order). I’m not aware of a single kid from a traditional WASP family, although there might be a few.
So I was pleasantly surprised when the school invited parents to hear the children sing in a “holiday sing-along”. There had been no celebrations for Moon Festival, Diwali, or Ramadan, and I knew that several of the children don’t celebrate Christmas, so I wasn’t sure how it would work out. But the kids started out strong with a few secular carols like “Jingle Bells”, and none of them seemed to be too uncomfortable.
Then they launched into an energetic rendition of “Happy Hanukkah”, all singing cheerily about “lighting the menorah”. There is a decidedly uncomfortable air in the room as parents glance around, wondering what’s coming next. Everyone winces in anticipation as the following song begins, loudly, “WE WISH YOU A MERRY…”
The children continue, “…HOLIDAYS, WE WISH YOU A MERRY HOLIDAYS, WE WISH YOU…”. All the parents let out sighs of relief as disaster is averted. Asking children to utter the words, “MERRY CHRIS-MAS”, and thus affirm the birth of Chris, would have been unbearably offensive. Especially to menorah-lighting Palestinians or Tibetans who have been oppressed by Chris for so long.
Yes, I’m being a little bit sarcastic, but the truth is that I have no problem with Chris. I have several friends named Chris. The real problems come when people run around singing about CHRIST this time of year.
Last weekend, while shopping at J.Z. Rose (the store attached to the skybridge from MSFT Lincoln Square office), I was delighted to hear carolers in the store. The Dickens Carolers, dressed to the gills in traditional Victorian garb, were pleasing passers-by with traditional songs. J.Z. Rose is a rather pagan, practically Wiccan store, and they had obviously hired these people to sing. So I wasn’t prepared for what happened next. The carolers began some vaguely familiar ditty about “Holly and Ivy”, and then one of them blurted out something about “Our Lord Jesus Christ”. Again it happened! And then, again! Were they not aware that there were people watching?!?!
It was like a sword cut through the audience. I could see a small cadre of watching fundies, no doubt emboldened by this public display of power, plotting to invade all of our homes and take away our porn. With each new utterance of “Our Lord Jesus Christ”, their backs became straighter, their lips narrower, and their eyes colder. Looking as us. For the secularists in the crowd, the first utterance was like a slap across the face. Then with each repetition, they became paler and more listless, like animals ready for the slaughter. They would have run around in desperate frenzy, for fear of the loss of porn, were it not for their energy being sapped.
Today I discovered and took Andy Rutledge’s little designer quiz. I got only two questions wrong, and one of them I knew the answer but got wrong on purpose (triangles suck!). But this doesn’t mean I’m a designer. It simply means that I’ve been immersed in design ideas for the past year. If I had taken the quiz a year or two ago, I would have gotten most of the questions wrong.
It’s nice to see some validation that my mind is expanding, but sometimes I worry about whether all of this “fluff” is causing me to loosen grasp of my past strengths. Another post I discovered today is this little bit on printing floats in Erlang. It appeared to me that this was the exact opposite of the designer mentality; getting *exactly* the right bit of code needed to do something like print a number. So pedestrian, but so familiar. I thought back to the times when Derek Denny-Brown and Andy Kimball were rewriting our number formatting routines for System.Xml, and back to the times I’d needed to do the same for CAD, accounting, or other systems years earlier. I looked at the Erlang source, and it took me back to when I did the same implementation in scheme. It warms my heart to see that people still care about things like this.
Today was the funeral for a co-worker. He was a year younger than me, with an infant son and two very sick parents. A terrible tragedy, he was cut down by an undetected and unexpected illness with only a week or two of warning.
The pastor at the funeral service exploited the tragedy to the maximum in an attempt to harvest souls. The pastor, speaking in Chinese with repetition by the English translator, painted a rather surreal picture. He explained that the deceased had found religion upon realizing that he was about to die, and that the deceased had essentially bargained with God; promising to testify on God’s behalf if God would spare his life.
Completely dodging the implications of making such a bargain when God calls your bluff, the pastor then lurched on to assert that “God *could* have saved the deceased, but sometimes God kills someone as a way to make people pay attention and submit to Jesus”. He repeatedly drew parallels between the death of the deceased and the passion of Christ, exhorting the largely Chinese (and no doubt shrewd) audience to respond to the propaganda and take the bargain.
I’m sure he thought he was doing the right thing, but the crass manipulation makes me want to puke. And the kindest thing that can be said of the theology is that there are serious questions to be raised. The people who respond to such arguments are not the people he wants; and the people he wants will be repulsed by such arguments. The end does not justify the means.
I think of the Drew Peterson case in current events, where it seems likely that this police officer killed two of his wives. The news recently has been rife with examples of police officers doing bad things, and people wonder who they can trust. Drew Peterson was a senior police officer with a son who is also a police officer, so it’s surreal to observe that he would probably pass a polygraph while reciting bald-faced lies.
Based on recent events, would you tell your children that police officers are murderers? More to the point, would you tell your children that a career in law enforcement would be unethical?
In the face of authorities who are often corrupt, people need to make judgments and decide whom to trust. Do you decide that all authority is untrustworthy, or do you refine your judgment and take a calculated risk with your revised definition of authority? It sure would be nice if all authorities were trustworthy and such questions never arose, but it would be boring as well. Capacity to judge is a defining human characteristic.
This funeral adds to three other tragedies in the past month, touching people I’ve known for years (memoriam via Dare). I knew Anita for nearly 10 years, and same for Uche, whose 3 young nieces were taken. Marc I only followed, but never met. Such tragedies give me a deeper sense of gratitude for the durability of good friend William Loughborough, who has emerged intact from a couple of situations in the past year. And also reinforce my resolve to live in a way that remains at peace with my own mortality.
When I was single, ten plus years ago, I was always “ready to die”. But having a wife and (especially) kids changed the equation immensely. It’s impossible to really explain how that changed things. But now, since last December or so, I’ve put things in order and am at peace with my own mortality and whatever happens to my obligations here. If I died tomorrow, there would be nothing to keep my anxious geist around. Hopefully I can maintain this state until I die many years from now.
Coincidentally, I’ve had three major losses of data/memory in the past few months:
- First, I decided to use my backup drives to temporarily do video processing for my job, since “what are the odds that the master will crash?”. I lost 3 years worth of e-mails and photos.
- After spending a couple of thousand dollars on hard drive recovery that was less than 50% successful, I once again “borrowed” my personal backup drives for work purposes — one at my office and one to fedex to a co-worker. Thinking, “what are the odds that a drive would crash again within just a few months?” The (new) data drive crashed two days ago and I’ve not yet attempted recovery. Assume the worst.
- I type notes to myself via e-mail from my phone. I queue notes for several weeks before sending. Today my phone completely crashed, losing more than 2 months worth of notes that had been stored in the “drafts” folder of the phone without being sent.
Every loss of personal history is a shattering pain. The loss of the notes from the phone is the most painful. I might as well have not lived for the last two months, and there is no guarantee that I’ll ever be able to replicate what was stored there. But I’ll neither bargain nor complain — what’s lost is lost.
Wow, this could be very, very ugly. Years ago, I discussed the subprime situation with some CXOs from a couple of the biggest banks in the US, and they knew then that the day of reckoning would come. They used words like “suicidal” to describe the banks who brought this mess upon us, and were convinced that even banks like Wells Fargo would go under within 18 months. But as the saying goes, the markets can remain irrational longer than you can remain solvent. So I marveled at their resolve to stay far away from the mess, tighten their belts, and ride it out until judgement was meted out on the wicked. It’s been longer than 18 months, now, and their patience hasn’t yet been rewarded — but by now everyone with half a brain can see that the high-flying wicked are collapsing into ruin.
This is why I am shocked at the proposed bail-out plan. Umair says:
In fact, it’s you and me that the banks are offloading their moral hazard/junk onto. Who pays? You and me – the taxpayers. Unbelievably, we’re bailing out the banks, and essentially retroactively paying the Street’s bonuses.
He should specify that he’s only talking about the suicidal banks, since not all of the banks were dirty. And while it is indeed bad that these jerks will not only escape prison, but will further rape the economy; this gets to the other point. This bailout essentially penalizes anyone who rode this out and stood to benefit in a big way when the carnage hit. All of that righteousness was for nought, and in fact is being punished.