OK, so this isn’t really type-directed programming [PDF]. It’s just a result of Dan Friedman’s Aphorism Number 2: code follows the shape of the data structure. It’s just more obvious in Haskell because the compiler checks that the code conforms to the data structure before letting you run it.

Anyway, I just finished the first draft of the code for my second qualifying paper. It’s heavily symbolic—I’m generating factorial typologies in Optimality Theory. As you might guess from the name, the naive algorithm for this is O(n!). (Just like the naive cryptogram algorithm, incidentally.) I’ve implemented four methods for calculating factorial typologies. Each method has a simple interface:
[Tableau] -> [[Candidate]] (or -> Set [Candidate], I suppose–order doesn’t matter). Tableaux are matrices of numbers with associated candidates, and candidates are just strings.

Despite the simple interface, the insides of each algorithm are quite hairy. I found out, though, that I could usually write the code Python-style (semi-top-down) like so:

sanders :: [Tableau] -> [[Candidate]]
sanders = undefined . map (colify . unzip . snd)
colify (cands, rows) = (cands, transpose rows)

tableaux.map(:snd | :unzip | :colify).undefined

All I’ve written here is the very first step of my top-level function—unpacking and converting tableaux from row-major to column-major form. The compiler will type-check map (colify . unzip . snd), but it allows undefined to take whatever type it needs to fit sanders‘ type signature. This way I can focus on getting the lower-level functions working one at a time, while still sticking them together in the right order at the top.

This allowed me to implement the top-level functions in a very ‘type-directed’ way: I said to myself “now that I have a [([Candidate], [[Int]])] (or [UnzipTableau]), I need to search each one of those for informative subtableau and return the set of winning candidates. So the next step is a function that is [UnzipTableau] -> Set [Candidate]

sanders = undefined . factStep . map (colify . unzip . snd)

From there it’s pretty obvious that I need to turn the set of candidate winners back into a list to get the desired output. So the final top-level function is

sanders = Set.toList . factStep . map (colify . unzip . snd)

Of course factStep is pretty complicated too, but I took the same approach to implementing it. I thought of the problem as transforming the data at each step to a form closer to the desired answer. If I didn’t have a function that did the current transformation, I wrote one. It’s a nice way of looking at the problem, although it is pretty far from the machine—I suspect this code is pretty slow. I suppose I will find out, since the time complexity will be part of my qualifying paper and I plan to profile the execution too.

I’ll be mickle busy this week so don’t expect much more. However, here is my hilarious CL lunch presentation now that it’s done.
I’ll leave you with Surfin’ Safari’s Web Inspector Redesign. Safari gets features about 4 years late, but when it does, it’s the most beautiful thing on earth.