[Haskell-cafe] Re: sort and lazyness (?)

[Luke Palmer]

On Fri, Dec 19, 2008 at 8:54 AM, Bayley, Alistair <
Alistair.Bayley at invesco.com> wrote:

> >       > How does reverse work in constant space?  At the
> > moment I can't imagine
> >       > it doing so; that's why I tried it, but of course you
> > could be right.
> >
> >
> >       It allocates a new list cell for every cell it finds in
> > the input list.
> >       If the input list can be garbage collected then reverse
> > takes constant
> >       space because each time it inspects a list cell from
> > the input list that
> >       cell can be garbage collected. If the input list is
> > being retained for
> >       some other reason then reverse will take linear space.
> >
> >
> > I don't think that's true.  It must inspect the whole input
> > list to give the first element of the output list, but it
> > cannot garbage collect the input list because it needs to
> > yield every element of it.
>
> reverse creates the output list by pulling items from the head of the
> input list, and prefixing them to the output list.


*Tail recursively! *That is a very important point.* *Let's have a closer
look at an explicitly recursive version.

reverse xs = go [] xs
  where
  go out [] = out
  go out (x:xs) = go (x:out) xs
*
*Now let's do a rewrite chain:

reverse (enumFromTo 1 4)
go [] (enumFromTo 1 4)
go [] (1:enumFromTo 2 4)
go (1:[]) (enumFromTo 2 4)
go (1:[]) (2:enumFromTo 3 4)
go (2:1:[]) (enumFromTo 3 4)
go (2:1:[]) (3:enumFromTo 4 4)
go (3:2:1:[]) (enumFromTo 4 4)
go (3:2:1:[]) (4:enumFromTo 5 4)
go (4:3:2:1:[]) (enumFromTo 5 4)
go (4:3:2:1:[]) []
4:3:2:1:[]

(For sanity I skipped the number evaluation steps, but enumFromTo would have
been forcing them to check for the end, so it ends up the same)

We needed to construct the entire reversed list before we could see the
first cons cell.

There *is* a very strange implementation of reverse whose spine is as lazy
as the input spine (but forcing the first element will still force the whole
input spine).  But it is quite odd, and certainly is not arrived at by the
compiler automatically from the definition in the Prelude.

I verified with -O2.  length . reverse is not constant space in GHC.  And
there really is no reasonable way it could be (save for specific RULES
pragmata).

Luke

After each item has
> been pulled from the input, the list node can be GC'd from the input
> list. Also, if the output list is itself being consumed by a function
> which does not require the entire list (like length) then again the list
> node can be GC'd soon after consumption.
>
>
> > ghci>  length $ reverse [1..10^7]
>
> This is a compiler optimisation, I think, so will probably require ghc
> -O(2?).
>
> Alistair
> *****************************************************************
> Confidentiality Note: The information contained in this message,
> and any attachments, may contain confidential and/or privileged
> material. It is intended solely for the person(s) or entity to
> which it is addressed. Any review, retransmission, dissemination,
> or taking of any action in reliance upon this information by
> persons or entities other than the intended recipient(s) is
> prohibited. If you received this in error, please contact the
> sender and delete the material from any computer.
> *****************************************************************
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20081219/b856a981/attachment.htm