Divide and conquer algorithms

The divide and conquer pattern is a widely used functional programming pattern. It lets you turn potentially hard problems into trivial problems and then recombine the answers.

Transcript

Eric Normand: What is the Divide and Conquer pattern? Hello. My name is Eric Normand and these are my thoughts on Functional Programming.

There's a common pattern for implementing algorithms in Functional Programming called Divide and Conquer.

I'll give you an example. If you're going to calculate the length of a linked list, the recursive way of defining that, the standard functional way, is you check if the list is empty. If it's empty, the length is obviously zero and if it's not empty, the length is one plus the length of the rest of the list.

Notice how in both cases, all you have to do is determine if it's empty or not. In both cases, the operation is trivial. There's no decisions to make after that. There's no looping, there's nothing. It's just a simple case analysis and then a trivial return. In the first case when it's empty, trivial return is zero. In the second case, it's one plus the calculation over the rest of the list.

This is the first principle that needs to be true to apply this pattern. That is that the small cases need to be easy because you're dividing the problem. That's where the Divide and Conquer comes from, the divide. You're dividing the problem up into small problems that are each easy to calculate. Often, they're trivial to calculate, there's almost no calculation.

The second part that you need is you have to be able to combine the answers of those trivial problems in some way. In this example, we're combining them with plus. We're doing one, which is the length of the head of the list, and then plus, and then the length of the rest of the list.

https://twitter.com/ericnormand/status/1031194415451308032?ref_src=twsrc%5Etfw

If you have some operation that happens to be associative, which means that the grouping doesn't matter. It means you can actually split the problem up arbitrarily.

In this example I just gave, the list was split into two but two in a very specific place, which was it's split in two right after the head. But you could split it in two right in the middle if that is better for your particular data structure. In this data structure, a linked list, it is the best way to split one off at a time.

Let's look at another algorithm and then apply these principles to see how we can do that. We've got this divide, get to an easy problem where it's trivial, and then put the answers back together. Let's say we're looking for a value in a list. We just want to know yes or no, is this value in this list?

https://twitter.com/ericnormand/status/1045689974211956736?ref_src=twsrc%5Etfw

Let's say we can break up a list arbitrarily. It's more like an array with random access. We want to find the trivial cases where it's almost no decision to make. In this case, we want to handle the...Obviously, we need to handle the empty array. If it's an empty array, the answer is obviously this value is not in the array so it's going to be a false.

In the case of an array of one element, all we have to do is compare the value we're looking for with the element. If they're equal, we return true, if they're not equal, we return false. A tiny little decision there. It's still trivial. There's no logic about searching or anything like that. We have one thing. We're comparing it to another. We're done.

In the other case, it's going to be where we have not zero, not one but more than one, we're just going to split. We're not going to do any real logic. We're just going to split. We're going to divide. Divide the problem and then recombine the answers.

How do we divide the problem? One thing we could do is split the array in two. We'll just figure out where the middle is. Take the length of the array. Cut the array in two, two separate arrays and then recursively find the element, the value in that list on the left, recursively do it on the right, and then we'll recombine them.

When we recombine them, we have to figure out what operation we're going to use. In this case, it's going to be OR. Did we find it in the left? Yes? Great, we're done. OR we didn't find it, let's look in the right. It's an OR. An OR, as we know, is associative.

The grouping doesn't matter. If there's any true anywhere, regardless of how you group, it's going to give you the same answer, true. Otherwise, it'll give you a false.

In that algorithm, those are the three cases. The empty array, trivially false, the one element array, which is trivially just compare the value to that one element, and the more than one array, which is simply split it in two, recursively call it, and OR them together.

Another thing that we notice is that in both of these cases, and I believe it's true generally, the identity value for the operation that we're combining is what we use for the empty array.

In the case of the count, the operation we're using to recombine the answers was plus. When we had an empty array, we used zero as the answer for that. In the case of finding a value, our operation was OR, and so we used the identity of that, which was false when we're dealing with the empty array case.

I think this applies generally. If you take it as a whole, this algorithmic pattern requires those three things now. You need an operation that is associative so that you can split the problem up arbitrarily and regroup the answers later. You need a problem that can be split up into smaller trivial problems, and you need an identity for the super trivial problems like the empty array.

All right. That just about does it for Divide and Conquer. I'd love to hear what your favorite Divide and Conquer algorithms are. I think it's a really useful pattern especially when you're dealing with recursively defined data structures, because the recursion works really well. But it also works on other kinds of things besides lists and vectors and arrays.

It doesn't have to be on a data structure. It could be on any kind of problem that can be split. For instance, if you wanted to, you could determine whether a number was even or odd, by dividing it in two recursively. If you get a zero, then yes, it is even. If you get a one, then no, it is odd. Then you AND them all together. If anybody returns a one, your overall answer is false.

Anyway, let me know what your favorite Divide and Conquer algorithms are. Let me know the most outlandish way that you can do divide and conquer, even when it is probably not the best way. I'd love to see some pretty crazy uses of this pattern. You can tweet me. I'm @ericnormand on Twitter. All right, see you later.