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

[Duncan Coutts]

On Mon, 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.

initlast :: [a] -> ([a],a)
initlast [x]    = ([], x)
initlast (x:xs) = (x : xs', x')
  where (xs', x') = initlast xs

It depends how you use it I think. If you look at the last element
immediately then you'll get a linear collection of thunks for the init.
However if you consume the init and then look at the last then I think
that will use constant space.

Duncan