Namaran

Code daily. Without assist.

2026-10-19

RightRec.hs

import Data.Char (isDigit)

-- expr ::= num '-' expr | num
expr :: String -> (Int, String)
expr s = case num s of
  (n, '-' : rest) -> let (m, rest') = expr rest in (n - m, rest')
  r -> r

num :: String -> (Int, String)
num s = let (ds, rest) = span isDigit s in (read ds, rest)

main :: IO ()
main = print (fst (expr "10-4-3"))

これは何を出力するでしょうか?

Answer

9 です。

expr は先頭の数を num で読み、続きが - なら、残りの文字列を expr で読み切ってからその値を引きます。"10-4-3" では n が10で、残りの "4-3" を内側の expr が読みます。内側では 4 - 3 が先に計算されて1が返り、外側の expr は 10 - 1 の9を返します。

コメントの文法 expr ::= num '-' expr | num は、- の右側に式全体を置いているので、10-4-3 を 10-(4-3) と組み立てます。引き算は左から順に (10-4)-3 と計算する左結合(left-associative)の演算なので、普通に読めば3になるところが9になります。

再帰を右側に置いたのは、左結合のとおりの文法 expr ::= expr '-' num | num をそのまま関数にすると止まらないからです。その expr は最初に同じ文字列で自分自身を呼び、1文字も読まないまま同じ呼び出しを繰り返します。この形の文法を左再帰(left recursion)といいます。再帰を右へ移せば呼び出すたびに数を1つ読むので必ず止まりますが、組み立てる向きも右からに変わります。左結合のまま止まるようにするには、- と数の組を読むたびに、それまでの値から引いていくループとして書きます。