Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Efficient Applicative Operations on Recursive Data Structures

IP.com Disclosure Number: IPCOM000128282D
Original Publication Date: 1985-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 6 page(s) / 22K

Publishing Venue

Software Patent Institute

Related People

RobertHood: AUTHOR [+3]

Abstract

This paper outlines O(l) time and space algorithms (in Pure LISP) for a given set of operations to manipulate recursive data structures, such as LISP's S-expressions. The operations include array-like selection and updating at an abstract position within a recursive data structure. One implication of this result is that the "efficiency" of Pure LISP is not enhanced by the addition of the given operations.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 24% of the total text.

Page 1 of 6

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Efficient Applicative Operations on Recursive Data Structures*

(summary)

RobertHood.

Rice COW. TR85-15 February 1985

Department of Computer Science Rice University P.O. Box 1892 Houston, TX 77251-1892

(713) 527-8101

*This research has been supported in part by National Science Foundation grants MCS 78-05- S-50, MCS-8104006, and MCS-8121884 and by International Business Machines Corporation under'a Faculty Development Award.

Abstract

This paper outlines O(l) time and space algorithms (in Pure LISP) for a given set of operations to manipulate recursive data structures, such as LISP's S-expressions. The operations include array-like selection and updating at an abstract position within a recursive data structure. One implication of this result is that the "efficiency" of Pure LISP is not enhanced by the addition of the given operations.

1. Introduction

As part of our practical work on the efficient implementation of very-high-level programming language constructs we have sought abstract, yet computationally efficient ways to manipulate recursive data structures [l.-2]. Because of the logical simplicity of proofs of correctness of appli- cative programs, that research led to the investigation of the applicative treatment of recursive data structures. In an attempt to justify a practical set of applicative operations on recursive data structures, we were looking for an example of a program that could be speeded up by,their use. In fact, what we found was a proof that the operations could be simulated in real-time, and thus that the addition of the operations as constant-time primitives produced no asymptotic gain in the efficiency of programs using them.

Although applicative programming is gaining in popularity, there are not very many published algorithms that implement applicative data structures. In a previous paper [3) we give an O(l) algorithm for the implementation of a queue in Pure LISP. The work presented here is a generali-zation of that work-it is a straightforward exercise to implement a queue using the operations given here.

By employing'a height- balancing scheme called AVL dags, Myers is able to implement a collec- tion of applicative operations on linear lists that require only O(log N) time and space [o]. His col-lection is, on the one hand, more general than the one presented here because, among

Rice University Page 1 Dec 31, 1985

Page 2 of 6

Efficient Applicative Operations on Recursive Data Structures

other things, he allows selection of the k 1h element of a list. On the other hand, because they deal only with linear lists, his collection is more restrictive.

'This research has been supported in Dart by National Science Foundation grants MCS 78- 05850, MCS-8104006. and MCS-8121884 and by International Business ~achines Corporation under a Faculty Development Award. The collection of operations implemented here seek to provide the concept of generalized...