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

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]

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

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