Functional Pearl: Pretty Printing with Lazy Dequeues

Functional Pearl: Pretty Printing with Lazy Dequeues

Olaf Chitil.


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.


Available as 136K gzipped postscript or 161K PDF.