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.