[Haskell-cafe] Ultra-newbie Question

[Daniel Peebles]

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.fischer at 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.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
> >
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20100920/f295db1c/attachment.html