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

[Henning Thielemann]

On Thu, 3 Jan 2008, Isaac Dupree wrote:

> Achim Schneider wrote:
> > Achim Schneider <barsoap at web.de> wrote:
> >
> >> [...]
> >
> > I'm trying to grok that
> >
> > [] = id
> > ++ = .
> >
> > in the context of Hughes lists.
>
> they are also known as "difference lists", and also used at type String
> in the Prelude as "ShowS", to help avoid quadratic behavior when making
> complicated Strings.

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.
 Also
  http://en.wikipedia.org/wiki/Difference_list
 doesn't answer this question. Where exactly is the problem?