School of Computing

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},
}

School of Computing, University of Kent, Canterbury, Kent, CT2 7NF

Enquiries: +44 (0)1227 824180 or contact us.

Last Updated: 21/03/2014