07.28.07

Exercise 7.2

Posted in Uncategorized at 9:43 pm by admin

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

Posted in Uncategorized at 9:37 pm by admin

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.

07.26.07

Exercise 5.9

Posted in Uncategorized at 11:20 pm by admin

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

See technical error 12 for a note about this exercise.

Exercise 5.8

Posted in Uncategorized at 11:18 pm by admin

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

Posted in Uncategorized at 11:08 pm by admin

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

Posted in Uncategorized at 11:04 pm by admin

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

Posted in Uncategorized at 10:58 pm by admin

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

Posted in Uncategorized at 10:47 pm by admin

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

Posted in Uncategorized at 10:33 pm by admin

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

Posted in Uncategorized at 10:12 pm by admin

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]

« Previous Page« Previous entries « Previous Page · Next Page » Next entries »Next Page »