Am Donnerstag, 3. Januar 2008 14:48 schrieb Henning Thielemann: > On Thu, 3 Jan 2008, Isaac Dupree wrote: > > Achim Schneider wrote: > > > Achim Schneider <[EMAIL PROTECTED]> 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 _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
