[Haskell-cafe] *GROUP HUG*
ekirpichov at gmail.com
Wed May 25 08:46:51 CEST 2011
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
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
Principal Engineer, Mirantis Inc. http://www.mirantis.com/
More information about the Haskell-Cafe