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.
Details
| Institution |
School of Computing and Mathematical Sciences‚ Oxford Brookes University |
| Month |
oct |
| Number |
CMS−TR−97−08 |
| Year |
1997 |
Links
Related pages
|
People |
|
|
Activities |