2026-10-19
Minus.hs
import Control.Applicative ((<|>))
import Data.Char (isDigit)
type Parser = String -> Maybe (Int, String)
num :: Parser
num s = case span isDigit s of
("", _) -> Nothing
(ds, rest) -> Just (read ds, rest)
-- expr ::= num | expr '-' num
expr :: Parser
expr s = num s <|> minus
where
minus = do
(a, '-' : r1) <- expr s
(b, r2) <- num r1
Just (a - b, r2)
main :: IO ()
main = print (expr "10-4-3")
expr は、数と - だけからなる式を読んで、値と読み残しの文字列を返すつもりの構文解析器です。コメントの文法のとおり、引き算は左から順に計算します。expr "10-4-3" のいまの出力は Just (10,"-4-3") で、最初の数だけを読んで止まっています。本来の出力は Just (3,"") です。
Answer
Wrong
expr s = num s <|> minus
where
minus = do
(a, '-' : r1) <- expr s
Maybe の <|> は、左が Just ならそれを返し、右を評価しません。"10-4-3" では num s が Just (10,"-4-3") を返すので、minus は一度も評価されず、最初の数を読んだところで expr が終わります。先頭が数である入力では、num s は必ず成功するので、minus の出番はありません。
minus <|> num s と入れ替えても直りません。minus は最初に同じ s で expr を呼び、その expr もまず minus を評価するので、1文字も読まないまま同じ呼び出しが続き、答えが返らなくなります。expr ::= expr '-' num のように、選択肢の先頭に自分自身が来る文法を左再帰(left recursion)といい、この文法は、選択肢をどの順に並べても、そのまま関数の再帰呼び出しに写すと正しく動きません。
Right
expr s = num s >>= uncurry rest
where
rest a ('-' : r1) = do
(b, r2) <- num r1
rest (a - b) r2
rest a r = Just (a, r)
先頭の数を読んでから、- と数の組を読むたびに、それまでの値 a から引いていきます。"10-4-3" では a が10、6、3と変わり、残りが空になった時点で Just (3,"") を返します。rest は呼び出すたびに - と1文字以上の数を読むので必ず止まり、値は左から順に組み立てられるので、文法が表す左結合の計算と一致します1。
- Parsec などのパーサコンビネータのライブラリは、この形を
chainl1という関数として用意しています。項を読む構文解析器と演算子を読む構文解析器を渡すと、左結合の式を読む構文解析器を返します。