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
