## Haskell Cabal O(n^2) / O(n) Fix

From: andrew cooke <andrew@...>

Date: Tue, 10 Dec 2013 07:58:19 -0300

This patch
https://github.com/nominolo/HTTP/commit/b9bd0a08fa09c6403f91422e3b23f08d339612eb
is on code that has existed since 2009, and which causes many users pain.

This is what it took to find it:
http://www.reddit.com/r/haskell/comments/1sh67u/the_reason_why_cabal_update_takes_so_long/cdxnr5l

Here's the whole thread:
http://www.reddit.com/r/haskell/comments/1sh67u/the_reason_why_cabal_update_takes_so_long/

If you squint at the code, you can guess why (I assume it's the iterative
append issue you get in a bunch of languages that allocate space dynamically).
So I wonder to what extent this is the infamous "it's hard to work out
performance in Haskell" and to what extent it's just bad luck.

Andrew