Nice explanation. I'm surprised that no one so far mentioned a cool trick for getting around this using a different way to define mappend as function composition, to make sure ++ is applied in the right order, since it's from LYAH (scroll to end of the linked chapter):
But, going back to the patch in question, the original code was effectively this:
Since flip had been applied to (++), the resulting operator you now want to treat as left associative to avoid quadratic blow-up. The code, however, uses the right-associative fold, foldr, to join the list of strings str.The patch fixes this problem by replacing the code with the equivalent code
And how is concat defined in the libraries? Looking at the source [1], it's Thus the fix is basically This version reverses strs, at linear-time cost, to be able to apply the normal, unflipped (++) with a right-associative fold and thus avoid the dreaded quadratic blow-up.[1] http://hackage.haskell.org/package/base-4.6.0.1/docs/src/GHC...
EDITED TO ADD: Also, if you knew the buffers were vanilla Strings, you could even eliminate the reverse overhead since
for all finite lists xs. Thus you could flip (++) and use foldl instead of foldr to get an efficient implementation like this: