Namaran

Code daily. Without assist.

2026-09-01

Knot.hs

newtype Box = Box [Int]

data Cell = Cell [Int]

boxes :: Box
boxes = case boxes of
  Box xs -> Box (1 : xs)

cells :: Cell
cells = Cell (case cells of Cell xs -> 2 : xs)

main :: IO ()
main = do
  let Box b = boxes
      Cell c = cells
  print (take 3 b, take 3 c)

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

Answer

([1,1,1],[2,2,2]) です。どちらの定義も止まり、b と c は同じ数が無限に続くリストになります。

main の let Box b = boxes と Cell c = cells は、let の中の照合なので、b や c が使われるまで行われません。最初に評価が始まるのは、print が take 3 b を表示しようとして b を求めたときです。

boxes は、右辺の case で boxes 自身を調べています。Box が data なら、case は調べる値を、外側のコンストラクタが分かる形(弱頭部正規形、WHNF)まで評価します。boxes を求めるのに boxes が要るので止まりません。しかし Box は newtype です。newtype のコンストラクタは型を区別するためだけのもので、実行時の値は中の [Int] と同じなので、Box xs との照合は何も評価せずに成功します。xs は boxes の中身のリストそのものを指し、b は先頭の1のあとに自分自身が続く 1 : b になります。

ここで「data の case は値を評価する」と当てはめると、cells は止まらないと読めます。cells の case は確かに cells を評価しますが、その case は Cell の引数の中にあります。コンストラクタは引数を評価しないまま値になるので、cells は中身が未評価の Cell としてすぐに出来上がります。case が動くのは take が c の要素を求めたときで、その時点の cells はもう Cell の形なので照合はすぐに成功し、c は 2 : c になります。

「newtype は data より遅延的だから、boxes だけが止まる」と考えても間違えます。newtype が効くのは照合の側で、cells が止まるのは、自分自身を調べる case がコンストラクタの引数として後回しにされるからです。Box を data にすると boxes は止まらなくなり、Cell の引数を正格フィールド ![Int] にすると、今度は cells が止まらなくなります1。

  1. 正格フィールドは、コンストラクタを適用する時点でその引数を弱頭部正規形まで評価させます。Cell を作る前に case cells of ... が評価され、その case は作りかけの cells を必要とします。GHC は、値が自分自身の評価の終わりを待つこの状態を実行時に見つけると、<<loop>> という例外を投げてプログラムを終了します。