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