Namaran

Code daily. Without assist.

2026-10-31

Race.hs

data Tramp a = Done a | More !(Tramp a)

race :: Tramp a -> Tramp a -> a
race (Done x) _ = x
race _ (Done y) = y
race (More s) (More t) = race s t

countdown :: Int -> Tramp Int
countdown 0 = Done 0
countdown n = More (countdown (n - 1))

spin :: Int -> Tramp Int
spin n = More (spin (n + 1))

main :: IO ()
main = print (race (spin 0) (countdown 3))

race は、2つの計算を1段ずつ交互に進め、先に Done に着いた方の値を返すつもりの関数です。片方が終わらない計算でも、もう片方が終われば値を返すはずです。main は、いつまでも Done に着かない spin 0 と、3段で Done 0 に着く countdown 3 を競わせるので、本来は 0 と出力されるはずです。いまは何も出力されず、メモリを使い続けて終わりません。手元では10秒で約6.7GBに達しました。

Answer

Wrong

data Tramp a = Done a | More !(Tramp a)

More のフィールドに付いた ! は、More を作るときにフィールドの値を弱頭部正規形1まで評価させます。spin 0 を評価すると More (spin 1) を作ることになり、その前に spin 1 を評価します。spin 1 もまた spin 2 を先に評価するので、spin は1段も More を返さないまま呼び出しを深くしていきます。

race は最初の節で1つ目の引数が Done かどうかを調べるために spin 0 を評価し、そこから戻ってきません。countdown 3 の側は一度も調べられないので、race の節の順を入れ替えても直りません。交互に進めるつもりの race は、More の中身が race にはがされるまで作られないことを前提にしていました。! はその前提を崩し、More を1つ作るたびに次の段まで作らせます。

Right

data Tramp a = Done a | More (Tramp a)

! を外すと、More (spin 1) は spin 1 を評価しないまま作られます。spin 0 は1段分の More をすぐ返し、race が More s と照合して s を調べたときに初めて次の段が作られます。race は両方を1段ずつ進め、3段はがして countdown の側が Done 0 になったところで 0 を返します。

  1. 弱頭部正規形(weak head normal form)は、式を外側のデータ構成子が分かるところまで評価した形です。More (spin 1) なら、中の spin 1 を評価していなくても、外側が More と分かった時点で弱頭部正規形です。