Functional Pearl trouble shared is trouble halved

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Functional Pearl trouble shared is trouble halved

Full text

Pdf (102 KB)

Source

Haskell Workshop archive
Proceedings of the 2003 ACM SIGPLAN workshop on Haskell table of contents

Uppsala, Sweden

Pages: 1 - 6

Year of Publication: 2003

ISBN:1-58113-758-3

Authors

Richard Bird	Oxford University Computing Laboratory, Oxford, England
Ralf Hinze	Universität Bonn, Römerstraβe, Bonn, Germany

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages
ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 0, Downloads (12 Months): 22, Citation Count: 1

Additional Information:

abstract references cited by index terms collaborative colleagues peer to peer

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/871895.871896 What is a DOI?

ABSTRACT

A nexus is a tree that contains shared nodes, nodes that have more than one incoming arc. Shared nodes are created in almost every functional program---for instance, when updating a purely functional data structure---though programmers are seldom aware of this. In fact, there are only a few algorithms that exploit sharing of nodes consciously. One example is constructing a tree in sublinear time. In this pearl we discuss an intriguing application of nexuses; we show that they serve admirably as memo structures featuring constant time access to memoized function calls. Along the way we encounter Boolean lattices and binomial trees.

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	Richard Bird , Oege de Moor, Algebra of programming, Prentice-Hall, Inc., Upper Saddle River, NJ, 1997
	2	Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
	3	Ralf Hinze. Memo functions, polytypically! In Johan Jeuring, editor, Proceedings of the 2nd Workshop on Generic Programming, Ponte de Lima, Portugal, pages 17--32, July 2000. The proceedings appeared as a technical report of Universiteit Utrecht, UU-CS-2000-19.
	4	Graham Hutton, The countdown problem, Journal of Functional Programming, v.12 n.6, p.609-616, November 2002 [doi>10.1017/S0956796801004300]
	5	Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
	6	Erik Meijer , Maarten Fokkinga , Ross Paterson, Functional programming with bananas, lenses, envelopes and barbed wire, Proceedings of the 5th ACM conference on Functional programming languages and computer architecture, p.124-144, June 1991, Cambridge, Massachusetts, United States
	7	Donald Michie. "Memo" functions and machine learning. Nature, (218):19--22, April 1968.
	8	Shin-Cheng Mu. A calculational approach to program inversion. PhD thesis, Oxford University Computing Laboratory, 2003.
	9	Chris Okasaki, Three algorithms on Braun trees, Journal of Functional Programming, v.7 n.6, p.661-666, November 1997 [doi>10.1017/S0956796897002876]
	10	Simon Peyton Jones. Haskell 98 Language and Libraries. Cambridge University Press, 2003.
	11	Neil Sarnak , Robert E. Tarjan, Planar point location using persistent search trees, Communications of the ACM, v.29 n.7, p.669-679, July 1986 [doi>10.1145/6138.6151]