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...
| Main Author: | |
|---|---|
| Format: | Report |
| Published: |
School of Computing and Mathematical Sciences‚ Oxford Brookes University
1997
|
| _version_ | 1826276910833860608 |
|---|---|
| author | Gibbons, J |
| author_facet | Gibbons, J |
| author_sort | Gibbons, J |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-06T23:20:57Z |
| format | Report |
| id | oxford-uuid:68b55cda-6cdc-4d27-a2b5-096532ca2689 |
| institution | University of Oxford |
| last_indexed | 2024-03-06T23:20:57Z |
| publishDate | 1997 |
| publisher | School of Computing and Mathematical Sciences‚ Oxford Brookes University |
| record_format | dspace |
| spelling | oxford-uuid:68b55cda-6cdc-4d27-a2b5-096532ca26892022-03-26T18:46:37ZMore on Merging and SelectionReporthttp://purl.org/coar/resource_type/c_93fcuuid:68b55cda-6cdc-4d27-a2b5-096532ca2689Department of Computer ScienceSchool of Computing and Mathematical Sciences‚ Oxford Brookes University1997Gibbons, JIn 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. |
| spellingShingle | Gibbons, J More on Merging and Selection |
| title | More on Merging and Selection |
| title_full | More on Merging and Selection |
| title_fullStr | More on Merging and Selection |
| title_full_unstemmed | More on Merging and Selection |
| title_short | More on Merging and Selection |
| title_sort | more on merging and selection |
| work_keys_str_mv | AT gibbonsj moreonmergingandselection |