目的

俺が忘れない為、忘れた時の思い出す材料としての概要メモです。

自然数

足し算は次の規則うで定義される。

どんな自然数 n と m の組についても

n + m = m + n

が成り立つ

補足: 足し算は左右逆になっても結果は変わらないよって事

どんな自然数nについても

n + 0 = 0 + n = n

が成り立つ。

補足: nに0を足してもnのままだよって事

どんな自然数mとnについても

m + s(n) = s(m + n)

が成り立つよって事。
この規則は帰納的な規則で、再起を使って組み立てられている。

sって関数の適用回数によって、連なる数を表現している
10進数での例:

s(0) = 1

s(s(s(0))) = 3

3 + s(2) = s(2 + 3) = 6

こういう感じ

ちなみにこの自然数の表現はλ計算での自然数の表現方法と凄く似ている

λ計算は、アロンゾ・チャーチ（AlonzoChurch、19031995）という名のアメリカの数学者によって、停止性問題のいくつかある証明のうち最初期のものの1つの中で設計された。

Haskell, Scala, Lispといった関数型プログラミング言語は、純粋なλ計算を別の構文で書いたもの。

λ計算の式はλ式と呼ぶ

純粋なλ計算では、全てが関数です。
関数の定義と適用しかできないので、関数以外の値はありません(例: 0, 1, 2や'h'や'hello world'等も一切ありません)。

何かデータ構造等がほしければλ計算を使って全てを作れます。

λ計算の関数は、「λパラメータ.本体」のように書く。
この式はパラメータが1つだけの関数を定義します。

関数の本体に出てくる名前で、パラメータ名に一致するのもの、識別子参照といいます。

例:

λa.a

この式のλa.aのλと.の間に挟まっている文字がパラメータで、.の後に登場したaが識別子参照をしている

引数の前に関数の値を書くと、引数への関数の適用になります。
xyのように書いて、関数xを値yに適用します。

例

x y

xが関数で、yが引数です

λ式はレキシカルスコープです。

λ式で自然数を表現する方法はいくつかあって、その中の1つ、チャーチ数を紹介する。

// fを0回適用したから 0
λx = x

// fを1回適用したから 1
λx = f x

// fを2回適用したから 2
λx = f (f x)

// fを3回適用したから 3
λx = f (f (f x))

これは、xにfを適用した回数で自然数を表現している。
これはこの記事の冒頭に登場する自然数の再起の式と凄く似ていると思う。

こういう式があったとする

λx.p (x y)

pとyって誰？ってなると思います。
このpとyが自由変数です。