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