Haskell函数式编程入门（第2版）练习答案（仅供参考）

Posted on Edited on In Disqus:

这本书还是挺不错的，至少对于入门而言足够详尽。大概从第八章开始就会发现学习曲线的陡峭。

电子书购买链接：第1卷，第2卷。

尽量不坑，争取完结。

我是跟着书从零学起，网上也没什么可供参考的练习答案，因此难免会有写得不正确或者不优雅的地方，欢迎指出。

书中的代码仓库：Github （仓库的名字有一个致命的缺陷，作者肯定很后悔吧，但也没法改了）

更新：咕了，我所需要的不仅仅是一门语言。

更新：在学完了 Coursera 上 UW 开的 programming language (Part 1 & 2 & 3) 之后，我又回来了。

Chapter 3

3.3.1

1
2
3
4
5
6
7
8
9
import Prelude hiding ((/=), (==), not, and, or, (%%), (||))

nor :: Bool -> Bool -> Bool
nor False False = True
nor _ _ = False

xnor, xor :: Bool -> Bool -> Bool
xnor a b = nor (nor a (nor a b)) (nor b (nor a b))
xor a b = nor t t where t = xnor a b

Chapter 5

5.2.1

1
2
3
delete :: Eq a => a -> [a] -> [a]
delete a [] = []
delete a (x : xs) = let t = delete a xs in if x == a then t else x : t

5.2.2

1
2
3
4
drop' :: Int -> [a] -> [a]
drop' n xs | n <= 0 = xs
drop' _ [] = []
drop' n (_ : xs) = drop' (n - 1) xs

5.7.1

1
2
3
4
5
6
7
8
9
10
  convert 17
= "X" ++ convert 7
= "X" ++ ("V" ++ convert 2)
= "X" ++ ("V" ++ ("I" ++ convert 1))
= "X" ++ ("V" ++ ("I" ++ ("I" ++ convert 0)))
= "X" ++ ("V" ++ ("I" ++ ("I" ++ "")))
= "X" ++ ("V" ++ ("I" ++ "I"))
= "X" ++ ("V" ++ "II")
= "X" ++ "VII"
= "XVII"

5.7.2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
romeNotation :: [String]
romeNotation = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"]

romeAmount :: [Int]
romeAmount = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]

pair :: [(Int, String)]
pair = zip romeAmount romeNotation

getFst :: String -> (Int, String)
getFst s = head $ filter (\x -> isPrefixOf (snd x) s) pair

convert :: String -> Int
convert "" = 0
convert s = let p = getFst s in fst p + convert (drop (length $ snd p) s)

5.7.3

1
2
3
4
convert, convert' :: Int -> String
convert x = if x == 0 then "0" else convert' x
convert' 0 = ""
convert' x = convert' (div x 2) ++ show (mod x 2)

5.8.1

复杂度是 \(\mathcal{O}(\log n+m)\)，其中 \(n\) 是列表元素数量，\(m\) 是匹配的元素数量。显然地，这是复杂度的下界。

1
2
3
4
5
6
search :: Ord a => a -> [a] -> [a]
search _ [] = []
search a xs | m < a = search a behind
            | m > a = search a front
            | otherwise = search a front ++ [m] ++ search a behind
            where (front, m : behind) = splitAt (length xs `div` 2) xs

5.10.1

C/Java 通常是 in-place 的排序，由于直接修改了数组元素，所以是 mutable 的，而函数式实现是 immutable 的。

5.10.2

Data.List.sort 的链接 https://hackage.haskell.org/package/base-4.12.0.0/docs/Data-List.html#v:sort，源代码点击右侧 Source。

zerol: 当时看了 Scala 中 sort 的实现，是用命令式实现的，本以为能看到优雅的函数式实现，结果还是为了效率妥协。而 Haskell 不一样，因为它根本就没有妥协的余地。

5.13.1

1
2
3
4
5
6
7
8
9
merge :: Ord a => [a] -> [a] -> [a]
merge xs [] = xs
merge [] ys = ys
merge (x : xs) (y : ys) | x < y = x : merge xs (y : ys)
                        | x > y = y : merge (x : xs) ys
                        | otherwise = x : merge xs ys

ham :: [Integer]
ham = 1 : merge (map (*2) ham) (merge (map (*3) ham) (map (*5) ham))

如果把最后一行改成 ham = merge [1] ... 那么会跑不出结果，原因在于永远无法获取列表中的第一个元素。

Chapter 6

6.1.1

1
2
3
4
series :: Int -> Int -> [Double]
series a n = [ 1 / (fromIntegral a ^ (2 * k + 1) * (2 * fromIntegral k + 1)) * (-1) ^ k | k <- [0 .. n] ]

pi' = ((sum $ series 2 1000) + (sum $ series 3 1000)) * 4

没有数字相关的隐式类型转换真的很不习惯。

6.2.1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
sieve :: Integral a => [a] -> [a]
sieve [] = []
sieve (p : xs) = p : sieve [ x | x <- xs, x `mod` p /= 0 ]

getExp :: Integer -> Integer -> Integer
getExp n k | mod n k /= 0 = 0
           | otherwise = 1 + getExp (div n k) k


f :: Integer -> Integer -> [(Integer, Integer)]
f n k | t == 0 = []
      | otherwise = [(k, t)]
      where t = getExp n k

primeFactors :: Integer -> [(Integer, Integer)]
primeFactors 1 = []
primeFactors n = concatMap (f n) $ takeWhile (<=n) $ sieve [2..]

6.4.1

1
2
3
choose :: Int -> [a] -> [[a]]
choose 0 _ = [[]]
choose n xs = [ y : ys | xs' @ (y : _) <- tails xs, ys <- choose (n - 1) xs' ]

6.7.1

1
2
3
4
5
6
7
8
9
-- 省略了 Introduction_to_Haskell_2ed_source/C06/ShortestPath.hs 中的内容
import Data.List
import Data.Maybe

nameidx :: Name -> [Name] -> Int
nameidx n ns  = fromJust $ elemIndex n ns

path' :: [[Distance]] -> [Name] -> Name -> Name -> Weight
path' dis ns s t = path dis ns !! (nameidx s ns) !! (nameidx t ns)

6.7.2

1
2
3
4
5
steps' :: Int -> RouteMap -> RouteMap
steps' 1 route = route
steps' n route | even n = step t t
               | odd n = step route (step t t)
               where t = steps' (n `div` 2) route

这里的 steps' n route 等价于 steps (n - 1) route。

Chapter 7

7.2.3 & 7.2.4

1
2
3
4
5
6
7
8
9
interLeave :: [a] -> [a] -> [a]
interLeave (x : xs) ys = x : interLeave ys xs
-- wrong !
-- interLeave (x : xs) (y : ys) = x : y : interLeave xs ys

interLeaveLists :: [[a]] -> [a]
interLeaveLists = foldr interLeave []

rationalNumbers = interLeaveLists [[(x, y) | y <- [1..]] | x <- [1..]]

代码中给出了符合 7.2.3 要求但是无法在 7.2.4 中使用的 interLeave 的定义，原因在于为了取出列表的第一个元素还要取出第二个元素，而第二个元素依旧来自两个无穷列表的 interLeave。

因为是无穷列表，所以 foldr 的第二个参数永远都不会用到。

为什么不能使用 foldl 呢？考虑 foldl 的定义，在计算过程中一直都是 foldl f v xs 的形式，只是 v 有所更新，而只有在 xs 为空的时候才能摆脱 foldl，期间始终取出列表的第一个元素。

最后的结果是否真的遍历了所有正整数对（不重不漏）呢？简单感受一下：观察取出元组的第一个元素，形如 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5。会有一半取到 1，另一半大于 1，而大于 1 的部分会有一半取到 2，另一半大于 2。也就是第 \(k\) 个元素来自于第 "\(k\) 的二进制表示的末尾 \(0\) 的数量 \(+ 1\)" 个列表，而每个列表中的元素会依次被选取，因此每一个确定的元素都会在确定位置被取到。

7.2.5

1
2
3
4
5
6
removeOne :: Eq a => a -> [a] -> [a]
removeOne v xs | elem v xs = xs
               | otherwise = v : xs

removeDup :: Eq a => [a] -> [a]
removeDup xs = foldr removeOne [] xs

7.4.1

为方便起见以及和书中一致，Foldable t => t a 简化为 [a]。

解决问题的关键在于，如果类型 a -> b -> c 被看做 x -> y，那么有 x = a 和 y = b -> c。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
foldl :: (b -> a -> b) -> b -> [a] -> b
foldr :: (a -> b -> b) -> b -> [a] -> b
foldl const :: b -> [a] -> b

-- const 的类型是 a -> b -> a，foldr 的第一个参数的类型要求是 a -> b -> b，导致 a 和 b 的类型必须相同
foldr const :: a -> [a] -> a
-------------------------------
map :: (a -> b) -> [a] -> [b]

-- 令 a = a' -> b', b = [a] -> [b] 并代入 [a] -> [b]
map map :: [a' -> b'] -> [[a] -> [b]]

-- 看作 (a -> b) -> ([a] -> [b]) 复合 ([a] -> [b]) -> ([[a]] -> [[b]])
map.map :: (a -> b) -> [[a]] -> [[b]]
-------------------------------
(.) :: (b -> c) -> (a -> b) -> a -> c

-- 令 b = b' -> c', c = (a' -> b') -> a' -> c' 并代入 (a -> b) -> a -> c
(.) (.) :: (a -> b' -> c') -> a -> (a' -> b') -> a' -> c'

-- 看作 (b -> c) -> ((a -> b) -> (a -> c)) 复合 ((a -> b) -> (a -> c)) -> ((a' -> a -> b) -> a' -> (a -> c))
(.).(.) :: (b -> c) -> (a' -> a -> b) -> a' -> a -> c

Chapter 8

8.7.1

1
2
3
brace :: Int -> [String]
brace 0 = [""]
brace n = ["(" ++ x ++ ")" ++ y | c <- [0 .. n - 1], x <- brace c, y <- brace (n - 1 - c)]

8.8.1

1
2
3
4
5
6
7
8
9
10
11
12
-- 省略了 Introduction_to_Haskell_2ed_source/C08/Huffman.hs 中的内容
import Data.List (sort, group, find)

freq :: String -> [(Char, Double)]
freq s = map (\x -> (head x, (fromIntegral $ length x) / (fromIntegral $ length s))) $ (group . sort) s

encode :: [(Char, [Char])] -> Char -> String
encode x c | Just s <- v = snd s
  where v = find ((== c) . fst) x
 
compress :: String -> String
compress s = concatMap (encode (huffman $ freq s)) s

8.8.2 (skip)

姑且跳过

8.9.* (skip)

Chapter 9

9.2.3

1
2
3
4
5
6
7
8
data Tree a = Leaf a | Branch (Tree (a, a)) deriving Show

instance Functor Tree where
  fmap f (Leaf a) = Leaf (f a)
  fmap f (Branch t) = Branch (fmap (\(x, y) -> (f x, f y)) t)
  
-- test code
tree = fmap (+1) (Branch (Branch (Leaf ((1, 2), (3, 4)))))

和书中之前提到的树相比，这里的树必须是完全二叉树。

9.2.8

1
liftA2 (:)

zerol: liftA2 是把二元函数转化为 actions（源代码注释这么说的），我的理解是，先做一件事，然后在这件事的基础上再做一件事，然后把它们组合起来。这么看的话，确实也更好地理解了 <* 和 *> 为什么不是单纯地忽略一侧的参数。

9.4.8 (skip)

没看懂题目2333