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

[Robert Dockins]

On Jun 19, 2006, at 12:50 PM, Duncan Coutts wrote:

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


Actually, the OP asked for constant stack space, which is quite  
different and much easier to achieve.


> 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?


That is, nonetheless, an interesting question.


> 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


Rob Dockins

Speak softly and drive a Sherman tank.
Laugh hard; it's a long way to the bank.
           -- TMBG