Explanation:<p>bufOps is a dictionary which holds a bunch of functions accessed with the getters on it. For the sake of this comment, we can concretize and use (buf_empty bufOps) as [] and (buf_append bufOps) as ++.<p>This code then essentially performs:<p><pre><code> foldr (flip (++)) [] xs
</code></pre>
Which, if you look up the definition of foldr, is:<p><pre><code> ((([] ++ xN) ++ ... ) ++ x2) ++ x1
</code></pre>
And a definition of ++ is of course:<p><pre><code> [] ++ ys = ys
(x:xs) ++ ys = x : (xs ++ ys)
</code></pre>
This means that for lists of this sort a ++ b runs in time O(length a), because it has to descend down the leftmost list to find the empty list -- only once it finds [] can it "work its way backwards" to append elements from a onto b.<p>If each of the x1, x2, ... xN has m elements, then we do 0 + m + 2m + ... + N m = m * N * (N + 1) / 2 operations. Each ++ will do about N operations and we'll do about N of them; it's O(N^2).<p>The new algorithm, `concat (reverse xs)`, works because `xs` is just a list which can be reversed by traversing down it in O(N) time, then those can be merged together in O(N * m) time.
So the original line of code has apparently been present since the very first import by Sigbjørn Finne in <a href="https://github.com/nominolo/HTTP/blob/c4765e822eb92196fec95560f8f640018d18737f/Network/HTTP/Base.hs" rel="nofollow">https://github.com/nominolo/HTTP/blob/c4765e822eb92196fec955...</a> (check line 443).<p>If a Haskell expert (e.g., he authored hdirect -- an IDL compiler and interface with Win32 COM -- sadly defunct now) makes this kind of mistake, how are mere mortals supposed to reason about algorithmic efficiency?
Here is the context<p><a href="http://www.reddit.com/r/haskell/comments/1sh67u/the_reason_why_cabal_update_takes_so_long/" rel="nofollow">http://www.reddit.com/r/haskell/comments/1sh67u/the_reason_w...</a>
I'd definitely like to see an explanation of what's going on, both at a high level and the specifics of the code. As a Haskell beginner-intermediate, I don't really know what most of those functions are doing (much less the context of what that function's purpose is), but I feel I could probably understand an explanation if it were given.