Reducing vs decomposing

A small distinction which I remembered about today – it was in the SICP videos I watched a while ago. If a problem A can be reduced to a simpler problem B, then once you’ve made that step you can forget about problem A entirely, safe in the knowledge that the answer to B will do just as well. In contrast, a problem which can be decomposed into sub-problems might yet require the sub-answers to be combined in some way to get the final results. Therefore, you need to do more bookkeeping in order to track the results of the subproblems.

To a programmer, this is just the difference between a tail-call and a non-tail call. But the insight pertains to how some programmer use the phrases “reduces to ..” and “decomposes into ..” to mean two subtly different things.


Turns out, programmers aren’t the only ones with neat monkeytools. I just learned that painters use mahlsticks to provide a temporary stable platform to support their hands whilst painting fiddly details. Artmonkey make clever tools! Weldingmonkey might copy artmonkey!

Haskell-meet-Erlang; (incl. Agile Sumo Wrestling)

Simon Peyton-Jones compares Haskell and Erlang. A good, fun historical tour of Haskell during a recent Erlang conference. I do enjoy watching talks where the presenter isn’t just preaching to the converted. Over the past few days, I’ve been writing a haskell IRC bot in an erlang message-passing style so this haskell/erlang video makes me wonder if there’s some kind of wormhole universe link-up going on!

307 Temporary Redirect

This blog has been quiet recently because, for the next month, I’m focused on my imminent 1,000 mile cycle ride from Land’s End to John O’Groats. I started a separate blog to track my training and progress if you’re interested!