モナドと再帰

モナドの再帰も、順を追って考えるとそれほど難しくないというお話です。

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