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