Case analysis

One of my secret tools

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

🇧🇪 I’ll be speaking in September 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 finished another chapter of Runnable Specifications. This one is the Composition Lens Supplement. It’s a twenty page reference detailing ten important algebraic properties. I hope you find it a lot more practical than the “algebra for programmers” writing out there.

---

Case analysis

Recently, a mentee asked me, “How do you think through a problem to solve it?” Nothing came to mind immediately, but we worked through a problem together and I realized there were three big ways of thinking I used all the time. Funny how I’m unconscious until I watch myself do it.

One of them was case analysis. I’ll talk about the two others in future issues.

Case analysis is a method for structured thinking. It basically means that you break your problem into smaller categories of situations (called cases). Then you handle every category. It helps because you can’t figure out the entire algorithm to solve a problem at once. It’s too intricate and big for your head. But each case might be solvable.

Let’s look at an example. Imagine we want to write a function to find an element in a list. We pass the function a predicate and a sequence. The function will return the first element that the predicate returns true for, or nil if it can’t find one.

(defn find-by [pred coll]

There’s the first line. But how do we proceed? Well, there are some easy cases to deal with. The first case is we have an empty collection. We can’t forget that case because it’s the one that we have to stop looking on.

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

We know we should return nil because if we hit the end of the sequence, we haven’t found what we’re looking for. We carved off a case, which makes the rest of the problem easier. I haven’t even thought about how to solve the rest. I just get that down, out of my head.

Now we know we’re looking at a sequence with a first element. Probably we should look at that first element. (This is a hint about the next skill for the next issue.)

When we look at that element, we will have two more cases. The first case is pred returns true for that value. Yay! We’re done.

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

    (pred (first coll))
    (first coll)

That leaves one more case.

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

    (pred (first coll))
    (first coll)

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

And that case is easy because there was nothing left to check.

It may seem like it happened to work out so that the checks were really easy. Often times it doesn’t. For instance, if you did them in the reverse order, the checks would be harder:

(defn find-by [pred coll]
  (cond
    (and (not (empty? coll))
         (not (pred (first coll))))
    (recur pred (rest coll))

    (not (empty? coll))
    (first coll)

    :else
    nil)))

It doesn’t read as well. It’s very hard to see whether I’ve actually covered all of the cases. In fact, I’m still not quite sure. Here are some tips for picking your next case:

1. Prefer cases that are easy to check.

2. Prefer cases whose bodies are simple.

3. Avoid negatives and compound boolean statements.

Remember, the reason we’re doing this is to get the simple cases down into code and out of our heads. Each case we can carve off makes the rest of the problem easier. So go for those easy (sometimes obvious) cases first. It’s a win if you write the obvious case even if you don’t know how to solve the rest.

You do not have to understand the complete solution to make progress. It’s like putting together a jigsaw puzzle. You start with the edge pieces because they’re easy to identify and there are fewer of them. You can do the edges before you even think about the middle.

When you are trying to clean up the code, I’m basically leaning on the natural ordering of cond to simplify things. And sometimes I have to reorder the cases until they’re as simple as I can get them.

But the real trick is even thinking in cases at all. Case analysis is a powerful skill that can even help you outside of programming. But in the rational world of computer programs, it’s an essential skill for breaking down programs. It works for recursive and non-recursive algorithms by incrementally reducing the size of the problem you’re working on. And it lets you make progress without knowing the whole algorithm. In fact, I trust in case analysis so that I can make progress.