Top-down design in “functional classic” programming
While waiting for my product owner to get back to me, I was going through open browser tabs. I read this from Swizec Teller:
The problem is one of turning a list of values, say, [A, B, C, D] into a list of pairs with itself, like so [[A,B], [A,C], [A,D], [B, C], [B,D], [C,D]].
He had problems coming up with a good solution. “I can do that!” I said, launched a Clojure REPL, and started typing the whole function out. I quickly got bogged down.
This, I think, is a problem with a common functional approach. Even with this kind of problem—the sort of list manipulation that functional programming lives for—there’s a temptation to build a single function bottom up. “I need to create the tails of the sequence,” I thought, “because I know roughly how I’ll use them.”
For me (and let’s not get into all that again), it usually works better to go top down, mainly because it lets me think of discrete, meaningful functions, give them names, and write facts about how they relate to one another. So that’s what I did.
First, what am I trying to do? Not create all the pairs, but only ones in which an element is combined with another element further down the list. Like this:
As I often do when doing list-manipulation problems, I lay things out to visually emphasize the “shape” of the solution. That helps me see more clearly what has to be done to create that solution. There’s one set of pairs, each headed by the first element of the list, then another set, each headed by the second element. That is, I can say the above fact is true provided two other facts are true:
It’s easy to see how I get the heads—just map down the list (maybe I have to worry about the last element, maybe not—I’ll worry about it if it comes up). What are those heads combined with? Just the successive tails of the original list: [2 3], [3]. I’ll assume there’s a function that does that for me. That gives me this entire fact-about-the-world-of-this-program:
Given all that, downward-pairs is easy enough to write:
It’s important to me that I have reached a stable point here. When building up a complicated function from snippets in a REPL, I more often create the wrong snippets than when I define what those snippets need to do via a function that uses them. (I’m not saying that I never backtrack: I might find a subfunction too hard to write, or I may have carved up the world in a way that leads to gross inefficiency, etc. I’m saying that I seem to end up with correct answers faster this way.)
Now I just have to solve two simpler problems. Tails I’ve done before, and here’s a solution I like:
For those who don’t know Clojure well, this produces this sequence of calls to drop:
This does roughly the same work as an iteration would do because of how laziness is implemented.
That leaves me headed-pairs, which is a pretty straightforward map:
This seems like a reasonable solution, doesn’t strike me as being terribly inefficient (given laziness), has a readability that I like, doubtless took me less time than developing it bottom-up would have, and comes with tests (including an end-to-end test that I won’t bother showing).
The whole solution is here.
UPDATE: Yes, I could have used do or even gotten explicit with the sequence-m monad, but that wouldn’t have addressed the original poster’s point, which I took to be how to think about functional problems.
October 7th, 2011 at 1:06 pm
That just seems grossly over-engineered to me. My off-the-top-of-my-head solution is:
(defn pairs [[head & tail]]
(when (not= head nil)
(concat (map (fn [snd] [head snd]) tail) (pairs tail))))
I did this design top-down much like you did. The list I want is the pairing of the head with each element from the tail, along with the pairs from the tail. I also think it’s functional.
I expect it to be as or more efficient than your solution, as it does a lot less manipulation per element. On the downside, it’s recursive, and not tail-recursive, so it’ll chew up stack proportional to the length of the list.
October 7th, 2011 at 1:10 pm
This seems to be overengineered. Here’s my solution:
(defn pairs [[head & tail]]
(when (not= head nil)
(concat (map (fn [snd] [head snd]) tail) (pairs tail))))
It’s top-down (”the list of pairs is the pairs from combining the head with each element of the tail, plus the pairs from the tail”). It should perform as well or better than your solution, since there’s much less mucking about with each element. The downside is that it’s recursive, but I find that occurs regularly with top-down programming.
October 7th, 2011 at 1:55 pm
For me, the first thing I turn to when solving a problem is trying to translate it to a known (and solved) problem. For instance:
(combinations ‘[a b c d] 2)
October 7th, 2011 at 3:08 pm
SB: Looking for existing solutions is fine, but it’s not practice for how to get your head around working with multiple list traversals.
MWM: I’ll have to work it out, but my hope is that all I’m doing is the equivalent of a doubly-nested loop, which is all I was going for. (With the hope that if I made the helper functions local, Compiler Magic would optimize it down into something pretty close to that loop.)
October 9th, 2011 at 1:41 pm
@MWM: Instead of (fn [snd] [head snd]) you could simply use “vector”. And I think you missed (repeat head).
So, your solution, a little bit more concise:
(defn pairs [ [ head & tail ] ]
(when head
(concat (map vector (repeat head) tail)
(pairs tail))))
October 10th, 2011 at 6:09 am
[…] Turns out the internet is super awesome and was more than willing to put me in my place. You guys posted a cumulative of 49 comments (on hackernews and this blog) and Brian Marick even posted a tutorial on approaching functional programming on this example, entitled Top-down design in “functional classic” programming. […]
October 10th, 2011 at 2:07 pm
This version of `tails` is better than mine:
It’s from this post. I don’t know the author.
October 11th, 2011 at 10:38 am
SO one of my co-workers came up with this solution. Thoughts?
def combine(l)
def pair(elem, l)
ret = []
l.each do |e|
ret