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
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
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