School of Computing

Pretty printing with lazy dequeues

Olaf Chitil

Transactions on Programming Languages and Systems (TOPLAS), 27(1):182-196, January 2005.


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.

Download publication 226 kbytes (PDF)

Bibtex Record

author = {Olaf Chitil},
title = {Pretty printing with lazy dequeues},
month = {January},
year = {2005},
pages = {182-196},
keywords = {determinacy analysis, Craig interpolants},
note = {},
doi = {},
url = {},
    publication_type = {article},
    submission_id = {4434_1112110265},
    ISSN = {0164-0925},
    journal = {Transactions on Programming Languages and Systems (TOPLAS)},
    volume = {27},
    number = {1 },
    publisher = {ACM},

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

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

Last Updated: 21/03/2014