IT練習ノート

IT関連で調べたこと(実際は嵌ったこと)を書いています。

CPS

CPSによる階乗計算

> :{
| fac 0 k = k 1
| fac n k = fac (n-1) $ \res -> k $ (*) n res
| :}
> fac 3 id
6
> fac 3 (+1) -- (1 * 2 * 3) + 1
7

手計算してみる。

  fac 3 k
= fac 2 $ \res -> k $ (*) 3 res
= fac 1 $ \res1 -> (\res -> k $ (*) 3 res) $ (*) 2 res1 
= fac 0 $ \res1 -> (\res -> k $ (*) 3 res) $ (*) 2 res1 
= (\res1 -> (\res -> k $ (*) 3 res) $ (*) 2 res1) 1
= (\res -> k $ (*) 3 res) $ (*) 2 1)
= \res -> k $ (*) 3 res $ 2
= k $ (*) 3 2) 
= k $ 6