Yifu's Blog
0%

Programming in Haskell Chapter6 Exercises Solutions

Posted on In

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

这一章节就是在讲递归，所以下面的定义都是默认用递归定义。

定义幂函数

1
2
3
4
5
6
7
8
9
10
mypow :: Int -> Int -> Int
mypow _ 0 = 1
mypow x n = x * mypow x (n-1)

-- *Main> mypow 2 3
-- 8
-- *Main> mypow 3 0
-- 1
-- *Main> mypow 3 1
-- 3

解释length, drop, init的递归求值过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

-- length [1, 2, 3]
-- = 1 + length [2, 3]
-- = 1 + (1 + length [3])
-- = 1 + (1 + (1 + length []))
-- = 3

-- drop 3 [1..5]
-- = drop 2 [2..5]
-- = drop 1 [3..5]
-- = drop 0 [4, 5]
-- = [4, 5]

-- init [1..3]
-- = 1 : init [2, 3]
-- = 1 : 2 : init [3]
-- = 1 : 2 : []
-- = [1, 2]

定义以下库函数

and
1
2
3
4
5
6
7
8
9
10
11
myand :: [Bool] -> Bool
myand [] = True
myand (n : ns) | n == False = False
               | otherwise = myand ns

-- *Main> myand [True, True]
-- True
-- *Main> myand [True, False]
-- False
-- *Main> myand []
-- True
concat
1
2
3
4
5
6
7
8
9
10
11
myconcat :: [[a]] -> [a]
myconcat [] = []
myconcat [[a]] = [a]
myconcat (n : ns) = n ++ myconcat ns

-- *Main> myconcat []
-- []
-- *Main> myconcat [[1,2,3]]
-- [1,2,3]
-- *Main> myconcat [[1,2,3],[3,4,5],[2,7]]
-- [1,2,3,3,4,5,2,7]
replicate
1
2
3
4
5
6
7
8
9
10
11
12
myreplicate :: Int -> a -> [a]
myreplicate 0 _ = []
myreplicate n a = a : myreplicate (n - 1) a

-- *Main> myreplicate 0 True
-- []
-- *Main> myreplicate 1 True
-- [True]
-- *Main> myreplicate 3 'c'
-- "ccc"
-- *Main> myreplicate 3 "hs"
-- ["hs","hs","hs"]
(!!)
1
2
3
4
5
6
7
8
9
10
mynth :: [a] -> Int -> a
mynth (x : xs) 0 = x
mynth (x : xs) n = mynth xs (n - 1)

-- 其实这里如果n大于长度应该要抛出一个异常，目前还没学到，先放着

-- *Main> mynth [1..3] 0
-- 1
-- *Main> mynth [1..3] 2
-- 3
elem
1
2
3
4
5
6
7
8
9
10
11
12
myelem :: Eq a => a -> [a] -> Bool
myelem x [] = False
myelem x (n : ns) | x == n = True
                  | otherwise = myelem x ns


-- *Main> myelem 0 []
-- False
-- *Main> myelem 0 [1..3]
-- False
-- *Main> myelem 3 [1..3]
-- True

定义merge函数

merge: 将两个有序list合并成一个有序list

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
merge :: Ord a => [a] -> [a] -> [a]
merge [] [] = []
merge a [] = a
merge [] a = a
merge (n:ns) (x:xs) | x >= n = n : merge ns (x:xs)
                    | x < n = x : merge (n:ns) xs

-- *Main> merge [1,2,3,4,5] [2,3,5,6,7]
-- [1,2,2,3,3,4,5,5,6,7]
-- *Main> merge [2,5,6] [1,3,4]
-- [1,2,3,4,5,6]
-- *Main> merge [1,3,4] []
-- [1,3,4]
-- *Main> merge [] []
-- []

利用merge定义归并排序msort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
halve :: [a] -> ([a], [a])
halve xs = let hl = (length xs) `div` 2 in
            (take hl xs, drop hl xs)

msort :: Ord a => [a] -> [a]
msort [] = []
msort [a] = [a]
msort xs = merge (msort (fst (halve xs))) (msort (snd (halve xs)))

-- *Main> msort []
-- []
-- *Main> msort [3,1,2,4]
-- [1,2,3,4]
-- *Main> msort [7,3,4,2,4,5,6,12,33,4,22,2]
-- [2,2,3,4,4,4,5,6,7,12,22,33]

定义sum, take, last

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

mysum :: Num a => [a] -> a
mysum [] = 0
mysum (x : xs) = x + mysum xs

-- *Main> mysum []
-- 0
-- *Main> mysum [1..5]
-- 15
-- *Main> mysum [3.6,7.6,5.77]
-- 16.97

mytake :: Int -> [a] -> [a]
mytake 0 _ = []
mytake _ [] = []
mytake n (x : xs) = x : mytake (n - 1) xs


-- *Main> mytake 0 [1..5]
-- []
-- *Main> mytake 3 [1..5]
-- [1,2,3]
-- *Main> mytake 7 [1..5]
-- [1,2,3,4,5]
-- *Main> mytake 7 []
-- []


mylast :: [a] -> a
mylast [x] = x
mylast (x : xs) = mylast xs


-- *Main> mylast [1..3]
-- 3
-- *Main> mylast [5]
-- 5