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 ...