Skip to main content

More on Merging and Selection

Jeremy Gibbons

Abstract

In his paper On Merging and Selection (Journal of Functional Programming 7(3), 1997), Bird considers the problem of computing the nth element of the list resulting from merging the two sorted lists x and y. Representing x and y by trees, Bird derives an algorithm for the problem taking time proportional to the sum of their depths. Bird's derivation is more complicated than necessary. By the simple tactic of delaying a design decision (in this case, the decision to represent the lists as trees) as long as possible, we obtain a much simpler solution.

Institution
School of Computing and Mathematical Sciences‚ Oxford Brookes University
Month
oct
Number
CMS−TR−97−08
Year
1997