[Haskell-beginners] Thompson Exercise 9.13

[dan portin]

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?
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/beginners/attachments/20100714/b70db061/attachment.html