[Haskell-cafe] Computing lazy and strict list operations at
the same time
duncan.coutts at worc.ox.ac.uk
Mon Jun 19 12:06:40 EDT 2006
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
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.
More information about the Haskell-Cafe