# [Haskell-cafe] Computing lazy and strict list operations at the same time

Robert Dockins 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
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

```