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
where
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 (++).
Rob Dockins
Speak softly and drive a Sherman tank.
Laugh hard; it's a long way to the bank.
-- TMBG
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
