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

Jon Fairbairn 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
> impossible.

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

```