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

[Henning Thielemann]

On Thu, 3 Jan 2008, Daniel Fischer wrote:

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

With difference lists I write

shows L . (shows T . shows R)
(shows LL . (showsLT . shows LR)) . (shows T . shows R)
((shows LLL . (shows LLT . shows LLR)) . (showsLT . shows LR)) . (shows T . shows R)

I still need to resolve three (.) until I get to the first character of
the result string, but for the subsequent characters I do not need to
resolve those dots. In the end, resolution of all (.) may need some time
but then concatenation is performed entirely right-associative. Seems to
be that this is the trick ...