Yifu's Blog
0%

Programming in Haskell Chapter5 Exercises Solutions

Posted on Edited on In

Programming in Haskell是一本入门Haskell的好书，介绍页面以及配套的slides, vedios, codes都在这里。

用List Comprehension计算1到100平方和

1
sum [x^2 | x <- [1..100]]

定义库函数replicate

1
2
3
4
5
-- > replicate 3 True
-- [True, True, True]

myreplicate :: Int -> a -> [a]
myreplicate n x = [x | _ <- [1..n]]

定义函数pyths

pyths n返回满足x^2 + y^2 == z^2的三元组(x, y, z)，其中xyz都小于等于n

1
2
3
4
5
6
7
8
-- > paths 10
-- [(3, 4, 5), (4, 3, 5), (6, 8, 10), (8, 6, 10)]

pyths   :: Int -> [(Int, Int, Int)]
pyths n = [(x,y,z) | x <- [1..n],
                     y <- [1..n],
                     z <- [1..n],
                     x^2 + y^2 == z^2]

定义完美数函数perfects

完美数的定义：一个数所有的真因子（除掉自身以外的因子）之和等于它本身。
例如：6 = 1 + 2 + 3

1
2
3
4
5
factors :: Int -> [Int]
factors x = [n | n <- [1..x-1], x `mod` n == 0]

perfects :: Int -> [Int]
perfects n = [x | x <- [1..n], x == sum (factors x)]

深入阅读：Perfect number

改写[(x, y) | x <- [1..3], y <- [1..3]]

将两层List Comprehension嵌套起来

1
concat [[(x,y)| x <- [1..3] ]| y <- [1..3]]

利用find函数重新定义positions函数

1
2
3
4
5
6
positions :: Eq a => a -> [a] -> [Int]
positions x xs = [i | (x', i) <- zip xs [0..n], x == x']
                    where n = length xs -1

find :: Eq a => a -> [(a, b)] -> [b]
find k t = [v | (k', v) <- t, k == k']

计算内积函数scalarproduct

1
2
scalarproduct :: [Int] -> [Int] -> Int
scalarproduct x y = sum [x * y | (x, y) <- zip x y]

修改书上的Caesar cipher程序，使之能处理大写字母

思路是：

  1. 用shift进行移位的时候，将大写字母、小写字母分开处理；
  2. crack计算概率的时候，把大写字母当做小写字母处理。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
let2int :: Char -> Int
let2int c = ord c - ord 'a'

-- new
let2intup :: Char -> Int
let2intup c = ord c - ord 'A'

int2let :: Int -> Char
int2let n = chr (ord 'a' + n)

-- new
int2letup :: Int -> Char
int2letup n = chr (ord 'A' + n)

-- modified
shift :: Int -> Char -> Char
shift n c | isLower c = int2let ((let2int c + n) `mod` 26)
          | isUpper c = int2letup ((let2intup c + n) `mod` 26)
          | otherwise = c

table :: [Float]
table = [8.2, 1.5, 2.8, 4.3, 12.7, 2.2,
         2.0, 6.1, 7.0, 0.2, 0.8, 4.0,
         2.4, 6.7, 7.5, 1.9, 0.1, 6.0,
         6.3, 9.1, 2.8, 1.0, 2.4, 0.2,
         2.0, 0.1]

encode :: Int -> String -> String
encode n xs = [shift n x | x <- xs]

percent :: Int -> Int -> Float
percent n m = (fromIntegral n / fromIntegral m) * 100

count :: Char -> String -> Int
count x xs = length [x' | x' <- xs, x == x']

-- lowers :: String -> Int
-- lowers xs = length [x | x <- xs, isLower x]

-- new
lowerstring :: String -> String
lowerstring xs = [if isUpper x then chr (ord x + 32) else x| x <- xs]

-- modified
freqs :: String -> [Float]
freqs xs = [percent (count x (lowerstring xs)) n | x <- ['a'..'z']]
            where n = length xs

-- chi-square
chisqr :: [Float] -> [Float] -> Float
chisqr os es = sum [(o - e)^2 / e | (o, e) <- zip os es]

rotate :: Int -> [a] -> [a]
rotate n xs = drop n xs ++ take n xs

crack :: String -> String
crack xs = encode (-factor) xs
    where
        factor = head (positions (minimum chitab) chitab)
        chitab = [chisqr (rotate n table') table | n <- [0..25]]
        table' = freqs xs

test：

1
2
3
4
5
6
7
*Main> :l ch5ex.hs 
[1 of 1] Compiling Main             ( ch5ex.hs, interpreted )
Ok, modules loaded: Main.
*Main> encode 3 "HasKELL iS FuN"
"KdvNHOO lV IxQ"
*Main> crack "KDvnhoO Lv IXQ"
"HAskelL Is FUN"