[Haskell-cafe] Ultra-newbie Question

Daniel Fischer daniel.is.fischer at web.de
Mon Sep 20 09:49:28 EDT 2010


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

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
>



More information about the Haskell-Cafe mailing list