Hi,

I am new to Haskell (and programming). Thompson's exercise 9.13 in Craft of Functional Programming gave me trouble. Searching the list archives, I saw people define init (xs), last (xs), and so on, in a variety of complex ways (using the Maybe monad, using fairly complex post-processing). This seems to be a hard problem for beginners; at least, it was rather hard for me.

The problem is to define the Prelude functions init and last using foldr. After a while, I came up with:

-- *Exercise 9.13*: Use foldr (f, s, xs) to give definitions of the prelude functions
-- unzip, last, and init.

-- Clearly,
--     [(x, y), (x1, y1)] = (x, y) : (x1, y1) : ([], [])
--     foldr f ([], []) ((x, y):(x1, y1):[]) = f (x, y) (f (x1, y1) ([], []))
-- Hence, f (x, y) (xs, ys) must equal (x:xs, y:ys) for any xs, ys.

unzip :: [(a, b)] -> ([a], [b])
unzip xys = foldr f ([], []) xys
where f :: (a, b) -> ([a], [b]) -> ([a], [b])
       f (x, y) (xs, ys) = (x:xs, y:ys)

last :: [a] -> a
last xs = head $ foldr f [] xs
where f :: a -> [a] -> [a]
       f x [] = [x]
       f x ys = ys ++ [x]

init :: [a] -> [a]
init xs = tail $ foldr f [] xs
where f :: a -> [a] -> [a]
       f x [] = [x]
       f x (y:xs) = y : x : xs

Now, these seemed to be hard questions. So, I have three questions: (1) are these correct? They work on test cases, and I did do some quick proofs. They seem okay. (2) Is there a way to eliminate the post-processing of the lists (i.e., head in last and tail in init)? (3) Why the complex answers in the list archives? Am I missing something?