[Haskell-cafe] Computing lazy and strict list operations at the same time

[Duncan Coutts]

On Mon, 2006-06-19 at 17:03 +0100, Jon Fairbairn wrote:
> On 2006-06-19 at 15:24-0000 "C Rodrigues" wrote:
> > Here's a puzzle I haven't been able to solve.  Is it possible to write the 
> > initlast function?
> > 
> > There are functions "init" and "last" that take constant stack space and 
> > traverse the list at most once.  You can think of traversing the list as 
> > deconstructing all the (:) [] constructors in list.
> > 
> > init (x:xs) = init' x xs
> >   where init' x (y:ys) = x:init' y ys
> >         init' _ [] = []
> > 
> > last (x:xs) = last' x xs
> >   where last' _ (y:ys) = last' y ys
> >         last' x [] = x
> > 
> > Now, is there a way to write initlast :: [a] -> ([a], a) that returns the 
> > result of init and the result of last, takes constant stack space, and 
> > traverses the list only once?  Calling reverse traverses the list again.  I 
> > couldn't think of a way to do it, but I couldn't figure out why it would be 
> > impossible.
> 
> 
> il [] = error "foo"
> il [x] = ([], x)
> il (x:xs) = cof x (il xs)
>             where cof x ~(a,b) = (x:a, b)
> --                      !

>From a quick test, it looks like none of our suggested solutions
actually work in constant space.

main = interact $ \s ->
  case il s of
    (xs, x) -> let l = length xs
               in l `seq` show (l,x)

using ghc:
ghc -O foo.hs -o foo
./foo +RTS -M10m -RTS < 50mb.data

using runhugs:
runhugs foo.hs < 50mb.data

in both cases and for each of the three solutions we've suggested the
prog runs out of heap space where the spec asked for constant heap use.

So what's wrong? In my test I was trying to follow my advice that we
should consume the init before consuming the last element. Was that
wrong? Is there another way of consuming the result of initlast that
will work in constant space?

Note that by changing discarding the x we do get constant space use:
main = interact $ \s ->
  case il s of
    (xs, x) -> let l = length xs
               in l `seq` show l  -- rather than 'show (l,x)'

Why does holding onto 'x' retain 'xs' (or the initial input or some
other structure with linear space use)?

Duncan