[Haskell-cafe] Ultra-newbie Question

James Andrew Cook mokus at deepbondi.net
Mon Sep 20 09:20:53 EDT 2010


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.fischer at 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



More information about the Haskell-Cafe mailing list