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