[Haskell-cafe] Difference lists and ShowS (Was: The Worker/Wrapper Transformation)

[Tillmann Rendel]

Henning Thielemann wrote:
> Sometimes I believed that I understand this reason, but then again I do
> not understand. I see that left-associative (++) like in
>   ((a0 ++ a1) ++ a2) ++ a3
>  would cause quadratic time. But (++) is right-associative and 'concat' is
> 'foldr'. They should not scan the leading lists more than once

the point is that the the right-associativity of (++) doesn't prevent 
terms of the form

   ((a0 ++ a1) ++ a2) ++ a3

to arise due to explicit parentheses or (more important) recursive 
processing of data structures. consider showing a tree-like structure of 
the form

   ((a0 `Cons` a1) `Cons` a2) `Cons` a3

A naive Show instance will basically replace every Cons by (++) and 
produce a string concatenation of the offending left-associative form:

   ((show a0 ++ show a1) ++ show a2) ++ show a3

Tillmann