Hostname: page-component-7c8c6479df-8mjnm Total loading time: 0 Render date: 2024-03-18T14:46:15.316Z Has data issue: false hasContentIssue false

FUNCTIONAL PEARL On merging and selection

Published online by Cambridge University Press:  01 May 1997

RICHARD S. BIRD
Affiliation:
Programming Research Group, Oxford University, Wolfson Building, Parks Road, Oxford OX1 3QD, UK
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Given two ascending lists xs and ys of combined length greater than n, consider the computation of

formula here

The standard function merge merges two ascending sequences and (!!) denotes list indexing. With a lazy evaluator the computation takes O(n) steps; with an eager one it takes O(p+q) steps, where p=length xs and q=length ys. Now in functional programming it is more efficient to index a tree than a list, so the question arises: can we find a faster solution if xs and ys are each represented by a tree? Somewhat surprisingly the answer is yes: if xs and ys are each represented by balanced binary search trees, then the computation can be reduced to O(log p+log q) steps. This is despite the fact that there is no known method for merging two binary search trees in better than linear time. The details, presented below, depend on a subtle relationship between merging and indexing.

Type
Research Article
Copyright
© 1997 Cambridge University Press
Submit a response

Discussions

No Discussions have been published for this article.