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