Namaran

Code daily. Without assist.

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。

  1. Parsec などのパーサコンビネータのライブラリは、この形を chainl1 という関数として用意しています。項を読む構文解析器と演算子を読む構文解析器を渡すと、左結合の式を読む構文解析器を返します。