| More on Merging and Selection (2007) | |||||||||||||||
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. 1 Introduction Richard Bird [2] considers the problem of computing merge (x; y) !! n ---that is, of computing the nth element of the list resulting from merging the two sorted lists x and y---and the related problem when x and y are represented by trees. For the former problem, \Theta(n) steps are required, even in a lazy functional language; for the latter problem Bird derives a solution taking time proportional to the sum of the dept... | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||