[Haskell-cafe] List concat

Neil Mitchell ndmitchell at gmail.com
Fri May 9 10:20:38 EDT 2008


data List a = Zero | One a | Two (List a) (List a)

On Fri, May 9, 2008 at 3:16 PM, Andrew Coppin
<andrewcoppin at btinternet.com> wrote:
> The function (++) :: [x] -> [x] -> [x] has O(n) complexity.

(++) = Two -- O(1) complexity

> If somebody were to invent some type that looks like [x] but actually uses
> some sort of tree rather than a linked list, you should be able to get O(1)
> concatenation. Has anybody ever implemented such a thing?

Yes. Me, last month.

I wasn't the first though - it's been in Lava for years as well, which
is where I got my inspiration.



More information about the Haskell-Cafe mailing list