Henning Thielemann wrote:
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
the point is that the the right-associativity of (++) doesn't prevent terms of the form ((a0 ++ a1) ++ a2) ++ a3 to arise due to explicit parentheses or (more important) recursive processing of data structures. consider showing a tree-like structure of the form ((a0 `Cons` a1) `Cons` a2) `Cons` a3 A naive Show instance will basically replace every Cons by (++) and produce a string concatenation of the offending left-associative form: ((show a0 ++ show a1) ++ show a2) ++ show a3 Tillmann