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

[Robert Dockins]

On Jun 19, 2006, at 11:24 AM, 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.


initlast :: [a] -> ([a],a)
initlast (x:xs) = f x xs id
where
   f x (y:ys) g = f y ys (g . (x:))
   f x []     g = (g [],x)



Its within the letter, if maybe not the spirit of the rules.  The  
accumulated function could arguably be considered to be traversing  
the list again.  FYI, the technique is a fairly well known one for  
overcoming the quadratic behavior of repeated (++).


Rob Dockins

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