Yifu's Blog
0%

Programming in Haskell Chapter8 Exercises Solutions

Posted on Edited on In

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 / 2，1 - 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)