2026-11-16
Rebuild.hs
import Data.List (find)
rebuild1, rebuild2 :: Int -> Int
rebuild1 n = n `div` 2 * 2 + n `mod` 2
rebuild2 n = n `quot` 2 * 2 + n `mod` 2
main :: IO ()
main = print (find (\n -> rebuild1 n /= rebuild2 n) [3, 2 ..])
これは何を出力するでしょうか?
Answer
Output
Just (-1)
[3, 2 ..] は 3、2、1、0、-1、…と下へ続く無限リストで、find は先頭から順に調べて、条件を満たす最初の要素で止まります。リストの残りは評価されないので、どこかで2つの関数が食い違えばそこで Just が返り、食い違わなければ終わりません。答えを出すには、どの n で最初に食い違うかを、除算の2つの規則を合わせて調べることになります。
div は商を負の無限大の方向へ切り捨て、mod はその div と組になる余りで、割る数 2 と同じ符号の 0 か 1 になります。この2つは (n `div` 2) * 2 + n `mod` 2 == n を必ず満たすので、rebuild1 はどの n でも n を返します。一方 quot は商を 0 の方向へ切り捨てます。0 以上の n では div と quot は同じ商を返すので、3 から 0 までは両者が一致します。
n = -1 では、div の商は -1、quot の商は 0 です。mod は -1 を 2 で割った余りを 1 とするので、rebuild1 (-1) は -2 + 1 で -1、rebuild2 (-1) は 0 + 1 で 1 です。ここで初めて食い違い、Just (-1) が出力されます。
規則を1つだけ使うと、答えは「終わらない」になります。quot も div と同じく切り捨てると考えれば2つの関数は同じ式になり、mod の余りが C の % のように割られる数と同じ符号になると考えれば、rebuild2 (-1) も 0 + (-1) で -1 になります。そう考えた mod は、quot と組になる余り rem そのものなので、rebuild2 はすべての n で n を返し、やはり食い違いません。