## Archive for July, 2007

### Exercise 7.2

Saturday, July 28th, 2007
```data InternalTree a = ILeaf | IBranch a (InternalTree a) (InternalTree a) deriving Show   takeTree :: Int -> InternalTree a -> InternalTree a takeTree 0 t = ILeaf takeTree n ILeaf = ILeaf takeTree n (IBranch a x y) = IBranch a (takeTree (n-1) x) (takeTree (n-1) y)   takeTreeWhile :: (a -> Bool) -> InternalTree a -> InternalTree a takeTreeWhile f ILeaf = ILeaf takeTreeWhile f (IBranch a x y) = if (f a) then IBranch a (takeTreeWhile f x) (takeTreeWhile f y) else ILeaf```

(Technical error 13 applies to this exercise.)

### Exercise 7.1

Saturday, July 28th, 2007
```data Tree a = Leaf a | Branch (Tree a) (Tree a) deriving Show   foldTree :: (a -> b -> b) -> (b -> b -> b) -> b -> Tree a -> b foldTree fLeaf _ init (Leaf x) = fLeaf x init foldTree fLeaf fBranch init (Branch x y) = fBranch x' y' where x' = foldTree fLeaf fBranch init x y' = foldTree fLeaf fBranch init y   fringe :: Tree a -> [a] fringe t = foldTree (:) (++) [] t   treeSize :: Tree a -> Int treeSize t = foldTree (\x y -> 1 + y) (+) 0 t   treeHeight :: Tree a -> Int treeHeight t = foldTree (\x y -> 0) (\x y -> 1 + max x y) 0 t```

The key to a tree fold was realising that two functions were needed: one for leaves and one for branches. In general, I think any fold would require a function per constructor for the data structure it works on.

### Exercise 5.9

Thursday, July 26th, 2007
```makeChange :: Int -> [Int] -> [Int] makeChange _ [] = [] makeChange 0 _ = [] makeChange amt (v:vs) = n : (makeChange newamt vs) where n = amt `div` v newamt = amt `mod` v```

This was one tricky to do with higher-order functions, until I discovered scanl.

```makeChange' :: Int -> [Int] -> [Int] makeChange' amt vs = zipWith div modvs vs where modvs = scanl mod amt vs```

### Exercise 5.8

Thursday, July 26th, 2007
```encrypt :: [Char] -> [Char] encrypt cs = map encChar cs where encChar c = toEnum((fromEnum c + 1) `mod` 256)   decrypt :: [Char] -> [Char] decrypt cs = map decChar cs where decChar c = toEnum((fromEnum c + 256 - 1) `mod` 256)```

The addition of 256 ensures a proper wraparound on decryption. This exercise seemed a bit silly to me: why not have one function to do both, and allow an arbitrary key?

```caesar :: [Char] -> Int -> [Char] caesar cs k = map caesarChar cs where caesarChar c = toEnum((fromEnum c + 256 + k) `mod` 256)```

### Exercise 5.7

Thursday, July 26th, 2007

We’ve seen zip, but I don’t think unzip has been mentioned. To me it’s the obvious way to solve this problem.

```addPairsPointwise :: [(Int, Int)] -> (Int, Int) addPairsPointwise xs = (foldl (+) 0 as, foldl (+) 0 bs) where (as,bs) = unzip xs   addPairsPointwise' xs = addPairsOp xs (0,0) where addPairsOp ((x,y):xs) (a,b) = addPairsOp xs (a+x, b+y) addPairsOp [] r = r```

### Exercise 5.6

Thursday, July 26th, 2007

Perhaps it was the C++ programmer in me who immediately thought about maximum/minimum integers as the initial values for these functions.

```maxList :: [Int] -> Int maxList xs = foldl maxop (minBound::Int) xs where maxop x y = if (x < y) then y else x   maxList' xs = maxop xs minBound::Int where maxop (x:xs) m = if (x < m) then maxop xs m else maxop xs x maxop [] m = m   minList :: [Int] -> Int minList xs = foldl minop (maxBound::Int) xs where minop x y = if (x < y) then x else y   minList' xs = minop xs maxBound::Int where minop (x:xs) m = if (x > m) then minop xs m else minop xs x minop [] m = m```

### Exercise 5.5

Thursday, July 26th, 2007
```doubleEach :: [Int] -> [Int] doubleEach xs = map (\x -> x * 2) xs   doubleEach' (x:xs) = (x * 2) : doubleEach' xs doubleEach' [] = []   pairAndOne :: [Int] -> [(Int, Int)] pairAndOne xs = zip xs (map (\x -> x + 1) xs)   pairAndOne' (x:xs) = (x, x+1) : pairAndOne' xs pairAndOne' [] = []   addEachPair :: [(Int, Int)] -> [Int] addEachPair xs = map (\(a,b) -> a + b) xs   addEachPair' ((a,b):xs) = (a + b) : addEachPair' xs addEachPair' [] = []```

### Exercise 5.4

Thursday, July 26th, 2007

Assume that f2 = map.
Then:

```f1 :: [a -> a] -> a -> [a] f1 fs x = map (\f -> f x) fs```

Or in one line:

`(\fs x -> map (\f -> f x) fs) (map (*) [1,2,3,4]) 5 => [5,10,15,20]`

### Exercise 5.3

Thursday, July 26th, 2007

Note: Anonymous functions are not introduced until chapter 9! But they are an easy way to solve problems like this.

```mylength :: [a] -> Int mylength xs = foldl (\x _ -> x + 1) 0 xs```

### Exercise 5.2

Thursday, July 26th, 2007
`map map [x] = [map x]`

Therefore:

`x :: a -> b`

because x is the first argument to map. Consider the type of map:

`map :: (a -> b) -> [a] -> [b]`

This implies:

```map x :: [a] -> [b] [map x] :: [[a] -> [b]]```

And hence:

`map map :: [a -> b] -> [[a] -> [b]]`

â€“

`foldl foldl x [y] = ?`

This is a type error. See technical error 10.

â€“

`map foldl [x] = [foldl x]`

And as before:

```foldl :: (a -> b -> a) -> a -> [b] -> a x :: a -> b -> a foldl x :: a -> [b] -> a [foldl x] :: [a -> [b] -> a] map foldl :: [a -> b -> a] -> [a -> [b] -> a]```