[Haskell-cafe] Ultra-newbie Question

[Jean-Marie Gaillourdet]

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.

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)

In order to compute g l you only have to evaluate e_n, not all the other e_i.

Hope this helps.

Jean