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

Am Donnerstag, 3. Januar 2008 14:48 schrieb Henning Thielemann:

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?

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