[Haskell-cafe] *GROUP HUG*

[Eugene Kirpichov]

Why so? I think it wouldn't.

data FList a = FNil | FCons Int a (FList a)
empty = FNil
len FNil = 0
len (FCons n _) = n
cons x xs = FCons (1 + len xs) x xs
tail (FCons _ _ xs) = xs

2011/5/24 Tony Morris <tonymorris at gmail.com>:
> On 24/05/11 22:41, Johannes Waldmann wrote:
>> Then tell me, why does calculating the length of a (Haskell)
>> list has O(n) complexity.
> Infiniticity aside, tail would become O(n) if you store a length with
> each cons cell.
>
> --
> Tony Morris
> http://tmorris.net/
>
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>



-- 
Eugene Kirpichov
Principal Engineer, Mirantis Inc. http://www.mirantis.com/
Editor, http://fprog.ru/