[Haskell-cafe] Thompson's Exercise 9.13

[Bernard Pope]

On Sun, 2005-04-10 at 15:44 +0900, Kaoru Hosokawa wrote:
> I've been working through Thompson's exercises and got to one I could 
> not solve. It's Exercise 9.13. This is where I need to define init 
> using foldr.
> 
> 	init :: [a] -> [a]
> 	init "Greggery Peccary" ~> "Greggary Peccar"

Hi,

Here's a tentative solution:

myinit xs
   = foldr (f (length xs)) [] xs
   where
   f len next []
      | len == 1 = []
      | otherwise = [next]
   f len next list@(x:xs)
      | length list + 1 == len = next : xs
      | otherwise = x : next : xs

What's the algorithm? 

We want to float the last item in the list to the front, and then drop
it off when the whole list is processed.

The trick is in knowing when we've processed the entire list. That is
done by keeping track of the length of the original input list, and
comparing that with the number of items processed. There is a special
case when the original list has only one element in it.

Not very efficient though! Also it behaves differently than init for the
empty list.

Perhaps you can come up with a more efficient solution!

Cheers,
Bernie.