© University of Kent - Contact | Feedback | Legal | FOI | Cookies
Pretty printing with lazy dequeues
Olaf Chitil
In Ralf Hinze, editor, Preliminary Proceedings of the 2001 ACM SIGPLAN Haskell Workshop, pages 182-196, Firenze, Italy, September 2001 Universiteit Utrecht UU-CS-2001-23. Final Proceedings to appear in ENTCS 59(2).Abstract
There are several Haskell 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 without backtracking. We show 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.
Download publication 160 kbytes (PDF)Bibtex Record
@inproceedings{1813, author = {Olaf Chitil}, title = {Pretty Printing with Lazy Dequeues}, month = {September}, year = {2001}, pages = {182-196}, keywords = {determinacy analysis, Craig interpolants}, note = {Universiteit Utrecht UU-CS-2001-23. Final Proceedings to appear in ENTCS 59(2).}, doi = {}, url = {http://www.cs.kent.ac.uk/pubs/2001/1813}, publication_type = {inproceedings}, submission_id = {16101_1077222786}, booktitle = {Preliminary Proceedings of the 2001 ACM SIGPLAN Haskell Workshop}, editor = {Ralf Hinze}, address = {Firenze, Italy}, refereed = {yes}, }