[Haskell-cafe] Computing lazy and strict list operations at the
jon.fairbairn at cl.cam.ac.uk
Mon Jun 19 12:03:35 EDT 2006
On 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
il  = error "foo"
il [x] = (, x)
il (x:xs) = cof x (il xs)
where cof x ~(a,b) = (x:a, b)
Should do it, I think.
Jón Fairbairn Jon.Fairbairn at cl.cam.ac.uk
More information about the Haskell-Cafe