Binary search—think positive

1 The cast and characters

The setting is a tutorial on program verification in Agda. Please consult the programme for further details. [See also Appendix A.]

Dramatis personæ

Dramatis locus

A small but pleasant room in some medieval college building.

2 Monday

Synopsis: The tutor is on a mission: she wants to dispel the common misconception that binary search is about searching an ordered table.

Tutor: Good morning class. This week I would like to discuss formalising one of the standard algorithms every programmer and computer science student should know: binary search.

Harry: Aah, searching an ordered table as described by Knuth (1973, Section 6.2.1)? That’s pretty straightforward, isn’t it? We assume that we have a linearly sorted sequence of keys ${K_1\mkern6mu{{{\prec}}}\mkern6mu{{\cdots}}\mkern6mu{{{\prec}}}\mkern6muK_n}$ . Given a key K, we would like to know if there is an index i such that ${K_i\mkern6mu{{{\equiv}}}\mkern6muK}$ . We pick an arbitrary index m with ${1\mkern6mu{{{\preceq}}}\mkern6mu{m}\mkern6mu{{{\preceq}}}\mkern6mu{n}}$ and compare K to ${K_m}$ . There are three possible outcomes with resulting actions:

• • ${K\mkern6mu{{{\prec}}}\mkern6muK_m}$ : we eliminate the keys from consideration.

• • ${K\mkern6mu{{{\equiv}}}\mkern6muK_m}$ : the search is done.

• • ${K\mkern6mu{{{\succ}}}\mkern6muK_m}$ : we eliminate the keys from consideration.

The problem can be solved in logarithmic time, if we iterate this step and the index picked is always the midpoint, ${{m}\mkern6mu:=\mkern6mu\mathord{{{\lfloor}}}\mkern6mu(1\mkern6mu\mathord{+}\mkern6mu{n})\mkern6mu\mathord{/}2\mathord{{{\rfloor}}}}$ . This is really old hat!

Lisa (frowns): That’s a bit too concrete for my taste. I actually prefer Bird&Wadler’s formalisation (1988). Given naturals l and r and a predicate ${P\mkern6mu\mathbin{:}\mkern6mu{\mathbb{N}}\mkern6mu\mathord{{\rightarrow}}\mkern6mu{Set}}$ , we are looking for the smallest index ${{i}\mkern6mu{{{\in}}}\mkern6mu[\mskip1.5mu \mkern6mu{l}\mkern6mu{,}\mkern6mu{r}\mkern6mu\mskip1.5mu]}$ such that ${P\mkern6mu{i}}$ holds. If the predicate is monotone, ${{{\forall}}\mkern6mu{a}\mkern6mu{b}\mkern6mu\mathord{{\rightarrow}}\mkern6mu{a}\mkern6mu{{\preceq}}\mkern6mu{b}\mkern6mu\mathord{{\rightarrow}}\mkern6mu(P\mkern6mu{a}\mkern6mu\mathord{{\rightarrow}}\mkern6muP\mkern6mu{b})}$ , then the problem can be solved in sub-linear time. We pick an index ${{m}\mkern6mu{{{\in}}}\mkern6mu[\mskip1.5mu \mkern6mu{l}\mkern6mu{,}\mkern6mu{r}\mkern6mu\mskip1.5mu]}$ and check ${P\mkern6mu{m}}$ . There are two possible outcomes with resulting actions:

• • ${P\mkern6mu{m}}$ holds: we eliminate the indices from consideration.

• • ${P\mkern6mu{m}}$ does not hold: we eliminate the indices from consideration.

Like in Harry’s setup, the algorithm runs in logarithmic time, if we always pick the midpoint, ${{m}\mkern6mu:=\mkern6mu\mathord{{{\lfloor}}}\mkern6mu({l}\mkern6mu\mathord{+}\mkern6mu{r})\mkern6mu\mathord{/}2\mathord{{{\rfloor}}}}$ .

Lambert: But there is no guarantee that a suitable index actually exists. Did you notice that the programs provided by Bird&Wadler are partial? Likewise, searching an ordered table for a certain key may fail.

Tutor (smiles): These points are all well taken, but I suggest that we ignore them for the moment and start afresh, solving a little puzzle instead. Agreed? [The students nod.]

You are presented with the following sequence of ${2\mkern6mu\mathord{+}\mkern6mu{n}}$ boxes, each containing a natural number. The numbers are hidden from you; only the contents of the first and of the last box is revealed.

Your goal is to find an even–odd pair, two neighbouring boxes such that the contents of the left box is even and the contents of its right neighbour is odd. Open as few boxes as possible.

Lisa: The problem description seems to suggest that an even–odd pair always exists. Perhaps, we should first prove this implicit assumption.

Harry: But is it actually true? After all, the boxes might contain only even numbers, or only odd numbers, or a sequence of odd numbers followed by a sequence of even numbers.

Lisa (frowns again): Harry, these possibilities are ruled out as we can observe that the first box contains an even number and the last box an odd number.

Lambert: So the existence of an even–odd pair depends on a precondition.

Harry: Ah, I see. And we know that there are at least two boxes. That’s another precondition, right?

Lisa: Good point. The proof of existence then proceeds by induction on n. If n is 0, we have found an even–odd pair. Otherwise, we open the second box, the box numbered 1. If we are lucky, it contains an odd number. If the number is even, we remove the leftmost box, the box numbered 0, and apply the same strategy to the residual sequence of ${1\mkern6mu\mathord{+}\mkern6mu{n}}$ boxes. All preconditions are satisfied: there are at least two boxes; the contents of the new leftmost box is even; the contents of the rightmost box is still odd. Consequently, an even–odd pair is bound to exist.

Ken: I guess we can start turning Lisa’s proof into Agda code? I’d like to suggest a small change though: the problem description builds on zero-based intervals. It seems prudent to follow Bird&Wadler’s lead, that is, to consider arbitrary intervals. Otherwise, we need to shift the interval in the recursive step. [The others signal agreement.] The proposition then reads:

The sequence of boxes is represented by a function ${{box}\mkern6mu\mathbin{:}\mkern6mu{\mathbb{N}}\mkern6mu\mathord{{\rightarrow}}\mkern6mu{\mathbb{N}}}$ that maps positions to contents $\dots$

Harry: $\dots$ and the precondition ${{l}\mkern6mu{{{\prec}}}\mkern6mu{r}}$ ensures that there are at least two boxes! Can you remind me what the type means?

Ken: This is actually a ${{{{\Sigma}}}}$ -type, a dependent pair type. In constructive logic, an existential quantification is given by a pair, consisting of a witness and a proof that the witness satisfies the stated proposition. It’s a dependent pair as the proof depends on the witness. In our scenario, this pair consists of a natural number i and two proofs: one holding evidence that ${{box}\mkern6mu{i}}$ is an even number, and the other showing that ${{box}\mkern6mu(1\mkern6mu\mathord{+}\mkern6mu{i})}$ is an odd number.

Harry: Thanks. However, I am not sure that the setup works. I foresee problems with Agda’s termination checker. [ $\dots$ lowers his voice mumbling $\ldots$ ] Agda is pretty picky when it comes to termination.

Lisa Harry is right. My argument is neither inductive on l, nor on r. Perhaps we should represent the interval ${[\mskip1.5mu \mkern6mu{l}\mkern6mu{,}\mkern6mu{r}\mkern6mu\mskip1.5mu]}$ differently, say, by offset and size, so that we can induct over the size?

Tutor: Don’t give up so easily. A few weeks ago, we formalised the strict order on the natural numbers in several different ways. [She pauses.] Anyone?

Lisa Of course! The endpoint l is strictly smaller than r if and only if the difference ${{r}\mkern6mu{{\mathop - \limits^\cdot}}\mkern6mu{l}}$ is positive.

Tutor: Should you need a reminder about notation such as , please check the course material [Appendix A].

Harry: Ah, I see the light. For the task at hand, we could use the variant of the strict order that builds on the difference of the endpoints!

The proposition ${4\mkern6mu{{{\prec}}}\mkern6mu7}$ , for example, is evidenced by , as the difference of seven and four is three. Honestly, at the time I didn’t see the point of formalising the order in umpteen different ways.

Ken: I guess we can start turning Lisa’s proof into Agda code now? May we assume that the predicates even and odd are provided from somewhere?

Tutor: Sure, and you may use the function ${{parity}\mkern6mu\mathbin{:}\mkern6mu{{{\forall}}}\mkern6mu{n}\mkern6mu\mathord{{\rightarrow}}\mkern6mu{even}\mkern6mu{n}\mkern6mu{{{\uplus}}}\mkern6mu{odd}\mkern6mu{n}}$ that decides whether a natural is even or odd.

Harry (busily typing): This is a breeze. When I conduct the case analysis, Agda is able to fill in the rest $\dots$ Well, almost, I have to specify the left endpoint for the recursive call:

The first equation deals with the case that there are only two boxes. Otherwise, we open the box numbered ${1\mkern6mu\mathord{+}\mkern6mu{l}}$ . There are now two cases that we can investigate using . In the first one, the box numbered ${1\mkern6mu\mathord{+}\mkern6mu{l}}$ contains an odd number, evidenced by ${{o{^{\prime}}}}$ . Thus, we have completed the task. In the second case, the box contains an even number, evidenced by ${{e{^{\prime}}}}$ . Here, we recurse on the smaller interval ranging from ${1\mkern6mu\mathord{+}\mkern6mu{l}}$ to r.

Lambert: Sorry, I don’t use Agda on a regular basis. What does ${{1\mathord{+}l\mathord{{{\prec}}}r}}$ mean?

Ken: That’s an Agda idiosyncrasy. Remember that in Agda only a space separates. ¹ The sequence of characters ${{1\mathord{+}l\mathord{{{\prec}}}r}}$ contains no space, so this is one identifier of type ${1\mkern6mu\mathord{+}\mkern6mu{l}\mkern6mu{{{\prec}}}\mkern6mu{r}}$ . The name typically reflects the type.

Tutor: Well done. Lisa’s proof has algorithmic content, detailing a simple search strategy: open the boxes sequentially from left to right until an even–odd pair is found. So the Agda code captures left-to-right sequential search. But, we set out to formalise binary search.

Harry: Ha, that should be easy. We simply change the definition of the standard order on the naturals to reflect the new search strategy. [Starts typing.] Is there any notation for the midpoint or centre of an interval?

Lambert: Good question. I don’t think there is. But, may I suggest one? What about ${\mathord{{{\lfloor}}}\mkern6mu{a}\mkern6mu\boldsymbol{{mid}}\mkern6mu{b}\mkern6mu{{{\rfloor}}}}$ ? The floor brackets indicate that the real midpoint is rounded downwards, and the notation is a slightly shorter than ${\mathord{{{\lfloor}}}\mkern6mu({a}\mkern6mu\mathord{+}\mkern6mu{b})\mkern6mu\mathord{/}2\mathord{{{\rfloor}}}}$ .

Harry: Okey-dokey. [Continues typing.] Voilà. I have simply changed the final line of the datatype definition. The new constructor states that if the midpoint of l and r is greater than l and less than r, then ${{l}\mkern6mu\mathord{{{\prec}}{^{\prime}}}\mkern6mu{r}}$ . The new name reflects the fact that the sizes of the sub-intervals are added.

Lisa (a connoisseur of sequence implementations): Interesting, this reminds me of the difference between standard lists and join lists, well, balanced join lists.

Harry ( ignoring Lisa): $\ldots$ and the implementation of ${{even-odd-pair}}$ can be easily adapted, as well. The recursive cases are now nicely symmetric.

Tutor: Well done, again. We have stressed repeatedly that proving is programming. As programmers, we appreciate that an abstract datatype, like the type of sequences, can be implemented in a variety of different ways. Likewise, an abstract concept such as an ordering relation can be evidenced in many different ways. Choosing a concrete representation for an ordering is as important as choosing a concrete data structure for a sequence type.

Lisa (with a sceptical undertone): It’s a bit odd (pun intended) that the proof doesn’t use any properties of the mid-point, isn’t it? In particular, we do not make use of the fact that the midpoint lies between the endpoints.

Tutor: Oh, is that the time already? Think about Lisa’s objection for tomorrow’s tutorial.

3 Tuesday

Synopsis: By abstracting from a particular search strategy, the tutees steer the development in an unforeseen direction.

Ken: I have given Lisa’s comment some thought and I think she has a point. However, I consider this a feature, not a bug, an opportunity to generalise the development. Do you mind if I share some code with you? [He opens his laptop.] First, I have generalised the two definitions of order.

Both variants of the strict order discussed yesterday can be seen as detailing a strategy, a strategy for exploring an interval. The first captures a sequential search from left to right, the second a binary subdivision scheme. The new type allows us to specify arbitrary strategies. [He glances at his fellow students who look confused.] Ah, sorry, I have renamed the type—I like to think of its elements as interval trees; the names reflect this.

Harry (still confused): So is now

Ken: Yes, and the second constructor generalises . Both constructors take an explicit argument—you will see why in a moment. Perhaps, it is instructive to look at an example tree first? [The others nod in approval.] Here is a strategy for exploring the interval .

Harry: Sorry, I need to draw a picture. [He sketches the interval tree on the whiteboard.] This looks like a binary sub-division scheme to me. Each inner node is labelled with the smallest, that is, the leftmost element of its right subtree. The leaves contain the numbers of the interval from left to right, including the left endpoint, but excluding the right endpoint.

Lambert (addressing Ken): I see, since 17 is not contained in the tree, you use the notation for right-open intervals ² : . You certainly have taken Dijkstra’s advice (1982) to heart!

Tutor (addressing the others): Just in case you haven’t read EWD831: Dijkstra makes an argument why the subsequence of natural numbers should be written ${2\mkern6mu{{{\preceq}}}\mkern6mu{i}\mkern6mu{{{\prec}}}\mkern6mu13}$ , ruling out ${1\mkern6mu{{{\prec}}}\mkern6mu{i}\mkern6mu{{{\preceq}}}\mkern6mu12}$ , ${2\mkern6mu{{{\preceq}}}\mkern6mu{i}\mkern6mu{{{\preceq}}}\mkern6mu12}$ , and ${1\mkern6mu{{{\prec}}}\mkern6mu{i}\mkern6mu{{{\prec}}}\mkern6mu13}$ .

Harry (who is not paying attention): I have seen this tree somewhere. [He turns the pages of TAOCP 3.] Here it is! Knuth introduces “comparison trees” to illustrate different strategies for searching an ordered table; this tree appears in Figure 5 (1973, Page 412) to visualise binary search. We are on the right track!

Ken: May I continue? I have tidied up the signature.

Since the tree constructors take explicit arguments, we no longer need to pass the endpoints explicitly—l and r are now implicit arguments. As a result, the proof is less cluttered.

A leaf signals success, whereas a node marks a decision point.

Harry: That’s pretty slick.

Tutor: Indeed. As an aside, the proposition ${{even}\mkern6mu({box}\mkern6mu{l})\mkern6mu\mathord{{\times}}\mkern6mu{odd}\mkern6mu({box}\mkern6mu{r})}$ is a lovely example of a functional invariant. In case you have not come across this concept before, the life-cycle of an invariant can be divided into three phases:

• The invariant is established (birth): this is the responsibility of the caller, the function that invokes ${{even-odd-pair}}$ .

• The invariant is maintained (life): this is the responsibility of the callee. In our example, ${{even-odd-pair}}$ adjusts the invariant using parity information.

The box numbered m with ${{l}\mkern6mu{{{\prec}}}\mkern6mu{m}\mkern6mu{{{\prec}}}\mkern6mu{r}}$ is inspected. If its contents is odd, the search continues on the left; if it is even, the search continues on the right.

• The invariant entails the desired result (fulfilment): again, this is the task of the callee. In our example, there is little to do as the invariant is the result.

The art of programming in Agda is to arrange things in such a way that each of these three tasks is as direct as possible.

Ken: In particular, the proof shows that the correctness of the search does not depend on the specific strategy we use. The strategy “only” affects the running time.

Lisa (who has been unusually quiet): I am even more concerned now. It seems to me that m, the argument of , can be an arbitrary natural number. In particular, it may lie outside the given interval. For example, if and then

Ken: Well, no. The expression is certainly a legal type. It is, however, uninhabited: there is no element of this type. We can show that the existence of an interval tree implies that the left endpoint is below the right endpoint.

Lisa: I see. Putting the order-theoretic spectacles on, is indeed just , evidence that the size of the interval is one. And the constructor, which joins two intervals, amounts to transitivity. [She pauses briefly.] Since Ken’s type generalises the order types, we can also show the converse of ${{domain}}$ . [Starts typing.] Agda’s code inference comes in handy.

The endpoints l and r are not in scope. However, as the code is dictated by the type, I can simply use underscores for the arguments of the tree constructors. Agda will infer the correct arguments automatically. So, overall, we have demonstrated that the propositions ${{l}\mkern6mu{{{\prec}}}\mkern6mu{r}}$ and are equivalent. Consequently, the corresponding implementations of ${{even-odd-pair}}$ are equivalent, as well! Thanks, this puts my mind to rest.

Ken: You are welcome. I like the name ${{sequential}}$ as it indicates that we are encoding the left-to-right sequential search as an interval tree. By the way, it is not more difficult to convert Harry’s “midpoint trees” [Page 5] to interval trees.

We basically rename the constructors.

Harry: It is intriguing that an interval tree can be viewed in two different ways: as evidence for a relation, the strict order of the naturals, or as a data structure, fixing a search strategy.

Tutor: A nice closing, Harry. That will do for today. There is one missing puzzle piece though. We have not yet discussed how to construct balanced interval trees, capturing binary search—a challenging task for tomorrow!

4 Wednesday

Synopsis: The discussion gets sidetracked by a technical issue: proofs of termination in Agda.

Harry ( with a perfidious smile): Problem solved! Instead of creating balanced interval trees, I have shown that the propositions ${{l}\mkern6mu{{{\prec}}}\mkern6mu{r}}$ and ${{l}\mkern6mu\mathord{{{\prec}}{^{\prime}}}\mkern6mu{r}}$ are equivalent. One direction is straightforward—left as an exercise to you. The proof of the other direction constructs the desired balanced tree.

For one-point intervals there is nothing to do. If the size of the interval is greater than one, I need to show that the midpoint lies between the endpoints.

The proofs are pretty straightforward but not very instructive. As one would hope, ${{binary-subdivision}\mkern6mu({balanced}\mkern6mu{0\mathord{{{\prec}}}17})}$ gives the tree that is still sitting on the whiteboard. [See Figure 1.]

Fig. 1. The whiteboard: Harry’s sketch of Ken’s interval tree.

Lisa: Good job Harry! So this is where we finally use properties of the midpoint. The propositions are somewhat asymmetric though. I guess this is due to the fact that we are rounding downwards?

Lambert: Yes, indeed. The floor midpoint is only strictly greater than the left endpoint if the difference of the endpoints is at least two: ${1\mkern6mu\mathord{+}\mkern6mu{a}\mkern6mu{{{\prec}}}\mkern6mu{b}}$ .

Lisa (peeking over Harry’s shoulder): May I? [She takes Harry’s laptop to scrutinise the Agda code.] Harry, you have been cheating: balanced has a termination pragma attached to it!

Harry (sighs): Guilty as charged. Agda’s termination checker was recalcitrant. I am pretty sure, however, that the program terminates—I ported it to Haskell and tested it extensively. The Haskell compiler never complains about non-termination!

Ken: You have excessive expectations, Harry. Agda can only prove termination if the function is structurally recursive, which is not the case with your function. You may pass ${{p}}$ , a sub-structure of the argument , to a recursive invocation of ${{balanced}}$ but not ${{a{{\prec}}a-mid-b}\mkern6mu{p}}$ or . Anyway, I would argue that a termination pragma is a cultural faux-pas in dependent type theory. It mars the entire development. Fortunately, a cure is readily at hand: we add a “recursion permit” to your function.

Tutor: Just to double-check: earlier this term, we discussed general recursion. In particular, we looked at a modular approach to course-of-values recursion using accessibility predicates. [Looks around at blank faces.] It seems some of you need a refresher. Ken, would you be willing to summarise the idea?

Ken: Sure. Say, we are programming a list consumer:

The function is, however, not structurally recursive; rather, it recurses over the length of the list argument ${{xs}}$ . To establish termination, we add an argument of type ${\textit{Accessible}\mkern6mu({length}\mkern6mu{xs})}$ , where ${\textit{Accessible}}$ is defined:

You may want to think of the additional argument as a “recursion permit”: it allows us to pass any list to a recursive call as long as it is shorter than ${{xs}}$ .

We only need to provide a proof, ${{p}\mkern6mu\mathbin{:}\mkern6mu{length}\mkern6mu{ys}\mkern6mu{{{\prec}}}\mkern6mu{length}\mkern6mu{xs}}$ , that certifies that the length is actually decreasing. Agda happily accepts the definition as it is structurally recursive on the recursion permit—note that ${\textit{Accessible}}$ is an inductively defined predicate on the naturals.

Lisa: So to fix Harry’s function, we add an argument of type ${\textit{Accessible}\mkern6mu({r}\mkern6mu{{\mathop - \limits^\cdot}}\mkern6mu{l})}$ , as we need to recurse over the size of the interval , right? Then we have to show that the size of the interval is decreasing for both recursive calls: ${{m}\mkern6mu{{\mathop - \limits^\cdot}}\mkern6mu{l}\mkern6mu{{{\prec}}}\mkern6mu{r}\mkern6mu{{\mathop - \limits^\cdot}}\mkern6mu{l}}$ and ${{r}\mkern6mu{{\mathop - \limits^\cdot}}\mkern6mu{m}\mkern6mu{{{\prec}}}\mkern6mu{r}\mkern6mu{{\mathop - \limits^\cdot}}\mkern6mu{l}}$ . [Ponders.]

Lambert: May I lend you a helping hand? These inequalities follow from order-theoretic properties of monus, which is monotone in its first argument and antitone in its second.

The first proposition is a consequence of ${\mathord{{{\lfloor}}}\mkern6mu{a}\mkern6mu\boldsymbol{{mid}}\mkern6mu{b}\mkern6mu{{{\rfloor}}}\mkern6mu{{{\prec}}}\mkern6mu{b}}$ and monotonicity; the second follows from ${{a}\mkern6mu{{{\prec}}}\mkern6mu\mathord{{{\lfloor}}}\mkern6mu{a}\mkern6mu\boldsymbol{{mid}}\mkern6mu{b}\mkern6mu{{{\rfloor}}}}$ and antitonicity. Well, at least in principle, the proofs are slightly more intricate as we require strict inequalities.

Harry: Nicely done Lambert. Surely, the standard library provides the necessary results. [He grabs his laptop.] Let me fix the definition of balanced. Ken’s setup strikes me as an instance of the worker/wrapper scheme. Thanks to Lisa and Lambert, the definition of the worker function is pretty straightforward.

[Pauses.] But I am unsure how to define the wrapper, the function ${{balanced}}$ itself. It needs to supply an argument of type ${\textit{Accessible}\mkern6mu({r}\mkern6mu{{\mathop - \limits^\cdot}}\mkern6mu{l})}$ $\dots$

Ken: I do like the worker/wrapper presentation. Yes, the worker uses the recursion permit, which the wrapper provides. Fortunately, permits can be produced in a completely generic way, independent of the application at hand.

The “ticket machine” is defined by structural induction on the naturals. The natural number is accessible as there is no number below zero.

Using the proof of ${{m}\mkern6mu{{{\prec}}}\mkern6mu0}$ given to us, we construct a contradiction.

Lambert: Ex falso sequitur quodlibet—from contradiction, anything follows.

Ken: Your Latin is pretty good, Lambert! For the successor of a natural number,

we distinguish two cases. Either m equals n, in which case, we simply return the recursion permit for n provided as an argument. Otherwise, when m is strictly smaller than n, we use the recursion permit for n to show that m is accessible. As an aside, the first case demonstrates that structural recursion is a special case of course-of-values recursion—recall that evidences .

Harry: Great! Then we can drive the story home.

Phew, this was rather hard work. [He pauses to reflect on the development.] But, do we really need the intermediate structure, my midpoint trees? Using a recursion permit, I could rewrite our very first definition of ${{even-odd-pair}}$ , to directly implement a binary sub-division scheme.

Tutor: Well, you can certainly deforest midpoint trees, fusing producer and consumer—a rather mechanical optimisation step. I would argue, however, that the present design is preferable as it nicely separates concerns. The proof of total correctness is divided into two parts:

• • A proof of partial correctness: ${{even-odd-pair}}$ establishes the existence of an even-odd pair. The proof relies, however, on an assumption: the existence of a midpoint tree. A priori, we have no reason to believe that your type ${{l}\mkern6mu\mathord{{{\prec}}{^{\prime}}}\mkern6mu{r}}$ is inhabited.

• • A termination argument: balanced shows that suitable midpoint trees exist. The proof involves properties of the midpoint.

Different proof techniques are used in each part: functional invariants for partial correctness and accessibility predicates for termination. Midpoint trees serve as a connecting element.

Unfortunately, time is already up. Tomorrow, we look at further applications of binary search.

5 Thursday

Synopsis: The discussion returns to the original topic: the beauty and power of binary search.

Tutor: Good morning class. I must say I am very pleased that you have come up with a solution to the even-odd puzzle that abstracts away from the search strategy. Are there further opportunities for abstraction? For example, is there anything special about evenness and oddness? Or, could we replace the parity properties by arbitrary predicates, say, P like petty and Q like quirky?

Lisa: Well, inspecting the definition of ${{even-odd-pair}}$ , it seems that we make only a single assumption: the predicates are exhaustive, each natural number is either even or odd. In order to generalise the proof, we could assume the existence of an oracle that classifies a given natural as petty or quirky.

Harry: Shouldn’t we also require that the predicates P and Q are exclusive? In other words, Q should be the complement of P.

Lisa: Hmm, I don’t see why. A number may be both petty and quirky—we leave it to the wisdom of the oracle to judge which property prevails.

Ken (busily typing): The amendment goes through smoothly. To reduce clutter, I have passed the predicates ${P\mkern6muQ\mkern6mu\mathbin{:}\mkern6mu{\mathbb{N}}\mkern6mu\mathord{{\rightarrow}}\mkern6mu\textit{Set}}$ as implicit arguments.

Thankfully, the even-odd puzzle is an instance of the general scheme.

And now the grand finale: if we instantiate the search strategy to Harry’s midpoint trees, we obtain a generic implementation of binary search!

Tutor: Excellent! Let us now discuss further applications of binary search. Do you know the game “Guess My Number”?

Someone thinks of a, say, three-digit number and the others try to guess it. After each guess, they are told whether the number is greater or less than their guess.

Lisa: Ha ha, that’s a good one! [Starts typing.] I am not that familiar with the Agda library—how can I decide the ordering on the naturals?

Ken: The library offers several functions that you could use, for example, the two-way comparison ${{\_\mathord{{{\preceq}}}?\mathord{{{\succ}}}\_}\mkern6mu\mathbin{:}\mkern6mu{{{\forall}}}\mkern6mu{m}\mkern6mu{n}\mkern6mu\mathord{{\rightarrow}}\mkern6mu({m}\mkern6mu{{{\preceq}}}\mkern6mu{n})\mkern6mu{{{\uplus}}}\mkern6mu({m}\mkern6mu{{{\succ}}}\mkern6mu{n})}$ . The operator looks perhaps a bit weird. A question mark typically indicates a decision procedure: ${{\_\mathord{{{\preceq}}}?\mathord{{{\succ}}}\_}}$ decides whether the arguments are related by or by .

Lisa: Thanks. Here we are.

Tutor: Very good. Do you remember the life-cycle of a functional invariant? The ${{guess-my-number}}$ application establishes the invariant of ${{binary-search}}$ , providing evidence that ${0\mkern6mu{{{\preceq}}}\mkern6mu{n}\mkern6mu{{{\prec}}}\mkern6mu1000}$ as ${P\mkern6mu{i}\mkern6mu\mathrel{=}\mkern6mu({i}\mkern6mu{{{\preceq}}}\mkern6mu{n})}$ and ${Q\mkern6mu{i}\mkern6mu\mathrel{=}\mkern6mu({n}\mkern6mu{{{\prec}}}\mkern6mu{i})}$ .

Harry: Now I see why Lisa is laughing: the postcondition tells us that i is actually equal to ${{n}}$ . Not a very useful function, but a reassuring result.

Tutor: The game was intended as a preparatory step. Let me tweak the oracle, applying a function, say, squaring to the index: ${\lambda\mkern6mu{i}\mkern6mu\mathord{{\rightarrow}}\mkern6mu{i}\mkern6mu\mbox{}\!^2\mkern6mu{\mathord{{{\preceq}}}?\mathord{{{\succ}}}}\mkern6mu{n}}$ .

Harry: We obtain the inverse of the function, the square root in your example?

Lambert: Not quite, squaring has no inverse in the naturals. The oracle implicitly defines the predicates: ${P\mkern6mu{i}\mkern6mu\mathrel{=}\mkern6mu({i}\mkern6mu\mbox{}\!^2\mkern6mu{{{\preceq}}}\mkern6mu{n})}$ and ${Q\mkern6mu{i}\mkern6mu\mathrel{=}\mkern6mu({n}\mkern6mu{{{\prec}}}\mkern6mu{i}\mkern6mu\mbox{}\!^2)}$ . The postcondition of binary search, ${{i}\mkern6mu\mbox{}\!^2\mkern6mu{{{\preceq}}}\mkern6mu{n}\mkern6mu{{{\prec}}}\mkern6mu(1\mkern6mu\mathord{+}\mkern6mu{i})\mkern6mu\mbox{}\!^2}$ , then tells us that we obtain the square root rounded downwards.

Lisa: So we can basically copy the code for “Guess My Number”.

All that remains to be done is to update the code for installing the functional invariant. Since the search interval is , we need to show ${{square-lemma}\mkern6mu\mathbin{:}\mkern6mu{{{\forall}}}\mkern6mu{n}\mkern6mu\mathord{{\rightarrow}}\mkern6mu{n}\mkern6mu{{{\prec}}}\mkern6mu(1\mkern6mu\mathord{+}\mkern6mu{n})\mkern6mu\mbox{}\!^2}$ .

Harry: This is certainly a valid proposition. [Pauses.] It seems to me that “searching an ordered table” is very similar to computing the square root. If we model the lookup table by a function ${{table}\mkern6mu\mathbin{:}\mkern6mu{\mathbb{N}}\mkern6mu\mathord{{\rightarrow}}\mkern6mu{\mathbb{N}}}$ that maps positions to keys, then the oracle reads .

The difference to Knuth’s setup is striking: his search returns an index i such that ${K_i\mkern6mu{{{\equiv}}}\mkern6muK}$ , but the search may fail; our search always succeeds, returning an index i such that ${K_i\mkern6mu{{{\preceq}}}\mkern6muK\mkern6mu{{{\prec}}}\mkern6muK_{1+i}}$ .

Lisa: There is one further difference: Knuth assumes that the table is ordered, that the function table is monotone; we don’t make this assumption.

Harry: Yes, you are right. “Searching an unordered table”? Weird!

Tutor: I see, you are getting into the mood. Ready for one of my favourite puzzles, taken from Jeff Erickson’s excellent lecture notes on algorithms (2011)?

You are a contestant on the game show “Beat Your Neighbours!”. You are presented with a sequence of n boxes, each containing a natural number. It costs 100€ to open a box. Your goal is to find a box whose number is larger than its left and right neighbours. If you spend less money than any of your opponents, you win a week-long trip to Berlin.

Harry: Does such a box always exist? In your example, the boxes numbered 2, 4, and 8 are winning boxes. But, what if all boxes contain the same number, or the numbers are strictly increasing from left to right?

Lisa: Perhaps we should first clarify what “larger” means: “strictly larger” or “no smaller”? Furthermore, the description is incomplete: the leftmost box has no left neighbour, and the rightmost box has no right neighbour.

Tutor: Well, the boxes at the ends need to beat only one neighbour. Regarding the reading of “larger”: to avoid upsetting the candidates, we should guarantee the existence of a winning box, so “larger” means “no smaller”.

Lambert: Treating the outermost boxes separately, strikes me as inelegant. To avoid three different winning criteria, I suggest to add “virtual” boxes to the ends. [He adds “sentinels” to the example.]

They are similar to “sentinel nodes”, which serve as traversal terminators in imperative programming. The virtual boxes contain the smallest natural number, so that the “beats” condition is trivially satisfied.

Harry: I don’t think that this puzzle is an instance of binary search. Say, you open the middle box and 6 is revealed to you. What conclusions can you draw? None! Perhaps a picture is helpful. [He plots the graph of the function.]

[Mumbles.] Looks like a mountain range to me.

Lisa: Harry Hacker, you are a genius. Imagine you are hiking in the mountains, aiming to climb some mountain peak. Which strategy do you follow? You consider the slope, not the height above sea level. [Adds a line of numbers.]

If we replace height by slope, ${{slope}\mkern6mu := \mkern6mu({box}\mkern6mu(1\mkern6mu\mathord{+}\mkern6mu{i})\mkern6mu\mathord{-}\mkern6mu{box}\mkern6mu{i})\mkern6mu\mathord{/}\mkern6mu((1\mkern6mu\mathord{+}\mkern6mu{i})\mkern6mu\mathord{-}\mkern6mu{i})}$ , then we have a straightforward application of binary search: ${P\mkern6mu{i}}$ holds if ${{slope}\mkern6mu{i}}$ is non-negative, ${Q\mkern6mu{i}}$ holds if ${{slope}\mkern6mu{i}}$ is non-positive.

Lambert: So in abstract clothing, we are looking for a local maximum.

Ken (again eagerly typing): The code is straightforward, indeed. I don’t use ${{slope}}$ though. Instead, I simply compare the contents of two adjacent boxes.

The code assumes Lambert’s sentinel trick as the winning criterion does not treat the boxes at the ends differently. Just in case you wonder, ${{\_\mathord{{{\preceq}}}?\mathord{{{\succeq}}}\_}\mkern6mu\mathbin{:}\mkern6mu{{{\forall}}}\mkern6mu{m}\mkern6mu{n}\mkern6mu\mathord{{\rightarrow}}\mkern6mu{m}\mkern6mu{{{\preceq}}}\mkern6mu{n}\mkern6mu{{{\uplus}}}\mkern6mu{m}\mkern6mu{{{\succeq}}}\mkern6mu{n}}$ is a “non-deterministic” variant of ${{\_\mathord{{{\preceq}}}?\mathord{{{\succ}}}\_}}$ . If the arguments are equal, the operator either returns a proof of ${{m}\mkern6mu{{{\preceq}}}\mkern6mu{n}}$ or a proof of ${{m}\mkern6mu{{{\succeq}}}\mkern6mu{n}}$ . We don’t know which, but also we don’t care.

Harry: So this is an example where P and Q are not exclusive. [Pauses.] On a more general note, I have to admit that I wasn’t very thrilled by this week’s topic, but binary search is much more general than I thought initially. In particular, I am intrigued that we do not need to assume that the data is ordered.

Ken: I like to think that we experience the effect of constructive logic. Both Knuth and Bird&Wadler are somewhat negative: in the recursive step, they eliminate data from consideration. In the end, their search may fail. We are much more positive: in the recursive step, we continue with the half that guarantees the existence of a petty-quirky pair—the other half possibly contains further pairs. Our search is always successful. Constructive logic favours a positive mindset.

Tutor: Sorry, we are already running overtime. Let’s continue the discussion tomorrow. If you feel energetic, try to re-implement Bird&Wadler in Agda.

6 Friday

Synopsis: The rôle of monotonicity is discussed.

Tutor: Good morning class. Lisa, do you want to take the lead?

Lisa: Sure. A quick refresher is probably not amiss. Given a monotone predicate ${P\mkern6mu\mathbin{:}\mkern6mu{\mathbb{N}}\mkern6mu\mathord{{\rightarrow}}\mkern6mu\textit{Set}}$ and an interval ${[\mskip1.5mu \mkern6mu{l}\mkern6mu{,}\mkern6mu{r}\mkern6mu\mskip1.5mu]}$ , Bird&Wadler seek to determine the smallest index ${{j}\mkern6mu{{{\in}}}\mkern6mu[\mskip1.5mu \mkern6mu{l}\mkern6mu{,}\mkern6mu{r}\mkern6mu\mskip1.5mu]}$ such that ${P\mkern6mu{j}}$ holds. In other words, they are looking for a position where the predicate P flips. This is no different than a petty-quirky pair, where ${{i}}$ is petty if ${{{\neg}}\mkern6muP\mkern6mu{i}}$ and ${{i}}$ is quirky if ${P\mkern6mu{i}}$ . Now, approaching the task with a positive mindset, we would, of course, like to guarantee the existence of such a pair. These considerations motivate the following interface.

The preconditions ${{l}\mkern6mu{{{\prec}}}\mkern6mu{r}}$ and ${{{\neg}}\mkern6muP\mkern6mu{l}\mkern6mu\mathord{{\times}}\mkern6muP\mkern6mu{r}}$ make sure that a petty-quirky pair exists. Since P is monotone the pair is also unique. The postcondition rewords this observation to say that we have found the smallest index j such that ${P\mkern6mu{j}}$ holds.

Harry: Are you suggesting that monotonicity plays no rôle for the actual search?

Lisa: Exactly! In particular, we can implement Bird&Wadler’s search function find in terms of our binary-search.

We obtain a petty-quirky pair, so ${1\mkern6mu\mathord{+}\mkern6mu{j}}$ is the desired smallest quirky index. For the proof of minimality, we basically apply the contrapositive of monotonicity: ${{a}\mkern6mu{{{\preceq}}}\mkern6mu{b}\mkern6mu\mathord{{\rightarrow}}\mkern6mu({{\neg}}\mkern6muP\mkern6mu{b}\mkern6mu\mathord{{\rightarrow}}\mkern6mu{{\neg}}\mkern6muP\mkern6mu{a})}$ . Concretely, from ${{i}\mkern6mu{{{\prec}}}\mkern6mu1\mkern6mu\mathord{+}\mkern6mu{j}}$ , which is equivalent to ${{i}\mkern6mu{{{\preceq}}}\mkern6mu{j}}$ and ${{{\neg}}\mkern6muP\mkern6mu{j}}$ we conclude ${{{\neg}}\mkern6muP\mkern6mu{i}}$ .

Lambert: It is interesting to see how things intertwine: the invariant guarantees the existence of a “quirky” index; monotonicity ensures that it is unique. I am really pleased to see that Lisa’s program is total in contrast to Bird&Wadler’s code. Their “Introduction to Functional Programming” is an excellent textbook, but the presentation of binary search is, well, slightly below standard.

Harry: In their defence, we place an additional burden on the caller of ${{find}}$ who needs to install the functional invariant ${{{\neg}}\mkern6muP\mkern6mu{l}\mkern6mu\mathord{{\times}}\mkern6muP\mkern6mu{r}}$ .

Lisa: Well, yes and no. Yes, they have to provide evidence that the search is in some sense “promising”. One option is to apply Lambert’s cute sentinel trick: assuming l is non-zero, the original search interval ${[\mskip1.5mu \mkern6mu{l}\mkern6mu{,}\mkern6mu{r}\mkern6mu\mskip1.5mu]}$ is widened to ${{l}\mkern6mu\mathord{-}\mkern6mu1\mkern6mu{{{\prec}}}\mkern6mu1\mkern6mu\mathord{+}\mkern6mu{r}}$ , setting ${P\mkern6mu{i}\mkern6mu:=\mkern6mu{{{\bot}}}}$ for ${{i}\mkern6mu{{{\prec}}}\mkern6mu{l}}$ and ${P\mkern6mu{i}\mkern6mu:=\mkern6mu{{\top}}}$ for ${{r}\mkern6mu{{{\prec}}}\mkern6mu{i}}$ . The conditions now hold by definition, so no, I don’t consider this a burden.

Harry: Hmm, okay. [Pauses.] So monotonicity is only used in an afterthought. [Pauses again.] Can we please revisit the problem of “searching an ordered table”? I really don’t see how to define this as an instance of our binary search. Approaching problems with a positive mindset is all good and well, but we simply cannot guarantee that a given table contains a given key.

Ken: True. But you can use monotonicity to decide containment. You may want to implement the following interface:

A property is decidable if you either have concrete evidence that it holds or evidence that it does not hold.

Harry: I guess you are suggesting to use yesterday’s ${{table-lookup}}$ , post-processing its results? [Starts typing.]

The function ${{table-lookup}}$ returns proofs that ${K_i\mkern6mu{{{\preceq}}}\mkern6muK\mkern6mu{{{\prec}}}\mkern6muK_{1+i}}$ . I pattern match on the first proof to check whether ${K_i\mkern6mu{{{\equiv}}}\mkern6muK}$ or ${K_i\mkern6mu{{{\prec}}}\mkern6muK}$ — recall that we defined ${{m}\mkern6mu{{{\preceq}}}\mkern6mu{n}\mkern6mu\mathrel{=}\mkern6mu({m}\mkern6mu{{{\equiv}}}\mkern6mu{n})\mkern6mu{{{\uplus}}}\mkern6mu({m}\mkern6mu{{{\prec}}}\mkern6mu{n})}$ . If the former, then I signal success; if the latter, I need to report that the key has not been found. [Stops typing.]

Ken: May I offer a helping hand? In the negative case, you can derive a contradiction using irreflexivity. Say, the adversary claims the existence of an index j with ${K_j\mkern6mu{{{\equiv}}}\mkern6muK}$ . Assuming ${{j}\mkern6mu{{{\preceq}}}\mkern6mu{i}}$ , monotonicity implies ${K_j\mkern6mu{{{\preceq}}}\mkern6muK_i}$ . Since we already know that ${K_i\mkern6mu{{{\prec}}}\mkern6muK\mkern6mu{{{\equiv}}}\mkern6muK_j}$ , witnessed by ${p_i}$ , we have ${K_i\mkern6mu{{{\prec}}}\mkern6muK_i}$ , which is impossible.

The other case enjoys a similar proof.

Harry: Cool. [Smiles mischievously.] I never thought that monotonicity would help with negative feelings.

Fig. 2. Exercise sheet: binary search and its applications.

Lisa: In the success case, monotonicity is also helpful: it implies that the index i lies in the specified interval: ${{l}\mkern6mu{{{\preceq}}}\mkern6mu{i}\mkern6mu{{{\prec}}}\mkern6mu{r}}$ .

Tutor: Well done everybody. We certainly have earned an early weekend. I hope you enjoyed these tutorials as much as I did. As usual, the exercise sheet contains some ideas for further exploration, revisiting design decisions and generalising the setup. [See Figure 2.] Enjoy! Oh, and I recommend reading Joshua Bloch’s blog post (2006) “Extra, Extra—Read All About It: Nearly All Binary Searches and Mergesorts Are Broken”, which shows that formal proofs do not eliminate the need for systematic testing—typical programming languages use fixed-precision arithmetic, which can lead to overflow errors when computing the midpoint. Our Peano naturals support arbitrary-precision arithmetic, so we avoid this problem.

7 Afterword

This pearl grew out of the authors’ frustration with textbook presentations of binary search. Given that binary search is one of the standard algorithms every programmer and computer science student should know, the subject is inadequately covered at best. Many textbooks mention binary search only in passing or they treat only special cases, such as computing the square root or searching an ordered table. A negative mindset prevails: the search possibly fails; in the divide&conquer step one half of the search space is excluded from consideration because searching this half will definitely fail. The correctness argument requires that the data is ordered, suggesting that monotonicity in some sense drives the search. One notable exception is Anne Kaldewaij’s textbook (1990): when discussing “function inversion” (given ${{n}}$ , find an argument ${{i}}$ such that ${{f}\mkern6mu{i}\mkern6mu{{{\preceq}}}\mkern6mu{n}\mkern6mu{{{\prec}}}\mkern6mu{f}\mkern6mu(1\mkern6mu\mathord{+}\mkern6mu{i})}$ ) he emphasises repeatedly that the correctness of the search does not require that ${{f}}$ is an ascending function.

The gist of this pearl is to approach search problems with a positive mind-set: the search always succeeds; in the divide&conquer step the search continues with the half that guarantees success. The correctness argument relies on a suitable functional invariant, not on monotonicity. The “Beat Your Neighbours!” problem, a concrete make-up for local maximum search, shows that the extra generality is actually needed.