Hostname: page-component-586b7cd67f-vdxz6 Total loading time: 0 Render date: 2024-11-27T16:43:53.585Z Has data issue: false hasContentIssue false
  • English
  • Français

O(1) reversible tree navigation without cycles

Published online by Cambridge University Press:  18 October 2001

RICHARD A. O'KEEFE
RICHARD A. O'KEEFE
Affiliation:
Department of Computer Science, The University of Otago, P.O. Box 56, Dunedin, 9001, New Zealand (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

Imperative programmers often use cyclically linked trees in order to achieve O(1) navigation time to neighbours. Some logic programmers believe that cyclic terms are necessary to achieve the same in logic-based languages. An old but little-known technique provides O(1) time and space navigation without cyclic links, in the form of reversible predicates. A small modification provides O(1) amortised time and space editing.

Keywords

tree navigationediting back-linkZipper
Type
PROGRAMMING PEARL
Information
Theory and Practice of Logic Programming , Volume 1 , Issue 5 , September 2001 , pp. 617 - 630
Copyright
© 2001 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)