# 07.28.07

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 |

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.)

Permalink

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 |

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.

Permalink

# 07.26.07

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 |

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 |

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.

Permalink

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) |

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) |

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

Permalink

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 |

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

Permalink

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 |

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

Permalink

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' [] = [] |

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' [] = []

Permalink

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 |

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] |

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

Permalink

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 |

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

Permalink

Posted in Uncategorized at 10:12 pm by admin

Therefore:

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

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

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

This implies:

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

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

And hence:

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

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

–

This is a type error. See technical error 10.

–

map foldl [x] = [foldl x] |

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] |

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]

Permalink

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