25 May
2011
25 May
'11
2:46 a.m.
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
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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
-- Eugene Kirpichov Principal Engineer, Mirantis Inc. http://www.mirantis.com/ Editor, http://fprog.ru/