On Sep 20, 2010, at 5:10 AM, Jean-Marie Gaillourdet wrote: > Hi Alberto, > > On 20.09.2010, at 10:53, Alberto G. Corona wrote: > >> 2010/9/18 Daniel Fischer <daniel.is.fisc...@web.de> >> >>> n_lastn n = reverse . take n . reverse >> >> Which is the most elegant definition, but it's an O(length list) space >> operation (as are all others proposed so far). T >> >> No!. You forget laziness!. it is 0(n) with n= the parameter passed to >> n_lastn. >> >> It is not O(length list). >> >> the reversed and de-reversed elements are just the ones being taken , not >> the whole list. >> >> (please kill me if I´m wrong. I don´t want to live in a world where beauty >> is inneficient) > > I am afraid you are argumentation is wrong. > > Let's see: > >> f :: [a] -> a >> f = head . reverse > > This is a function running in O(n) time, where n is the length of given list. > That is, because f has to follow at least n pointers in order to reach the > end of the parameter list. It might be much more expensive if the list has to > be computed, because f got only a thunk to cumpute a list instead of a > finished list.
I don't believe he was claiming O(n) time, only O(n) space, which I am inclined to believe. Your 'f' should also run in O(1) space. In general, there can be no function depending in any way on the location of the end of the list that isn't O(length list) time, because if nothing else the end of the list must be discovered, which requires that much time no matter what the algorithm. > Lazyness helps helps to reduce work if your input list is lazily constructed > and your function forces the returned element. Then you don't have to force > all elements of the list, only the last one. Let's say l = [e_0, ..., e_n]. > All the e_i are expensive calculations. > >> g :: [a] -> a >> g xs = x `seq` x >> where >> x = head (reverse xs) > Can "x `seq` x" have any different strictness than just plain x? I may be wrong, but I don't think so. Essentially, it's saying that "when x is needed, evaluate x to WHNF and then return x". -- James _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
