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 _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
