More on Merging and Selection
In his paper <i>On Merging and Selection</i> (<i>Journal of Functional Programming</i> 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 algorith...
| Glavni avtor: | |
|---|---|
| Format: | Report |
| Izdano: |
School of Computing and Mathematical Sciences‚ Oxford Brookes University
1997
|
| Izvleček: | In his paper <i>On Merging and Selection</i> (<i>Journal of Functional Programming</i> 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. |
|---|