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

On Thu, 3 Jan 2008, Isaac Dupree wrote:

Achim Schneider wrote:

...

Achim Schneider 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?