Pretty printing with lazy dequeues

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Pretty printing with lazy dequeues

Full text

Pdf (209 KB)

Source

ACM Transactions on Programming Languages and Systems (TOPLAS) archive
Volume 27 , Issue 1 (January 2005) table of contents

Pages: 163 - 184

Year of Publication: 2005

ISSN:0164-0925

Author

Olaf Chitil

University of Kent, United Kingdom

Publisher

ACM New York, NY, USA

Bibliometrics

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

Additional Information:

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

ABSTRACT

There are several purely functional libraries for converting tree structured data into indented text, but they all make use of some backtracking. Over twenty years ago, Oppen published a more efficient imperative implementation of a pretty printer. This article shows that the same efficiency is also obtainable without destructive updates by developing a similar but purely functional Haskell implementation with the same complexity bounds. At its heart lie two lazy double ended queues.

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	Azero, P. and Swierstra, D. 1998. Optimal pretty-printing combinators. http://www.cs.uu.nl/groups/ST/Center/SoftwareDistributions.
	2	Bird, R. S. 1984. Using circular programs to eliminate multiple traversals of data. Acta Inf. 21, 239--250.
	3	R J M Hughes, A novel representation of lists and its application to the function "reverse", Information Processing Letters, v.22 n.3, p.141-144, March 1986 [doi>10.1016/0020-0190(86)90059-1]
	4	John Hughes, The Design of a Pretty-printing Library, Advanced Functional Programming, First International Spring School on Advanced Functional Programming Techniques-Tutorial Text, p.53-96, May 24-30, 1995
	5	Chris Okasaki, Purely functional data structures, Cambridge University Press, New York, NY, 1998
	6	Chris Okasaki, Breadth-first numbering: lessons from a small exercise in algorithm design, Proceedings of the fifth ACM SIGPLAN international conference on Functional programming, p.131-136, September 2000
	7	Dereck C. Oppen, Prettyprinting, ACM Transactions on Programming Languages and Systems (TOPLAS), v.2 n.4, p.465-483, Oct. 1980 [doi>10.1145/357114.357115]
	8	Peyton Jones, S. L. 1997. A pretty printer library in Haskell. Part of the GHC distribution at http://www.haskell.org/ghc.
	9	Peyton Jones, S. L., Ed. 2003. Haskell 98 Language and Libraries, The Revised Report. Cambridge University Press.
	10	Wadler, P. 2003. A prettier printer. In The Fun of Programming. Palgrave Macmillan, Chapter 11, 223--244.

CITED BY 3

	Arthur I. Baars , S. Doaitse Swierstra, Type-safe, self inspecting code, Proceedings of the 2004 ACM SIGPLAN workshop on Haskell, September 22-22, 2004, Snowbird, Utah, USA
	Martijn M. Schrage , Arjan van IJzendoorn , Linda C. van der Gaag, Haskell ready to dazzle the real world, Proceedings of the 2005 ACM SIGPLAN workshop on Haskell, p.17-26, September 30-30, 2005, Tallinn, Estonia
	S. doaitse Swierstra , Olaf Chitil, Linear, bounded, functional pretty-printing, Journal of Functional Programming, v.19 n.1, p.1-16, January 2009