Namaran

Code daily. Without assist.

2026-10-31

Parity.hs

data Step a = Done a | Next (Step a)

run :: Int -> Step a -> (Int, a)
run k (Done x) = (k, x)
run k (Next s) = run (k + 1) s

isEven :: Int -> Step Bool
isEven 0 = Done True
isEven n = Next (isOdd (n - 1))

isOdd :: Int -> Step Bool
isOdd 0 = Done False
isOdd n = Next (isEven (n - 1))

main :: IO ()
main = print (run 0 (isOdd 5))

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

Answer

(5,True) です。

isOdd と isEven は相手を直接呼ばず、次にする呼び出しを Next に包んだ値を返します。run はその Next を1つはがすたびに k を1増やし、中の呼び出しを進めます。

isOdd 5 から始めると、isEven 4、isOdd 3、isEven 2、isOdd 1、isEven 0 と、n が0になるまで5回 Next を経由します。isEven 0 は Done True を返すので、run は k が5のところで止まり、(5,True) を返します。数えるのは Next の数で、関数を呼んだ回数(6回)ではありません。

Next の中の呼び出しは、run が Next s と照合して s を調べるときに初めて評価されます。isOdd は Next を返した時点で戻っているので、isOdd と isEven の呼び出しが互いの中に積み重なることはありません。