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 <[email protected]>:
> 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
> [email protected]
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>



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

_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe

Reply via email to