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

[Daniel Fischer]

Am Donnerstag, 3. Januar 2008 14:48 schrieb 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?

Show a binary tree inorder? 
L-T-R gives (show L) ++ (show T ++ (show R))
gives ((show LL) ++ (showLT ++ (show LR))) ++ (show T ++ (show R))
gives (((show LLL) ++ (show LLT ++ (show LLR))) ++ (show LT ++ (show LR))) ++ 
(show T ++ (show R))

etc.
If the tree is large, you end up with a pretty large left association for the 
left subtree. True, there's lot of right association, too, but bad enough, I 
think.

Cheers,
Daniel