[Haskell-cafe] Pretty Printing Libraries with an Emphasis on Consistency

[Heinrich Apfelmus]

Oliver Charles wrote:
> Yes, hindent is exponential in its pretty printing and that's exactly the
> program I'm trying to speed up ;) To be specific, hindent has `sandbox`
> which runs a printer and then lets me make decisions on what the resulting
> state might be. I'm curious if there are other approaches.

I wager you need some kind of context-freeness to pretty print 
efficiently. At least, Wadler's pretty printer [1] makes use of that in 
section 2, where he argues that you can efficiently choose a minimal 
element in a huge set of possible layouts, the latter being represented 
by the type `Doc`.

   [1]: http://homepages.inf.ed.ac.uk/wadler/papers/prettier/prettier.pdf


If you allow non-context free restrictions on the possible layouts, as 
you do, then it's no longer clear to me how to efficiently pick an 
optimal one. To see whether this is a hard problem, you may want to do 
to the following test: Formalize (a subset of) the restrictions that you 
want to allow and check whether the problem is NP complete, i.e. whether 
you can encode solutions to an NP complete problem (knapsack?) as 
solutions of your desired layout algorithm.


Best regards,
Heinrich Apfelmus

--
http://apfelmus.nfshost.com