モナドの再帰も、順を追って考えるとそれほど難しくないというお話です。
string
Parsec の string について考えます。
string :: String -> Parser String string "" = return "" string (c:cs) = do char c string cs return $ c:cs
char c は、c を返すので、"<-" が使われていません。分りやすさのために、冗長に書くとこうなります。
string :: String -> Parser String string "" = return "" string (c:cs) = do a <- char c as <- string cs return $ a:as
こうしてみても、パターンマッチや do などに邪魔されて分りにくいままですが、Scheme で書けばこんな意味合いになります。
(define (string loc) (if (null? loc) '() (cons (char (car loc)) (string (cdr loc)))))
これは、再帰の基本である
- 終了条件を調べる
- car に対して仕事をする
- cdr に対して自分自身を呼び出す
に忠実です。
でも、この種のパターンは、再帰の練習問題の答えとして目にすることはあっても、実際には使いません。リストから新しいリストを生成する場合は、通常 map を使うからです。
という訳で、string はこう定義できます。
string :: String -> Parser String string = mapM char
many
Parsec の many について考えてみます。
パーサー p を 0 個表現するには、こうなります。
m0 p = return []
1 個か 0 個を表現するには、こうなります。
m1 p = do a1 <- p return [a1] <|> return []
2 個か 1 個か 0 個を表現するには、こうなる気がします。
--これは間違い m2 p = do a1 <- p a2 <- p return [a1,a2] <|> do a1 <- p return [a1] <|> return []
しかし、<|> は消費した入力を戻せないので、実際にはうまく行きません。意図通りに動かすためには、共通項をくくり出す必要があります。
m2 p = do a1 <- p as <- do a2 <- p return [a2] <|> return [] return $ a1:as <|> return []
この真ん中の部分は、m1 に他なりません。
m2 p = do a1 <- p as <- m1 p return $ a1:as <|> return []
という訳で、一般化するとこうなります。
many p = do a <- p as <- many p return $ a:as <|> return []
many1
次に many1 を考えます。
1 個を表現するには、こうなります。
n1 p = do a1 <- p return [a1]
2 個か 1 個を表現するには、こうなる気がします。
--これは間違い n2 p = do a1 <- p a2 <- p return [a1,a2] <|> do a1 <- p return [a1]
しかし、<|> は消費した入力を戻せないので、共通項をくくり出す必要があります。
n2 p = do a1 <- p as <- do a2 <- p return [a2] <|> return [] return $ a1:as
中央部分は n1 ではなく、m1 であると分ります。
n2 p = do a1 <- p as <- m1 p return $ a1:as
という訳で、一般化するとこうなります。
many1 p = do a <- p as <- many p return $ a:as
many と many1
many と many1 を見比べると、many の中は many1 と同じ形をしているのが分ります。
many p = do a <- p as <- many p return $ a:as <|> return [] many1 p = do a <- p as <- many p return $ a:as
よって、many はこう定義できます。
many p = many1 p <|> return []
最終形は、こうです。
many p = many1 p <|> return [] many1 p = do a <- p as <- many p return $ a:as
