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

[Jerzy Karczmarczuk]

> 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?

After Robert Dockins, Jon Fairbarn and Duncan Coutts, one more,
nothing original...:

initlast (x:xs) = inl x xs where
   inl x (a:as) = (x:q,y) where (q,y) = inl a as
   inl x [] = ([],x)

Such tricks become your second nature, when you take the solution
(lazy) of the "repmin" problem by Richard Bird, you put it under your
pillow, and sleep for one week with your head close to it.


Jerzy Karczmarczuk