A functional implementation of the garsia--wachs algorithm

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A functional implementation of the garsia--wachs algorithm: (functional pearl)

Full text

Pdf (218 KB)

Source

International Conference on Functional Programming archive
Proceedings of the 2008 ACM SIGPLAN workshop on ML table of contents

Victoria, BC, Canada

SESSION: Session 3 table of contents

Pages 91-96

Year of Publication: 2008

ISBN:978-1-60558-062-3

Author

Jean-Christophe Filliatre

Univ Paris Sud and INRIA Saclay - Ile-de-France, Orsay, France

Sponsors

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

Publisher

ACM New York, NY, USA

Bibliometrics

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

Additional Information:

abstract references 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/1411304.1411317 What is a DOI?

ABSTRACT

This functional pearl proposes an ML implementation of the Garsia-Wachs algorithm. This somewhat obscure algorithm builds a binary tree with minimum weighted path length from weighted leaf nodes with given inorder. Our solution exhibits the usual benefits of functional programming (use of immutable data structures, pattern-matching, polymorphism) and nicely compares to the purely imperative implementation from The Art of Computer Programming.

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	Hans-J. Boehm , Russ Atkinson , Michael Plass, Ropes: an alternative to strings, Software—Practice & Experience, v.25 n.12, p.1315-1330, Dec. 1995 [doi>10.1002/spe.4380251203]
	2	Xavier Leroy phet al. The Objective Caml language. http://caml.inria.fr./
	3	Adriano M. Garsia and Michelle L. Wachs. A new algorithm for minimum cost binary trees. SIAM Journal on Computing, 6(4):622--642, December 1977.
	4	Gérard Huet, The Zipper, Journal of Functional Programming, v.7 n.5, p.549-554, September 1997 [doi>10.1017/S0956796897002864]
	5	D. A. Huffman. A method for the construction of minimum-redundancy codes. Proceedings of the IRE, 40(9):1098--1101, 1952.
	6	D. E. Knuth. CWEB implementation of Garsia-Wachs algorithm. http://www-cs-faculty.stanford.edu/~knuth/programs/garsia-wachs.w.
	7	Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
	8	Donald Ervin Knuth , Silvio Levy, The CWEB System of Structured Documentation: Version 3.0, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1994
	9	Philip Wadler. Monads for functional programming. In Marktoberdorf Summer School on Program Design Calculi, August 1992.