Yifu's Blog
0%

Programming in Haskell Chapter7 Exercises Solutions

Posted on Edited on In

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

用map和filter表示[f x | x <- xs, p x]

1
2
3
-- [f x | x <- xs, p x]
-- [f x | x <- xs, p x]
-- = map f (filter p xs)

定义高阶函数all, any, takeWhile, dropWhile

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
myall :: (a -> Bool) -> [a] -> Bool
myall _ [] = True
myall p (x : xs) | p x == False = False
                 | otherwise = myall p xs

-- *Main> myall (>3) [1..3]
-- False
-- *Main> myall (>3) [1..5]
-- False
-- *Main> myall (>3) [4..5]
-- True

myany :: (a -> Bool) -> [a] -> Bool
myany _ [] = False
myany p (x : xs) | p x == True = True
                 | otherwise = myany p xs

-- *Main> myany (>3) [1..5]
-- True
-- *Main> myany (>3) [1..3]
-- False


mytakeWhile :: (a -> Bool) -> [a] -> [a]
mytakeWhile _ [] = []
mytakeWhile p (x : xs) | p x == True = x : mytakeWhile p xs
                       | otherwise = []

-- *Main> mytakeWhile (<3) [1..5]
-- [1,2]
-- *Main> mytakeWhile (>3) [1..5]
-- []
-- *Main> mytakeWhile (<3) [1,2,3,1,2]
-- [1,2]

mydropWhile :: (a -> Bool) -> [a] -> [a]
mydropWhile _ [] = []
mydropWhile p (x : xs) | p x == True = mydropWhile p xs
                       | otherwise = x : xs

-- *Main> mydropWhile (<3) [1..5]
-- [3,4,5]
-- *Main> mydropWhile (>3) [1..5]
-- [1,2,3,4,5]

用foldr定义map f和filter p

1
2
3
4
5
6
mymap f = foldr (\x xs -> f x : xs) []

-- *Main> mymap (*3) [1..6]
-- [3,6,9,12,15,18]
myfilter p = foldr (\x xs -> if p x then x : xs else xs) []

用foldl定义dec2int :: [Int] -> Int

1
2
3
4
5
6
7
8
9
dec2int :: [Int] -> Int
dec2int = foldl (\x y -> x * 10 + y) 0

-- *Main> dec2int [2,3,4,5]
-- 2345
-- *Main> dec2int [2]
-- 2
-- *Main> dec2int []
-- 0

修改错误：sumsqreven = compose [sum, map (^2), filter even]

1
2
3
4
compose = foldr (.) id

sumsqreven xs = sum (compose [map (^2), filter even] xs)

curry & uncurry

1
2
3
4
5
6
7
8
9
-- 6

mycurry :: ((a, b) -> c) -> (a -> b -> c)
mycurry f = \x y -> f (x, y)


myuncurry :: (a -> b -> c) -> ((a, b) -> c)
myuncurry f = \(x, y) -> f x y

利用unfold定义chop8, map f, iterate f

1
2
3
4
5
6
7
8
9
10
11
unfold p h t x | p x = []
               | otherwise = h x : unfold p h t (t x)

int2bin' = unfold (== 0) (`mod` 2) (`div` 2)

chop8' :: [Int] -> [[Int]]
chop8' = unfold (== []) (take 8) (drop 8)

mymap' f = unfold (== []) (f.head) tail

myiterate f = unfold (\_ -> False) id f

给string transmitter程序加上奇偶校验位（parity bit）

我这里是在数据位的末端添加的，奇数个1则为1，否则为0。

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
63
64
65
66
67
68
69
-- 8

-- import Data.Char

type Bit = Int

bin2int :: [Bit] -> Int
-- bin2int bits = sum [w * b | (w, b) <- zip weights bits]
--                 where weights = iterate (*2) 1


bin2int = foldr (\x y -> x + 2 * y) 0

int2bin :: Int -> [Bit]
int2bin 0 = []
int2bin n = n `mod` 2 : int2bin (n `div` 2)

make8 :: [Bit] -> [Bit]
make8 bits = take 8 (bits ++ repeat 0)
--new
count1 :: [Bit] -> Bit
count1 = (`mod` 2) . sum
--new
addparitybits :: [Bit] -> [Bit]
addparitybits bits = bits ++ [count1 bits]
--modifyed
encode :: String -> [Bit]
encode = concat.map (addparitybits.make8.int2bin.ord)

chop9 :: [Bit] -> [[Bit]]
chop9 [] = []
chop9 bits = take 9 bits : chop9 (drop 9 bits)

--new
isvalid :: [Bit] -> Bool
isvalid bits = (count1 (take 8 bits)) == (last bits)

decode :: [Bit] -> String

decode xs | all isvalid (chop9 xs) = map (chr.bin2int.(take 8)) (chop9 xs)
          | otherwise = error "Wrong parity bit!"

transmit :: String -> String
transmit = decode.channel.encode

channel :: [Bit] -> [Bit]
channel = id


-- *Main> decode (encode "abc")
-- "abc"
-- *Main> (encode "abc")
-- [1,0,0,0,0,1,1,0,1,0,1,0,0,0,1,1,0,1,1,1,0,0,0,1,1,0,0]
-- *Main> decode [1,0,0,0,0,1,1,0,1,0,1,0,0,0,1,1,0,1,1,1,0,0,0,1,1,0,1] --> change last bit
-- "*** Exception: Wrong parity bit!
-- CallStack (from HasCallStack):
--   error, called at ch7ex.hs:149:25 in main:Main


-- 9
transmit' :: String -> String
transmit' = decode.tail.encode

-- *Main> transmit "abc"
-- "abc"
-- *Main> transmit' "abc"
-- "*** Exception: Wrong parity bit!
-- CallStack (from HasCallStack):
--   error, called at ch7ex.hs:147:25 in main:Main