Purely functional random-access lists

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Purely functional random-access lists

Full text

Pdf (840 KB)

Source

Functional Programming Languages and Computer Architecture archive
Proceedings of the seventh international conference on Functional programming languages and computer architecture table of contents

La Jolla, California, United States

Pages: 86 - 95

Year of Publication: 1995

ISBN:0-89791-719-7

Author

Chris Okasaki

School of Computer Science, Carnegie Mellon University, 5000 Forbes Avenue, Pittsburgh, Pennsylvania

Sponsors

IFIP WG 2.8 : IFIP WG 2.8
SIGPLAN: ACM Special Interest Group on Programming Languages
SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 43, Citation Count: 3

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/224164.224187 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	A. Aasa , Sören Holmström , Christina Nilsson, An efficiency comparison of some representations of purely functional arrays, BIT, v.28 n.3, p.490-503, 1988
	2	Pankaj K. Agarwal , Alok Aggarwal , Boris Aronov , S. Rao Kosaraju , Baruch Schieber , Subhash Suri, Computing external farthest neighbors for a simple polygon, Discrete Applied Mathematics, v.31 n.2, p.97-111, 1991 [doi>10.1016/0166-218X(91)90063-3]
	3	William E. Aitken and John H. Reppy. Abstract value constructors. In A CM SIGPLAN Workshop on ML and its Applications, pages 1-11, 1992.
	4	Henry G. Baker, Jr., Shallow binding in Lisp 1.5, Communications of the ACM, v.21 n.7, p.565-569, July 1978 [doi>10.1145/359545.359566]
	5	Henry G. Baker, Shallow binding makes functional arrays fast, ACM SIGPLAN Notices, v.26 n.8, p.145-147, Aug. 1991 [doi>10.1145/122598.122614]
	6	Amir M. Ben-Amram , Zvi Galil, On pointers versus addresses, Journal of the ACM (JACM), v.39 n.3, p.617-648, July 1992 [doi>10.1145/146637.146666]
	7	Adrienne Bloss, Update analysis and the efficient implementation of functional aggregates, Proceedings of the fourth international conference on Functional programming languages and computer architecture, p.26-38, September 11-13, 1989, Imperial College, London, United Kingdom [doi>10.1145/99370.99373]
	8	F. Warren Burton and Robert D. Cameron. Pattern matching with abstract data types. Journal of Functional Programming, 3(2):171-190, April 1993.
	9	Tyng-Ruey Chuang, A randomized implementation of multiple functional arrays, Proceedings of the 1994 ACM conference on LISP and functional programming, p.173-184, June 27-29, 1994, Orlando, Florida, United States
	10	Tyng-Ruey Chuang , Benjamin Goldberg, Real-time deques, multihead Turing machines, and purely functional programming, Proceedings of the conference on Functional programming languages and computer architecture, p.289-298, June 09-11, 1993, Copenhagen, Denmark [doi>10.1145/165180.165225]
	11	Richard Cole and Alan Siegel. River routing every which way, but loose. In Proceedings o/the 25th Annual IEEE Symposium on Foundations of Computer Science, pages 65-73, 1984.
	12	Paul F. Dietz, Fully Persistent Arrays (Extended Array), Proceedings of the Workshop on Algorithms and Data Structures, p.67-74, August 17-19, 1989
	13	Edsger W. Dijksta. A Disciphne o/Programming. Prentice Hall, Englewood Cliffs, New Jersey, 1976.
	14	James R. Driscoll , Neil Sarnak , Daniel D. Sleator , Robert E. Tarjan, Making data structures persistent, Journal of Computer and System Sciences, v.38 n.1, p.86-124, February 1989 [doi>10.1016/0022-0000(89)90034-2]
	15	Greg N. Frederickson, Planar graph decomposition and all pairs shortest paths, Journal of the ACM (JACM), v.38 n.1, p.162-204, Jan. 1991 [doi>10.1145/102782.102788]
	16	H Gajewska , R E Tarjan, Deques with heap order, Information Processing Letters, v.22 n.4, p.197-200, April 1986 [doi>10.1016/0020-0190(86)90028-1]
	17	Robert Todd Hood, The efficient implementation of very-high-level programming language constructs, 1982
	18	Robert Hood and Robert Melville. ReaLtime queue operations in pure Lisp. Information Processing Letters, 13(2):50-53, November 1981.
	19	Rob R. Hoogerwoord, A Logarithmic Implementation of Flexible Arrays, Proceedings of the Second International Conference on Mathematics of Program Construction, p.191-207, June 29-July 03, 1992
	20	Haim Kaplan , Robert E. Tarjan, Persistent lists with catenation via recursive slow-down, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.93-102, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225090]
	21	S. Rao Kosaraju, Localized search in sorted lists, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.62-69, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802458]
	22	Henry Lieberman , Carl Hewitt, A real-time garbage collector based on the lifetimes of objects, Communications of the ACM, v.26 n.6, p.419-429, June 1983 [doi>10.1145/358141.358147]
	23	Robin Milner , Mads Tofte , Robert Harper, The definition of Standard ML, MIT Press, Cambridge, MA, 1990
	24	Eugene W. Myers. An applicative random-access stack. Information Processing Letters, 17(5):241-248, December 1983.
	25	Eugene W. Myers, Efficient applicative data types, Proceedings of the 11th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.66-75, January 15-18, 1984, Salt Lake City, Utah, United States [doi>10.1145/800017.800517]
	26	Martin Odersky, How to make destructive updates less destructive, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.25-36, January 21-23, 1991, Orlando, Florida, United States [doi>10.1145/99583.99590]
	27	Chris Okasaki. Simple and efficient purely functional queues and deques. Journal of Functional Programming, 1994. To appear.
	28	Laurence C. Paulson, ML for the working programmer, Cambridge University Press, New York, NY, 1991
	29	Simon L. Peyton Jones , Philip Wadler, Imperative functional programming, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.71-84, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158524]
	30	A. V. S. Sastry , William Clinger , Zena Ariola, Order-of-evaluation analysis for destructive updates in strict functional languages with flat aggregates, Proceedings of the conference on Functional programming languages and computer architecture, p.266-275, June 09-11, 1993, Copenhagen, Denmark [doi>10.1145/165180.165222]
	31	David A. Schmidt, Detecting global variables in denotational specifications, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.2, p.299-310, April 1985 [doi>10.1145/3318.3323]
	32	Zhong Shao , John H. Reppy , Andrew W. Appel, Unrolling lists, Proceedings of the 1994 ACM conference on LISP and functional programming, p.185-195, June 27-29, 1994, Orlando, Florida, United States
	33	Athanasios K Tsakalidis, AVL-trees for localized search, Information and Control, v.67 n.1-3, p.173-194, Oct./Nov./Dec. 1986 [doi>10.1016/S0019-9958(85)80034-6]
	34	Jean Vuillemin, A data structure for manipulating priority queues, Communications of the ACM, v.21 n.4, p.309-315, April 1978 [doi>10.1145/359460.359478]
	35	P. Wadler, Views: a way for pattern matching to cohabit with data abstraction, Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.307-313, January 21-23, 1987, Munich, West Germany [doi>10.1145/41625.41653]
	36	Philip Wadler. Linear types can change the world! In Proceedings of the IFIP TC 2 Working Conference on Programming Concepts and Methods, pages 561-581, 1990.

CITED BY 3

	Tyng-Ruey Chuang , Wen L. Hwang, A probabilistic approach to the problem of automatic selection of data representations, ACM SIGPLAN Notices, v.31 n.6, p.190-200, June 15, 1996
	Ralf Hinze, Bootstrapping one-sided flexible arrays, ACM SIGPLAN Notices, v.37 n.9, p.2-13, September 2002
	Graeme E. Moss , Colin Runciman, Inductive benchmarking for purely functional data structures, Journal of Functional Programming, v.11 n.5, p.525-556, September 2001