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?
