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

C Rodrigues red5_2 at hotmail.com
Mon Jun 19 11:24:44 EDT 2006

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 

More information about the Haskell-Cafe mailing list