Pretty printing with lazy dequeues

Chitil, Olaf (2005) Pretty printing with lazy dequeues. Transactions on Programming Languages and Systems (TOPLAS), 27 (1). pp. 163-184. ISSN 0164-0925. (Full text available)

Download (232kB)


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.

Item Type: Article
Uncontrolled keywords: Algorithms, Haskell, lazy functional programming
Subjects: Q Science > QA Mathematics (inc Computing science) > QA 76 Software, computer programming,
Divisions: Faculties > Science Technology and Medical Studies > School of Computing > Theoretical Computing Group
Depositing User: Mark Wheadon
Date Deposited: 24 Nov 2008 18:03
Last Modified: 06 Sep 2011 01:30
Resource URI: (The current URI for this page, for reference purposes)
  • Depositors only (login required):


Downloads per month over past year