Haskellでチャーチ数 - うまくいかない版

Haskellでチャーチ数

あとで説明をつける予定

はじめに

これは単純だけどうまく動かない版だ。Lispは型なしラムダ計算を背景にしているのに対して、Haskellは型付きラムダ計算を背景にしている。型推論の際に型が無限ループになってしまう。まずこの版を見てから「うまく動く版」を見ると理解しやすいだろう。

• うまく動かない版
• うまく動く版

整数との相互変換

churchNaive.hs

toInt n = n (+ 1) 0
toChurch 0 = zero
toChurch n = s . toChurch $ n - 1

ブール値と条件分岐

churchNaive.hs

false x y = y
true x y = x
_if b x y = b x y

数

churchNaive.hs

zero f x = x
s n f x = f $ n f x
one = s zero
two = s one
three = s two
four = s three
five = s four
six = s five

数の演算

churchNaive.hs

add m n f x = m f $ n f x
mul m n f = m $ n f
pre n f x = n (\g h -> h $ g f) (\u -> x) (\u -> u)

述語

churchNaive.hs

isZero n = n (\x -> false) true

型の不一致

問題ない例

churchNaive.hs

zeroToOne n = _if (isZero n) one zero

型の不一致

churchNaive.hs

zeroToOne' n = _if (isZero n) one n