[Haskell-cafe] pretty-printing with fixed indentation increase per sub-structure

[Jeff Clites]

Is it possible that your size pre-calculation is inadvertently inducing quadratic behavior? I remember a pretty-printer implementation that generated both a line-broken and single-line version as it went, in order to avoid quadratic behavior due to backtracking. (IIRC, it would discard one as it went, if it determined that the single-line version of a sub-structure wouldn’t fit.) I don’t remember the exact details though so I know that’s a bit vague.

I know you are caching size in order to avoid calculating it multiple times, but I’m wondering if that is still inducing double-traversal (once for size, once to generate the final text), and if that double could turn into a square.

Just a possibility.

Jeff

> On Apr 17, 2023, at 3:51 AM, Johannes Waldmann <johannes.waldmann at htwk-leipzig.de> wrote:
> 
> Dear Cafe,
> 
> I was looking for a way to pretty-print Haskell literals
> (with lists, tuples, records with named and positional notation)
> like this example
> 
> ( Leftist
>    { tree = Branch
>        { left = Branch { left = Leaf, key = 4, right = Leaf }
>        , key = 3
>        , right = Leaf
>        }
>    , refs = listToFM [ ( Ref 13, [ 0 ] ), ( Ref 17, [ ] ) ]
>    }
> , [ Any, Any ]
> )
> 
> for each sub-structure, the indentation level
> (for the following lines) should increase - by a _fixed_ amount.
> in the above example: line break after "tree = Branch".
> But (missing from this example), line break _before_
> the list starts in "{ foo = [ 42 , ... ] ... }".
> 
> I found this impossible to do with wl-pprint
> but perhaps I did not try hard enough.
> 
> 
> Instead, I "invented" combinators `nest` and `skip`
> and made this prototypical implementation
> https://gitlab.imn.htwk-leipzig.de/autotool/all0/-/blob/master/todoc/src/Text/PrettyPrint/Dent.hs  (it has some explanatory text at the top)
> see also https://gitlab.imn.htwk-leipzig.de/autotool/all0/-/issues/960
> 
> but certainly this cannot be a new idea.
> 
> 
> While I do like the semantics (in the context of my application),
> I don't like the performance of my implementation.
> What am I doing wrong?
> It's just updating indentation level and current position,
> this should not take any time at all?
> 
> Of course, it would be best if I don't need the implementation at all -
> if the effect could be achieved via some combinators in
> established libraries (that have optimized implementation).
> 
> Any pointers appreciated.
> 
> 
> Best regards - J.
> _______________________________________________
> Haskell-Cafe mailing list
> To (un)subscribe, modify options or view archives go to:
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
> Only members subscribed via the mailman list are allowed to post.