Have we put off the ultra-newbie by derailing his simple question into a discussion on subtle issues he shouldn't care about this early on?
On Mon, Sep 20, 2010 at 3:49 PM, Daniel Fischer <daniel.is.fisc...@web.de>wrote: > On Monday 20 September 2010 15:20:53, James Andrew Cook wrote: > > 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, > > Right. > > > which I am inclined to believe. Your 'f' should also run in O(1) space. > > Alas, no. At least with GHC (and I don't see how it could be otherwise), > reverse is always an O(length xs) space operation. > > reverse :: [a] -> [a] > #ifdef USE_REPORT_PRELUDE > reverse = foldl (flip (:)) [] > #else > reverse l = rev l [] > where > rev [] a = a > rev (x:xs) a = rev xs (x:a) > #endif > > Both, the report-reverse and the other version, build the reversed list as > an accumulation parameter of a tail-recursive function. The entire reversed > list is returned in one piece once the end is reached. > > The only way to make functions using reverse run in less than O(length xs) > space is, as far as I know, using rewrite rules > (e.g. head . reverse = last). > > > 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? > > No, "x `seq` x" is exactly equivalent to 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". > > Exactly. In "x `seq` y", the seq forces evaluation of x to WHNF precisely > if/when y has to be evaluated to WHNF. > > > > > -- James > > > > _______________________________________________ > 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