The Stable Marriage Problem

It's been far too long since I wrote posts with any real code in, so in an attempt to get back into good habits I'm going to try to write a few more posts and read up a bit more about some algorithms and the history behind them.

The Stable Marriage Problem was originally described by David Gale and Lloyd Shapley in their 1962 paper, "College Admissions and the Stability of Marriage". They describe the problem as follows:

A certain community consists of n men and n women. Each person ranks those of the opposite sex in accordance with his or her preferences for a marriage partner. We seek a satisfactory way of marrying off all member of the community. We call a set of marriage unstable if under it there are a man and a woman who are not married to each other, but prefer each other to their actual mates.

Gale and Shapley shows that for any pattern of preferences it's possible to find a stable set of marriages.

On its own, this doesn't sound very interesting. However, bringing together resources is an important economic principle and this work formed part of the puzzle of Cooperative Game Theory and Shapley was jointly awarded the Nobel Prize for economics in 2012.

So how does the algorithm for Stable Marriages work?

Let's start by defining the problem. Given two lists of preferences, find the match such that there is no unstable match (that is two pairs that would cooperatively trade partners to make each other better off). The only constraint the types have is that they have is that they are equatable. This isn't the ideal representation (to put it mildly) in a strongly typed language (it doesn't enforce any invariants about the structure of the lists), but it's probably the simplest representation for explaining the algorithm.

stableMatch :: (Eq m, Eq w) => [(m,[w])] -> [(w,[m])] -> [(m,w)]

The algorithm continues whilst there are any unmarried men. If there are no unmarried men, then the algorithm terminates.

  stableMatch :: (Eq m, Eq w) => [(m,[w])] -> [(w,[m])] -> [(m,w)]
  stableMatch ms ws = stableMatch' []
    where       
      stableMatch' ps = case unmarried ms ps of
        Just unmarriedMan  -> stableMatch' (findMatch unmarriedMan ws ps)
        Nothing            -> ps

  unmarried :: Eq m => [(m,[w])] -> [(m,w)] -> Maybe (m,[w])
  unmarried ms ps = find (\(m,_) -> m `notElem` engagedMen) ms
    where
      engagedMen = map fst ps

If there is at least one unmarried man, then we need to find a match. We do this by proposing to each of his preferences in turn. If his first preference is not engaged, then we propose. Otherwise, if his potential partner is already engaged and would prefer him then this violates the stable marriage principle and we breakup the engagement and re-engage with our first choice.

findMatch :: (Eq m,Eq w) => (m,[w]) -> [(w,[m])] -> [(m,w)] -> [(m,w)]
  findMatch (m,w:rest) ws ps = case isEngaged w ps of
      
    -- w is already engaged to m' - is there a better match?
    Just m' -> if prefers (getPrefs ws w) m m'
               then engage (breakup m' ps) m w
               else findMatch (m,rest) ws ps
                      
    -- can match with first choice
    Nothing -> engage ps m w

You can see the full code at Stable Marriage Problem. As always flames, comments and critiques gratefully received.

Getting the most out of Extract Class

Resharper is a wonderful tool. I can't imagine working in the horribleness of legacy code without it.

Every so often you come across a little workflow that makes slicing and dicing code either. For example, before you could "Move Instance Method" you could "Make Static", "Move Method" and "Make instance method". Knowing you could do this made tearing code apart easier.

Recently I've been using "Extract class" a million and one times to deal with one of those 10K line long classes that no-one ever admits to having. The classes in question are in this:

class DoesEverythingAndThenSome {

       private ThingToDoWithA1 m_ThingToDoWithA1;
       private ThingToDoWithA2 m_ThingToDoWithA2;
       private ThingToDoWithA3 m_ThingToDoWithA3;

       private ThingToDoWithB1 m_ThingToDoWithB1;
       private ThingToDoWithB2 m_ThingToDoWithB2;
       private ThingToDoWithB3 m_ThingToDoWithB3;

       // repeat for thousands of other "things"

       public void DO_ALL_THE_THINGS_WITH_A () {

       }
   
       public void DO_ALL_THE_THINGS_WITH_B () {

       }

       // thousands of lines of random shit
       public void example_of_random_shit () {
          if (incrediblyComplicatedCondition()) {
             for (var apples in bananas) {
               m_ThingsToDoWithA1.SomethingImportant();
             }
          } else if (auberginesAreLumpy()) {
             m_ThingsToDoWithB.SomethingElse();
          }
       }
    }

Obviously I want to extract out the responsibilities to do with A and B into separate class. Using "Extract Class" directly doesn't work because I can't pull out the references in example_of_random_shit without making properties public and introducing back references from the extracted class to the parent class.

The simple refactoring is to just extract out each line to do with each field into a single method.

class DoesEverythingAndThenSome {

       /* the rest is the same as above */

       public void SomethingToDoWithA() {
           m_ThingsToDoWithA1.SomethingImportant();
       }
 
       public void SomethingToDoWithB() {
           m_ThingsToDoWithB.SomethingElse();
       }

       // thousands of lines of random shit
       public void example_of_random_shit () {
          if (incrediblyComplicatedCondition()) {
             for (var apples in bananas) {
                 SomethingToDoWithA();
             }
          } else if (auberginesAreLumpy()) {
             SomethingToDoWithB();
          }
       }
    }

Once I've completed this simple refactoring, "Extract Class" can now do the heavy lifting and I can move all the fields, and all the functions across in a single refactoring. What was previously hard (unpicking the back references) is now incredibly simple and I end up with a mechanical transformation to get data and functions in the right place. Extract class will now give me:

class ThingsToDoWithA {
       private ThingToDoWithA1 m_ThingToDoWithA1;
       private ThingToDoWithA2 m_ThingToDoWithA2;
       private ThingToDoWithA3 m_ThingToDoWithA3;

       // snip constructor

       public void DO_ALL_THE_THINGS_WITH_A () {

       }

       public void SomethingToDoWithA() {
           m_ThingsToDoWithA1.SomethingImportant();
       }
    }

    class DoesEverythingAndThenSome {
       
       private ThingToDoWithA m_ThingToDoWithA;

       private ThingToDoWithB1 m_ThingToDoWithB1;
       private ThingToDoWithB2 m_ThingToDoWithB2;
       private ThingToDoWithB3 m_ThingToDoWithB3;

       // snip constructor

       // repeat for thousands of other "things"
   
       public void DO_ALL_THE_THINGS_WITH_B () {

       }

       // thousands of lines of random shit
       public void example_of_random_shit () {
          if (incrediblyComplicatedCondition()) {
             for (var apples in bananas) {
               m_ThingsToDoWithA.SomethingImportant();
             }
          } else if (auberginesAreLumpy()) {
             m_ThingsToDoWithB.SomethingElse();
          }
       }
    }

Repeat this mechanically for all the other responsibilities Then the hard work begins of actually working out sensible names...

How does it feel to give a terrible conference talk?

Have you been to a conference and sat through an awful presentation and wondered just how the hell someone got there? Me too!

Recently I attended the ACCU conference in Bristol and got to experience what it feels like to deliver something that went down like a lead balloon. One evening many moons ago, I thought I'd send in a proposal. By some small miracle I got accepted and was all set to run a 90 minute introduction to Haskell.

I'd already run through the workshop once at a local user group. The material isn't amazing, but I was confident in delivering it and thought it offered people a chance to get a taste of Haskell and programming with functions.

Then the problems started. It's ACCU. It's full of clever people, therefore I should level-up the material and assume more knowledge. Right? I should make it more hands-on, more interactive and better in every way.

I prepared hard. I updated the slides. I added more and more. I wrote notes, I dug references and I was confident it would kick-ass.

And then the day arrived.

90 minutes seem like a long time. It isn't. I spent a good 15 minutes ensuring that everyone could run "hello world". Very rapidly 90 minutes because 60 minutes.

Then my cleverness got the better of me. The Curry-Howard isomorphism is fascinating, but perhaps it's not the best subject matter within the first 30 minutes of any presentation. Trying to explain it under pressure with questions from an audience eager to learn makes it even worse. I probably lost another 20 minutes trying and failing to explain that const :: a -> b -> a only has one valid implementation in Haskell. And what the hell are the poor attendees going to do with this information? GAH!

And so it continued. On to writing some code. I'd wanted to make it easier to compose higher order functions to produce results, so I'd made the initial data structures in the exercises a bit more complicated than those I'd shown in the example slides. Big mistake. This made it much harder for people to grok the syntax; I'd shown simple syntax but not given enough direction. 30 minutes rapidly disappeared and I'm now *way* behind schedule.

At this point, I'd already realized the situation was going Pete Tong. But what'd you do? You can't just down tools and walk out the room (well, I suppose you could, but that'd be worse), so you just have to knuckle down and carry on. And carry on I did, through more examples (well over-egged) and then onto the Universality of Fold (brain, what the hell are you thinking?!).

With 5 minutes left, there's plenty of time to through a demo of QuickCheck in, right?But then, I realized I'm in an Emacs buffer. How'd I increase the font-size so people can read it? GNARGH!! It's over to Notepad and bump the fonts up in that. "Should have used vi!" went the audience. ARGH!

And then the buzzer sounds (well, not really, but it's time to go). Bring things to a halt and escape to a corner of the building. I can't imagine that was particularly fun for the participants. A few people kept up (hurrah!) and there were a couple of positive things said, but I knew it'd gone wrong and it boy that doesn't feel good.

So, at least now I know how it feels (bad, very bad) and I also learnt an important lesson. Keep the message simple! Focus on the single takeaway you want participants to have. I wanted people to leave knowing that Haskell isn't impenetrable and looking at how far you can get just by reading type signatures. However, I lost this in a noise of other random related things and tried (and failed) to communicate a million and one other features.

KISS!