Well, if you want to be picky evaluating (calling) (xs ++ ys) takes whatever time it takes to evaluate xs to WHNF and if xs is null then it in addition takes the time it takes to evaluate ys to WHNF. Saying anything about time complexity with lazy evaluation requires a lot of context to be exact.
-- Lennart On Mon, May 12, 2008 at 7:36 AM, <[EMAIL PROTECTED]> wrote: > G'day all. > > Quoting Andrew Coppin <[EMAIL PROTECTED]>: > > The function (++) :: [x] -> [x] -> [x] has O(n) complexity. >> > > That's not entirely true. > > When you call (++), it does O(1) work. If you evaluate k cons cells. > it takes O(min(k,n)) work. > > Cheers, > Andrew Bromage > > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe@haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe >
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
