Programming in Haskell Chapter8 Exercises Solutions

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


这章信息量简直爆炸,书上给的东西太少了,讲的又太多了。找了一堆资料看了好久才弄明白。

结合的参考资料如下:
Chapter8讲课视频
Monadic Parsing in Haskell
“Programming In Haskell” error in sat function

按照书上的Parser定义,是没法使用do notation的,所以下面的习题全部用>>=完成。

完整的代码我放在这里


int :: Parser Int

1
2
3
4
5
6
7
8
9
10
11
12
int :: Parser Int
int = natural +++
(symbol "-" >>= \_ ->
natural >>= \x ->
return (-x))

-- *Main> parse int "123da"
-- [(123,"da")]
-- *Main> parse int "sdada"
-- []
-- *Main> parse int "-213sdada"
-- [(-213,"sdada")]

comment :: Parser ()

1
2
3
4
5
6
7
8
9
10
11
comment :: Parser ()
comment = symbol "--" >>= \_ ->
many (sat (/= '\n')) >>= \_ ->
many (char '\n') >>= \_ ->
return () -- why return ()?
-- *Main> parse comment "foo"
-- []
-- *Main> parse comment "--foo"
-- [((),"")]
-- *Main> parse comment "--foo\nbar"
-- [((),"bar")]

扩展arithmetic expressions parser

这里一个坑就是在于处理8 / 2 / 2 / 21 - 2 - 3 - 4这种情况,如果模仿+, *,的实现,很错误地容易把8 / 2 / 2 / 2parse成(8 / 2) / (2 / 2)

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
70
71
72
73
74
75
76
77
78

-- new gramma rules:
-- expr ::= term (+ expr | - expr | <E>)
-- term ::= power (* term | / term | <E>)
-- power ::= factor (^ power | <E>)
-- factor ::= (expr) | nat
-- nat ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

-- !! WRONG:
-- (symbol "-" >>= \_ ->
-- expr >>= \e ->
-- return (ex - e))

-- (symbol "/" >>= \_ ->
-- term >>= \t ->
-- return (f `div` t))


expr :: Parser Int
expr = term >>= \t ->
(symbol "+" >>= \_ ->
expr >>= \e ->
return (t + e))
+++
(many (symbol "-" >>= \_ ->
term >>= \n ->
return n) >>= \ss ->
return (foldl (-) t ss))
+++
return t

term :: Parser Int
term = power >>= \p ->
(symbol "*" >>= \_ ->
term >>= \t ->
return (p * t))
+++
(many (symbol "/" >>= \_ ->
power >>= \t ->
return t) >>= \ss ->
return (foldl div p ss))
+++
return p

power :: Parser Int
power = factor >>= \f ->
(symbol "^" >>= \_ ->
power >>= \p ->
return (f ^ p))
+++ return f

factor :: Parser Int
factor = (symbol "(" >>= \_ ->
expr >>= \e ->
symbol ")" >>= \_ ->
return e)
+++ natural

eval :: String -> Int
eval xs = case parse expr xs of
[(n, [])] -> n
[(_, out)] -> error("unused input " ++ out)
[] -> error "invalid input"

-- *Main> eval "2^3"
-- 8
-- *Main> eval "2*3 ^ 4"
-- 1296
-- *Main> eval "2 ^ 3 * 4"
-- 4096
-- *Main> eval "2 + 2^ 2"
-- 6
-- *Main> eval "2^2^2"
-- 16
-- *Main> eval "8-2-2-2"
-- 2
-- *Main> eval "16 /2/2/2"
-- 2

考虑expr ::= expr - nat | nat的parser

要注意的点在和上一题是一样的.

1
2
3
4
5
6
7
-- expr'  ::= expr' - nat | nat
-- nat ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

expr' :: Parser Int
expr' = natural >>= \n ->
many (symbol "-" >>= \_ -> natural) >>= \ns ->
return (foldl (-) n ns)