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

[Jon Fairbairn]

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)
--                      !


Should do it, I think.

-- 
Jón Fairbairn                              Jon.Fairbairn at cl.cam.ac.uk