[Haskell-cafe] Computing lazy and strict list operations at the
robdockins at fastmail.fm
Mon Jun 19 11:59:29 EDT 2006
On Jun 19, 2006, at 11:24 AM, 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:xs) = f x xs id
f x (y:ys) g = f y ys (g . (x:))
f x  g = (g ,x)
Its within the letter, if maybe not the spirit of the rules. The
accumulated function could arguably be considered to be traversing
the list again. FYI, the technique is a fairly well known one for
overcoming the quadratic behavior of repeated (++).
Speak softly and drive a Sherman tank.
Laugh hard; it's a long way to the bank.
More information about the Haskell-Cafe