Efficient applicative data types

Published 1 January 1984

Eugene W. Myers

Citations64

TL;DR

This work treats the applicative manipulation of queues and stacks with the requirement that operations be free of side-effects, which makes it difficult to achieve efficient implementations.

Abstract

Article Efficient applicative data types Share on Author: Eugene W. Myers Department of Computer Science, The University of Arizona, Tucson, Arizona Department of Computer Science, The University of Arizona, Tucson, ArizonaView Profile Authors Info & Claims POPL '84: Proceedings of the 11th ACM SIGACT-SIGPLAN symposium on Principles of programming languagesJanuary 1984 Pages 66–75https://doi.org/10.1145/800017.800517Online:15 January 1984Publication History 46citation450DownloadsMetricsTotal Citations46Total Downloads450Last 12 Months18Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Keywords

Computer Science

Communications of the ACMCan programming be liberated from the von Neumann style?

2,582 Citations1978John Backus

A new class of computing systems uses the functional programming style both in its programming language and in its state transition rules; these systems have semantics loosely coupled to states—only one state transition occurs per major computation.

View PDF

Munich Personal RePEc Archive (Ludwig Maximilian University of Munich)AN ALGORITHM FOR THE ORGANIZATION OF INFORMATION

796 Citations1963M. AdelsonVelskii

The organization of information placed in the points of an automatic computer is discussed and the role of memory, storage and retrieval in this regard is discussed.

Communications of the ACMSymmetric list processor

196 Citations1963Joseph Weizenbaum

A list processing system in which each list cell contains both a forward and a backward link as well as a datum is described, intended for imbedding in higher level languages capable of calling functions and subroutines coded in machine language.

View PDF

Information Processing LettersReal-time queue operations in pure LISP

98 Citations1981Robert Hood, Robert Melville

Several methods of implementing a queue in Pure LISP are presented, including a technique to distribute the reversal of a list over a number of operations leads to a real-time queue implementation.

Experience with an applicative string processing language

36 Citations1980James H. Morris, Eric E. Schmidt +1 more

The major conclusions are: Applicative programming can be made more natural through the use of built-in iterative operators and post-fix notation and Clever evaluation strategies can make applicative programming more computationally efficient.

Information Processing LettersAn applicative random-access stack

30 Citations1983Eugene W. Myers

In this article, applicative algorithms for a random-access stuck @A-stack (RA-stack) are presented and a singly-linked list representation which is augmented with auxiliary pointers that permit the access of arbitrary stack elements in O(lg N) time were N is the size of the stack.

Efficient uses of the past

24 Citations1980David Dobkin, J. Ian Munro

ACM Transactions on Programming Languages and SystemsCombining Algebraic and Algorithmic Reasoning: An Approach to the Schorr-Waite Algorithm

23 Citations1982Manfred Broy, Peter Pepper

The basic idea of the Schorr-Waite graph-marking algorithm can be precisely formulated, explained, and verified in a completely applicative (functional) programming style.

View PDF