[Haskell-cafe] List concat

[Ross Paterson]

On Fri, May 09, 2008 at 11:04:26PM +0100, Lennart Augustsson wrote:
> There are many implementations of such things.  Data.Sequence is one.  You can
> also make an implementation that has O(1) cons, snoc, and append, but that's
> rather tricky and has a large constant factor.

It's also rather difficult to construct a use case that distinguishes
between O(1) and O(log(min(n1,n2))) append.  For example, building a
sequence with either sort of append takes linear time.  The constant
factors are everything.