Givens + needs

How a trick I learned in Physics class is key in functional programming

👨‍🏫 No office hours this week. I’m retooling and figuring out the format. Stay tuned.

🇧🇪 I’ll be speaking next week at Heart of Clojure in Belgium. Get your tickets for 10% off with this magic coupon link. This looks like one cool Clojure conference.

📖 Grokking Simplicity has passed 14k copies sold! That’s not bad for a programming book. If you want a copy, please buy it on Amazon because it boosts the rank so people who want it find it. Leaving a review will help, too, because it will help people decide whether to buy. You can also find Grokking Simplicity on O'Reilly Online.

📖 I would love any comments you have on Runnable Specifications. The latest “chapter” is the Composition Lens Supplement. It’s a twenty page reference detailing ten important algebraic properties. My questions are: Is it useful? What’s missing? How’s the presentation?

---

Givens + needs

My physics teacher in college used to make us list out the given values, the needed values (the values we needed to provide as an answer), and the equations we knew that used those values. I balked at the idea. I had taken physics in High School, so many of the problems seemed easy to me. I didn’t need to write those things down…

Until I started getting to the problems we hadn’t covered in High School. They were trickier. There were fewer knowns, and they weren’t just plug numbers into an equation and solve for x. You usually had to use two or more equations in steps. Once the easy problems were out of the way, these small disciplines were important for making the connections you needed. By doing that little bit of work, the medium problems became easy again.

And it turns out that this is exactly the kind of discipline that helps us define functions and solve problems in code. And, lucky us, the language syntax makes us do the work.

You see, the givens of any function are its arguments. They happen to be variables (that represent some quantity that will be known later when the function is called). And the needed value is the return value. Our job, much like in physics, is to relate the givens to the needed value.

I was mentoring someone the other day, and it struck me how much they needed this discipline. As I was helping them through a problem, I also realized how much I was doing it in my head unconsciously. I was listing the possible operations on the arguments and the possible operations that yielded the return value, and I was trying to forge a path between them. I suppose for a big enough skill difference between mentee and mentor, it would start to seem like wizardry. But it’s very mundane. Let’s look at the same example we saw last week, the function find-by. Here is the signature:

(defn find-by [pred coll]

Look at those two arguments. pred is a function of one argument that returns true/false. coll is a collection, which really only has a handful of possible operations:

1. empty?

2. first

3. rest

4. conj

The funny thing about abstraction (we don’t know what type of collection) is that it helps us by limiting what we can do. I think not knowing the type used to give me anxiety because when abstraction is done wrong, you need to do a lot of work to figure out what type it is, and I coded a lot in systems with bad abstraction. But in this case, it’s not like that. We don’t want to know whether it’s a set or a vector or whatever.

Knowing what find-by does also tells us that pred will be called on the elements of coll. Let’s start to make a list of this stuff:

• Givens

  • pred - function from elements of coll to true/false

    • The only thing we can do is to call it on an element of coll.

  • coll - a collection

    • empty? - check if the collection is empty, dividing all collections into two “cases”

    • first - the first element of a non-empty collection

    • rest - get another collection containing everything but the first element

    • conj - add another element to the collection

    • count, drop, take, etc. are also candidates

• Needed

  • The first element of coll that pred returns true for OR

  • nil if there isn’t one

I posit that this is dead obvious to anyone skilled in Clojure. But to a newbie, it may be difficult to generate. And, admittedly, there are many operations on collections that I did not list because I know they are not needed. These include map, filter, reduce, partition, concat, etc. These can be learned over time. And they are built out of the first four (empty?, first, rest, conj), so they’re basically shortcuts.

This list of givens and needed, plus a little case analysis, will get you there with no muss. Let’s take a look.

First, we can’t call first and rest on coll because we don’t know if there is a first element (and what would we do with the nil it returned?). coll could be empty. And we don’t have anything to put into coll, so we can’t call conj. It really only leaves empty?, which gives us our first case:

(defn find-by [pred coll]
  (cond
    (empty? coll)

And we know that if we have an empty collection, we have not found what we are looking for, and the spec says to return nil in that case.

(defn find-by [pred coll]
  (cond
    (empty? coll)
    nil

Now, in the next case, we know it’s non-empty. We don’t need empty? anymore. We could get the first element or the rest of the elements. We can’t conj because we still don’t have one.

If we get the first element, that will let us subdivide into two cases again by using pred. So let’s get the first element. Notice that I had to think one step ahead to decide. We have limited lookahead ability, but one step is within that limit.

(defn find-by [pred coll]
  (cond
    (empty? coll)
    nil

    (pred (first coll))

Now, if pred returns true, we are done! It’s easy to see that this fulfills the needed: The first element, if it returns true for pred, is the first element that returns true for pred. So we return it.

(defn find-by [pred coll]
  (cond
    (empty? coll)
    nil

    (pred (first coll))
    (first coll)

Now we know that (pred first) is not true. We need to handle that case. We don’t need empty?, we don’t need first (it’s useless now), and we don’t have anything to conj. So we need the rest. Now here’s a trick that we didn’t put on the list, which we should have: You can always call the function you’re in recursively.

• Knowns

  • find-by - takes a predicate and a collection

And guess what: We have a predicate, and rest will give us a new collection! And because it’s in tail position, in Clojure we should use the recur form:

(defn find-by [pred coll]
  (cond
    (empty? coll)
    nil

    (pred (first coll))
    (first coll)

    :else
    (recur pred (rest coll))))

And we’re done. We listed out all of the givens (the arguments), the operations that apply to the givens, and the needed values. Then, at each step, we used the process of elimination to figure out what to do next. Occasionally we needed to think one extra step ahead. In more complex code, sometimes the elimination will leave you more than one option to explore. But it is surprising how much the simple process of elimination can make the path ahead obvious. Try it on problems you find challenging.

As you practice this method, you’ll find that your mind eliminates options faster. The right next step will pop out to you brighter and quicker. You’ll be able to do more challenging problems. You will not need to externally list the givens and their operations. You can do it in your head.

But that takes time. I remember when I taught math. Students were writing just the final answer, and if it was wrong, I had no idea how they got it. I asked them to show their work. The students groaned, “Why do we have to do all of that?”

“Well,” I replied, “if you get the answer right, it doesn’t matter. You get full credit. But if you get the answer wrong, I have nothing to grade. I can’t give you partial credit. If you show me the steps, I can give you one point per correct step.”

They groaned again. Some of them did start doing it, and they got partial credit. But the ironic thing was, those who did it were more likely to get the answer right. They were more careful. They had extended their working memory to the paper. But, also, they practiced the discipline of listing the givens, the formulas, and the needed values. The repetition made it easier for them to recall them. And they got better faster. By the end of the class, they could do it in their heads and write just the correct answer.

Sometimes I wonder if I should have been more strict on that. If a kid can’t understand the logic of partial credit (as I couldn’t as late as in college physics), maybe the logic of immediate reward/punishment could have gotten them to do it, and they’d be better off.

It took me a long time to learn that when someone makes something look easy, it’s probably because they worked really hard to develop a high level of skill. So instead of doing what the best mathematicians do, which looks like they just write a number down, perhaps trusting their intuition, we need to do what they did to get there, which was careful practice.

So, no matter what your current skill level, you have an edge of challenge. What you do at the edge determines if you improve your skill or stay at that level. When you get stuck, you’re now a beginner again. Go back to the basics. Write out what you know. Start to eliminate possibilities. Look a few steps ahead. Do a case analysis and get the easy ones out of the way. This is how we grow.

---

This essay was partly inspired by a lecture by Edsger Dijkstra, structured thinker extraordinaire: