The Haskell School of Expression: Exercises

data Expr = C Float | V String | Expr :+ Expr | Expr :- Expr | Expr :* Expr | Expr :/ Expr | Let String Expr Expr deriving Show evaluate :: Expr -> [(String, Float)] -> Float evaluate (C x) _ = x evaluate (V x) vars = lookup x vars where lookup […]

It’s not clear what the action of zip should be on trees with data only at the leaves: if the two trees are mismatched, what should the zipped tree look like? So it is easier to define zipWith on an InternalTree, and of course to define zip in terms of zipWith. zipWithInternalTree :: (a -> […]

foldrTree :: (a -> b -> b) -> b -> InternalTree a -> b foldrTree f z ILeaf = z foldrTree f z (IBranch a x y) = foldrTree f (f a (foldrTree f z y)) x foldlTree :: (a -> b -> a) -> a -> InternalTree b -> a foldlTree f z 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 […]

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’ […]

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

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

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) = […]

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) […]

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’ […]