Thanks for your interest in our book, here are our solutions for chapters 2,3,4 and 5 (which are the only ones currently available). You should load this file into a text editor and separate the four files by hand Guy Lapalme (lapalme@iro.umontreal.ca) ***** Solutions of exercices for Chapter 2 ****************************** module Exerc2 where -- -- examples of solutions to exercises of chapter 2 -- import Array -- -- Exercise 2 -- fact 0 = 1 fact 1 = 1 fact n | n < 0 = -1 | otherwise = n * fact (n-1) -- -- Exercise 4 -- f l = reverse (f' l []) where f' [] r = r f' (x:xs) r = (2*x):(f' xs r) -- -- Exercise 6 -- average :: [Float]->Float average [] = error "average of []" average xs = sum xs / fromIntegral(length xs) average'::[Float]->Float average' [] = error "average' of []" average' xs = av xs 0 0 where av [] s n = s/n av (x:xs) s n = av xs (s+x) (n+1) middle [] = error "middle of []" middle xs | odd (length xs) = xs !! (length xs `div` 2) | otherwise = error "middle of even length list" -- -- Exercise 7 -- ex7_a1 = [(x,y) | x<-[1..2], y<-[2..5],(x+y)/=4] -- => [(1, 2), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5)] ex7_a2 = [x | x<-[1..10], (x `mod` 2) == 0] -- => [2, 4, 6, 8, 10] ex7_b1 = [ x | x<-[1..15] , x/=9] ex7_b2 = [x*(-1)^x|x<-[2..11]] -- -- Exercise 8 -- neg x = length [y|y<-x,y <0] rep n = [i|i<-[1..n],k<-[1..i]] -- -- Exercise 9 -- string2int s = s2i s 0 -- with explicit recursion using an accumulator where s2i [] v = v s2i (d:ds) v | isDigit d = s2i ds (v*10+digitToInt d) | otherwise = error ("string2int: illegal digit=" ++ [d]) string2int' s = foldl f 0 s -- with a left fold where f v d | isDigit d = v*10+digitToInt d | otherwise = error ("string2int: illegal digit=" ++ [d]) -- -- Exercise 10 -- ex10_1 :: [Int] ex10_1 = map fst [(1,2),(3,8),(0,6),(3,1)] ex10_2 :: (Int,Int) ex10_2 = (foldr f 0 l,foldl f 0 l) where l = [6,9,8,3,10] f x y = (x+y) `div` 2 ex10_3 :: [Int] ex10_3 = foldr (++) [] [[1,2,3],[4,5,6],[],[7]] -- -- Exercise 11 -- compose :: (a -> b) -> (c -> a) -> c -> b compose f g x = f (g x) -- the same as (.) -- -- Exercise 12 -- ex12_1 = array (1,4) [(1,11),(2,20),(3,36),(4,47)] ex12_2 = array (1,14) (zip [1..14] [ x | x<-[1..15] , x/=9]) ex12_3 = array (1,10) [(x-1,x*(-1)^x)|x<-[2..11]] -- see ex7_2b -- -- Exercise 13 -- ex13_1 = array ((1,1),(3,3)) [((1,1),2),((1,2),3),((1,3),4), ((2,1),5),((2,2),6),((2,3),7), ((3,1),8),((3,2),9),((3,3),10)] ex13_2 = array ((1,1),(3,3)) [(ij,v)|(ij,v)<-zip [(i,j)|i<-[1..3],j<-[1..3]] [2..10]] transpose3x3 a = array ((1,1),(3,3)) [((i,j),a!(j,i))|i<-[1..3],j<-[1..3]] transposeNxN a = array ((ly,lx),(hy,hx)) [ ((j,i),a!(i,j)) | i <-[lx..hx],j<-[ly..hy] ] where ((lx,ly),(hx,hy)) = bounds a -- -- Exercise 14 -- cube :: Num a => a -> a cube x = x*x*x maxi :: Ord a => a -> a -> a maxi x y | x>= x = x | otherwise = y sumAtoB :: (Num a, Enum a) => a -> a -> a sumAtoB a b = sum [a..b] -- -- Exercise 15 -- -- (!) :: Ix a => Array a b -> a -> b -- bounds :: Ix a => Array a b -> (a,a) -- indices :: Ix a => Array a b -> [a] -- elems :: Ix a => Array a b -> [b] ***** Solutions of exercices for Chapter 3 ****************************** module Exerc3 where import Prelude hiding (sum) -- -- exercise 1 -- -- (f $! a) b -- a only -- (f a) $! b -- b only -- (f $! a) $! b -- both a and b -- -- exercise 2 -- -- time counting version powerT k = if (k==0) then 1 else if (k `mod` 2) == 0 then 1 + (powerT (k `div` 2)) else 1 + (powerT (k `div` 2)) -- recurrence relation solution (for k>0): powerTsol k = truncate(logBase 2 k) + 2 -- -- exercise 3 -- -- head : a. O(1), b. O(n), c. O(mn) -- length : a. O(n), b. O(n), c. O(mn) -- sum : a. O(mn), b. O(mn), c. O(mn) -- -- exercise 4 -- -- original version prodsum x = prod x + sum x prod 0 = 1 prod n = n * prod (n - 1) sum 0 = 0 sum n = n + sum (n - 1) -- tail recursive version (a) prodsumTR x = prodTR x 1 + sumTR x 0 prodTR 0 r = r prodTR n r = prodTR (n-1) (n*r) sumTR 0 r = r sumTR n r = sumTR (n-1) (n+r) -- one pass - tuple version (b) prodsumTP x = f+t where (f,t) = prodsum' x prodsum' 0 = (1,0) prodsum' n = (n*f',n+t') where (f',t') = prodsum' (n-1) -- one pass - no tuple (c) prodsumNTP x = prodsumNTP' x 1 0 where prodsumNTP' 0 f t = f+t prodsumNTP' n f t = prodsumNTP' (n-1) (n*f) (n+t) ***** Solutions of exercices for Chapter 4 ****************************** module Exerc4 where -- -- exercise 1 -- -- If we assume n lists of length m -- -- concat1(n,m) : O(m.n) -- concat2(n,m) : O(m.n^2) -- -- -- exercise 2 -- comp f g l = [f x | x <- map g l, x>10] comp' f g l = [f (g x) | x <- l, g x > 10] comp'' f g l = [f gx | x <-l, let gx=g x, gx>10] -- -- exercise 3 -- split x [] = ([],[]) split x (y:ys) | y <= x = (y:ys1,ys2) | otherwise = (ys1,y:ys2) where (ys1,ys2) = split x ys split' x l = splitTR x l ([],[]) where splitTR x [] (ys1,ys2) = (reverse ys1,reverse ys2) splitTR x (y:ys) (ys1,ys2) | y <= x = splitTR x ys (y:ys1,ys2) | otherwise = splitTR x ys (ys1,y:ys2) -- -- exercise 5 -- data BinTree a = Empty | NodeBT a (BinTree a) (BinTree a) deriving Show bt = (NodeBT 5 (NodeBT 8 (NodeBT 3 Empty Empty) (NodeBT 1 Empty Empty)) (NodeBT 6 Empty (NodeBT 4 Empty Empty))) bt'= (NodeBT 4 (NodeBT 6 (NodeBT 2 Empty Empty) (NodeBT 1 Empty Empty)) (NodeBT 6 Empty (NodeBT 5 Empty Empty))) bt''=(NodeBT 5 (NodeBT 8 Empty (NodeBT 1 Empty Empty)) (NodeBT 6 Empty (NodeBT 4 Empty Empty))) sameStruct Empty Empty = True sameStruct (NodeBT _ lf rt) (NodeBT _ lf' rt') = sameStruct lf lf' && sameStruct rt rt' sameStruct _ _ = False -- -- exercise 6 -- inorder Empty = [] inorder (NodeBT a l r) = inorder l ++ [a] ++ inorder r size tr = length (inorder tr) size' Empty z = z size' (NodeBT a l r) z = 1 + size' l (size' r z) {- examples of evaluations and results ? comp (+1) (*2) [1..10] [13, 15, 17, 19, 21] ? comp' (+1) (*2) [1..10] [13, 15, 17, 19, 21] ? comp'' (+1) (*2) [1..10] [13, 15, 17, 19, 21] ? split 5 [1..10] ([1, 2, 3, 4, 5], [6, 7, 8, 9, 10]) ? split' 5 [1..10] ([1, 2, 3, 4, 5], [6, 7, 8, 9, 10]) ? sameStruct bt bt' True ? sameStruct bt bt'' False -} ***** Solutions of exercices for Chapter 5 ****************************** module Exerc5 where -- -- examples of solutions to exercises of chapter 5 -- --- --- Exercise 1 --- dist (x,y) = sqrt (x^2+y^2) data Point = Pt (Float,Float) instance Eq Point where (Pt p1) == (Pt p2) = (dist p1 == dist p2) instance Ord Point where (Pt p1) <= (Pt p2) = (dist p1 <= dist p2) -- -- Exercise 2 -- -- the changes are in the following: enPQ :: (a -> a -> Bool) -> a -> PQueue a -> PQueue a type PQueue a = [a] enPQ smaller x [] = [x] enPQ smaller x r@(e:r') | x `smaller` e = x:r | otherwise = e:(enPQ smaller x r') -- -- Exercise 3 -- inside s x = or [x'==x|x'<-s] included s1 s2 = and [inside s2 x|x<-s1] inter s1 s2 = [x|x<-s1, inside s2 x] union s1 s2 = s1++[x|x<-s2, not (inside s1 x)] -- -- Exercises 7 and 8 -- need access to the internals of Heap.hs which are repeated here ---------------------------------------------------------------------- --module Heap(Heap,emptyHeap,heapEmpty,findHeap,insHeap,delHeap) -- where emptyHeap:: (Ord a) => Heap a heapEmpty:: (Ord a) => Heap a -> Bool findHeap :: (Ord a) => Heap a -> a insHeap :: (Ord a) => a -> Heap a -> Heap a delHeap :: (Ord a) => Heap a -> Heap a -- IMPLEMENTATION with Leftist Heap -- adapted from C. Okasaki Purely Functional Data Structures p 197 data (Ord a) => Heap a = EmptyHP | HP a Int (Heap a) (Heap a) deriving Show emptyHeap = EmptyHP heapEmpty EmptyHP = True heapEmpty _ = False findHeap EmptyHP = error "findHeap:empty heap" findHeap (HP x _ a b) = x insHeap x h = merge (HP x 1 EmptyHP EmptyHP) h delHeap EmptyHP = error "delHeap:empty heap" delHeap (HP x _ a b) = merge a b -- auxiliary functions rank :: (Ord a) => Heap a -> Int rank EmptyHP = 0 rank (HP _ r _ _) = r makeHP :: (Ord a) => a -> Heap a -> Heap a -> Heap a makeHP x a b | rank a >= rank b = HP x (rank b + 1) a b | otherwise = HP x (rank a + 1) b a merge ::(Ord a) => Heap a -> Heap a -> Heap a merge h EmptyHP = h merge EmptyHP h = h merge h1@(HP x _ a1 b1) h2@(HP y _ a2 b2) | x <= y = makeHP x a1 (merge b1 h2) | otherwise = makeHP y a2 (merge h1 b2) -- end of internals of Heap.hs ---------------------------------------------------------------------- listToHeap xs = foldr insHeap emptyHeap xs listToHeap' [] = EmptyHP listToHeap' [x] = HP x 1 EmptyHP EmptyHP listToHeap' xs = merge (listToHeap' xs1) (listToHeap' xs2) where xs1 = take n xs xs2 = drop n xs n = length xs `div` 2 --- --- Exercise 8 --- -- Replacing the value of the first parameter in the definition of merge -- because h = h1 = HP x 1 EmptyHP EmptyHP -- a1 = b1 = EmptyHP insHeap' :: (Ord a) => a -> Heap a -> Heap a insHeap' x EmptyHP = HP x 1 EmptyHP EmptyHP -- second case of merge can never occur insHeap' x h2@(HP y _ a2 b2) -- | x <= y = makeHP x EmptyHP (merge EmptyHP h2) | x <= y = makeHP x EmptyHP h2 -- | otherwise = makeHP y a2 (merge (HP x 1 EmptyHP EmptyHP) b2) -- which by definition of insHeap' can be rewritten as | otherwise = makeHP y a2 (insHeap' x b2) --- --- Exercise 9 --- data (Ord a,Show a) => AVLTree a = EmptyAVL | NodeAVL a Int (AVLTree a) (AVLTree a) deriving Show emptyAVL = EmptyAVL height EmptyAVL = 0 height (NodeAVL _ h lf rt) = h rotateLeft,rotateRight :: (Ord a,Show a)=> AVLTree a -> AVLTree a rotateLeft EmptyAVL = EmptyAVL rotateLeft (NodeAVL v _ (NodeAVL lv _ lflf lfrt) rt) = NodeAVL lv h lflf (NodeAVL v h' lfrt rt) where h' = max (height lfrt) (height rt) + 1 h = max h' (height lflf) + 1 rotateRight EmptyAVL = EmptyAVL rotateRight (NodeAVL v _ lf (NodeAVL rv _ rtlf rtrt)) = NodeAVL rv h (NodeAVL v h' lf rtlf) rtrt where h' = max (height rtlf) (height lf) + 1 h = max h' (height rtrt) + 1 dRotLeftRight , dRotRightLeft :: (Ord a,Show a) => AVLTree a -> AVLTree a dRotRightLeft (NodeAVL v _ lf (NodeAVL rtv _ (NodeAVL rtlv _ rtlflf rtlfrt) rtrt)) = NodeAVL rtlv h (NodeAVL v h' lf rtlflf) (NodeAVL rtv h'' rtlfrt rtrt) where h''= max (height rtlfrt) (height rtrt) + 1 h' = max (height rtlflf) (height lf) + 1 h = max h' h'' + 1 dRotLeftRight (NodeAVL v _ (NodeAVL lfv _ lflf (NodeAVL lfrv _ lfrtlf lfrtrt)) rt) = NodeAVL lfrv h (NodeAVL lfv h' lflf lfrtlf) (NodeAVL v h'' lfrtrt rt) where h''= max (height lfrtrt) (height rt) + 1 h' = max (height lflf) (height lfrtlf) + 1 h = max h' h'' + 1 addAVL i EmptyAVL= NodeAVL i 1 EmptyAVL EmptyAVL addAVL i (NodeAVL v _ lf rt) | i < v = let newlf@(NodeAVL newlfv h _ _) = addAVL i lf h' = height rt in if ((h - h') == 2) then if i < newlfv then rotateLeft (NodeAVL v 0 newlf rt) else dRotLeftRight (NodeAVL v 0 newlf rt) else (NodeAVL v (max h h' + 1) newlf rt) | otherwise = let newrt@(NodeAVL newrtv h _ _) = addAVL i rt h' = height lf in if ((h - h') == 2) then if i > newrtv then rotateRight (NodeAVL v 0 lf newrt) else dRotRightLeft (NodeAVL v 0 lf newrt) else (NodeAVL v (max h h' + 1) lf newrt) {- examples of calls and results ? foldr addAVL emptyAVL [7,6..1] NodeAVL 4 3 (NodeAVL 2 2 (NodeAVL 1 1 EmptyAVL EmptyAVL) (NodeAVL 3 1 EmptyAVL EmptyAVL)) (NodeAVL 6 2 (NodeAVL 5 1 EmptyAVL EmptyAVL) (NodeAVL 7 1 EmptyAVL EmptyAVL)) -} -- -- Exercise 10 -- --The deletion of a node is a complex process, possibly involving --O(log n) rotations. For an information description of the algorithm, --see: --R.L. Kruse, Data Structures and Program Design, Prentice Hall, 1984, --pp. 365-367.