title: Understanding performance characteristics of Wadler's Prettier Printer
body: <p>I am using the Prettier Printer implementation from the <code>contrib</code> library in <code>Idris</code>. </p>
  
  <p>When I fold with the <code>|//|</code> operator on a list of <code>Doc</code>s, the performance quickly explodes, i.e. the following code doesn't terminate before I lose my patience:</p>
  
  <pre><code>*IdrisFMT\PrettyDocs&gt; :exec toString 0 15 $ fold (|//|) $ map text $ words "this is a long sentence with a lot of words that I can use for testing the performance of the prettier printer implementation. I need a few more words to prove my point, though."
  </code></pre>
  
  <p>Please note, the above fold is equal to the pre-defined combinator <code>fillCat</code>. </p>
  
  <p>If I instead use the pre-defined <code>cat</code> combinator (<code>= group . vcat</code>), it terminates within a second:</p>
  
  <pre><code>*IdrisFMT\PrettyDocs&gt; :exec toString 0 15 $ cat $ map text $ words "this is a long sentence with a lot of words that I can use for testing the performance of the prettier printer implementation. I need a few more words to prove my point, though."
  "this\nis\na\nlong\nsentence\nwith\na\nlot\nof\nwords\nthat\nI\ncan\nuse\nfor\ntesting\nthe\nperformance\nof\nthe\nprettier\nprinter\nimplementation.\nI\nneed\na\nfew\nmore\nwords\nto\nprove\nmy\npoint,\nthough."
  </code></pre>
  
  <p>The <code>Doc</code> adt version of <code>cat $ map text $ words "this is a long sentence with a lot of words that I can use for testing the performance of the prettier printer implementation. I need a few more words to prove my point, though."</code> can be seen here: <a href="https://pastebin.com/4AJWcGnD" rel="noreferrer">https://pastebin.com/4AJWcGnD</a></p>
  
  <p>I understand that the <code>cat</code> combinator solves a much simpler problem, but I fail to see how <code>fillCat</code> is so complex as to never terminate. </p>
  
  <p>Could this be caused by a mistake in the implementation, or am I simply constructing too complex a document?</p>
  
  <p><strong>EDIT</strong></p>
  
  <p>The definition of the <code>|//|</code> operator is found here:
  <a href="https://github.com/idris-lang/Idris-dev/blob/master/libs/contrib/Text/PrettyPrint/WL/Combinators.idr#L65-L69" rel="noreferrer">https://github.com/idris-lang/Idris-dev/blob/master/libs/contrib/Text/PrettyPrint/WL/Combinators.idr#L65-L69</a></p>
  
  <pre><code>||| The document `(x |//| y)` concatenates document `x` and `y` with
  ||| a 'softbreak' in between. This effectively puts `x` and `y` either
  ||| right next to each other or underneath each other.
  (|//|) : Doc -&gt; Doc -&gt; Doc
  (|//|) = concatDoc softBreak
  </code></pre>