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 ... _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
