對(duì)自然數(shù)的理解，是隨著自己的成長(zhǎng)而不斷深入的。在小學(xué)的時(shí)候覺(jué)得很自然就理解了，很自然就用起來(lái)了，加、減、乘和整除很自然就學(xué)會(huì)了，感覺(jué)沒(méi)有什么障礙。到了初中的某一天，突然想到一個(gè)問(wèn)題：1 + 1為什么就是等于2呢？沒(méi)有理由的就指定了是2，沒(méi)有推導(dǎo)和證明的過(guò)程，感覺(jué)很不自然。于是自己思考了好幾個(gè)月，覺(jué)得似乎想通了，寫(xiě)了一篇文章，然后被一些同學(xué)嘲笑了。現(xiàn)在也想不起來(lái)當(dāng)時(shí)寫(xiě)的是什么了，那篇文章也不知道遺失到哪里去了，不過(guò)應(yīng)該還是沒(méi)有寫(xiě)清楚究竟為什么1 + 1等于2，要不然我是不會(huì)忘記寫(xiě)的是什么的。于是這個(gè)令人疑惑的問(wèn)題一直困擾著我，一直到參加工作，也依然時(shí)不時(shí)會(huì)惦記著這個(gè)問(wèn)題。

直到我學(xué)習(xí)了Haskell，看到一篇關(guān)于自然數(shù)的表示文章，用Haskell清晰的定義了自然數(shù)，定義了自然數(shù)的加法和乘法。我終于明白了1 + 1為什么就是等于2，這個(gè)從自然數(shù)的定義和加法的定義很自然就可以推導(dǎo)得到了，證明起來(lái)很容易。在這之后，又看了皮亞諾公理的自然數(shù)定義，對(duì)自然數(shù)的定義更加清楚了。在這之前，我聽(tīng)說(shuō)過(guò)皮亞諾公理，但是并不感興趣，還感受不到自然數(shù)公理化的意義，所以并沒(méi)有去看。

大概兩個(gè)月前，我收到了劉新宇的新書(shū)《同構(gòu)--編程中的數(shù)學(xué)》，看到了這本書(shū)中對(duì)自然數(shù)的論述，然后又重溫了丘奇數(shù)的概念。覺(jué)得可以寫(xiě)點(diǎn)關(guān)于自然數(shù)的東西了。這是一個(gè)系列，有兩篇文章：第一篇講自然數(shù)和丘奇數(shù)的基礎(chǔ)概念和構(gòu)造，以及在其上的基本運(yùn)算，第二篇講自然數(shù)的變換，結(jié)合F-Alg來(lái)講如何消除自然數(shù)的結(jié)構(gòu)得到其他的類型的值。

好了，讓我們從一無(wú)所知的狀態(tài)來(lái)開(kāi)始了解什么是自然數(shù)吧。我們最早了解自然數(shù)是從數(shù)數(shù)開(kāi)始的，當(dāng)我們不知道桌上一堆東西有多少個(gè)時(shí)，最簡(jiǎn)單的辦法就是數(shù)一數(shù)有多少個(gè)。數(shù)一下手指頭是1 個(gè)，數(shù)兩下手指頭是2 個(gè)，數(shù)三下手指頭是3 個(gè)，這樣一直數(shù)下去，直到數(shù)完了這堆東西。于是我們就得到了一系列的數(shù)：1, 2, 3, ...，這些數(shù)和數(shù)手指頭的次數(shù)的對(duì)應(yīng)關(guān)系如下。

1 ： 數(shù)一下手指頭

當(dāng)桌上沒(méi)有東西的時(shí)候，我們就不用數(shù)手指頭了，因?yàn)槭裁炊紱](méi)有，所以什么也不用做。這個(gè)時(shí)候我們用0 個(gè)來(lái)表示桌上東西的數(shù)量。于是有下面這個(gè)新的數(shù)和數(shù)手指頭的次數(shù)的對(duì)應(yīng)關(guān)系。

0 ： 什么也不做

因?yàn)槲覀円粺o(wú)所知，就像幼兒園的小朋友一樣，還弄不明白兩下、三下是怎么來(lái)的，是什么意思。我們?cè)賮?lái)看一遍我們數(shù)數(shù)的過(guò)程，一開(kāi)始是什么也不做，然后將一個(gè)東西擺到桌子的另一邊，做一次數(shù)手指頭的動(dòng)作，再將一個(gè)東西擺到桌子的另一邊，再做一次數(shù)手指頭的動(dòng)作，這樣每將一個(gè)東西擺到桌子的另一邊，我們都接著做一次數(shù)手指頭的動(dòng)作，直到把桌子上的東西數(shù)完。于是我們就得到一個(gè)數(shù)手指頭的動(dòng)作的序列，這個(gè)數(shù)手指頭動(dòng)作的序列的次數(shù)就是東西的個(gè)數(shù)。因此有下面的數(shù)和數(shù)手指頭的動(dòng)作序列的對(duì)應(yīng)關(guān)系。

0 ： 什么也不做

我們把上面的什么也不做用O 來(lái)表示，把數(shù)手指頭這個(gè)動(dòng)作用S 來(lái)表示，于是上面的數(shù)和數(shù)手指頭的動(dòng)作序列的對(duì)應(yīng)關(guān)系就變成了下面這樣。

0 ： O

我們可以這樣認(rèn)為，最開(kāi)始存在一個(gè)自然數(shù)O，然后我們開(kāi)始做一個(gè)數(shù)手指頭的動(dòng)作，就得到一個(gè)新的自然數(shù)S O，再做一個(gè)數(shù)手指頭的動(dòng)作，又得到一個(gè)新的自然數(shù)S (S O)。再繼續(xù)下去，我們就得到了自然數(shù)的序列：O, S O, S (S O), S (S (S O), ...。我們用N 來(lái)表示所有自然數(shù)的集合，也就是自然數(shù)類型，這樣每做一次數(shù)手指頭的動(dòng)作，我們就得到了一個(gè)自然數(shù)n ∈ N 的后繼S n，這也是一個(gè)自然數(shù)。我們可以使用Haskell來(lái)定義自然數(shù)：

data

于是我們就得到了所有的自然數(shù)。我們可以通過(guò)皮亞諾公理來(lái)驗(yàn)證這一點(diǎn)，皮亞諾公理的表述如下：

1. 0 是自然數(shù)。

2. 每個(gè)自然數(shù)都有它的下一個(gè)自然數(shù)，稱為它的后繼。

3. 0 不是任何自然數(shù)的后繼。

4. 不同的自然數(shù)有不同的后繼數(shù)。

5. 如果自然數(shù)的某個(gè)子集包含 0，并且其中每個(gè)元素都有后繼元素。那么這個(gè)子集就是全體自然數(shù)。

這里得到自然數(shù)的后繼用動(dòng)作S 來(lái)表示，也可把S 看成是自然數(shù)集合上的自函數(shù)。皮亞諾公理確保了0（也就是我們前面用O來(lái)表示的數(shù)）是第一個(gè)自然數(shù)，然后通過(guò)不停的獲取自然數(shù)的后繼，我們就得到了所有的自然數(shù)。其中皮亞諾公理的第4條確保了S 是一個(gè)單射，第5條確保了S 是一個(gè)滿射，因此S 是一個(gè)自同構(gòu)（這一點(diǎn)在下一篇中會(huì)用到）。

另外第5條公理還有如下的等價(jià)描述：

任意關(guān)于自然數(shù)的命題，如果證明了它對(duì)自然數(shù) 0 是對(duì)的，又假定它對(duì)自然數(shù) n 為真時(shí)，可以證明它對(duì) n的后繼n′ 也真，那么命題對(duì)所有自然數(shù)都真。

這保證了數(shù)學(xué)歸納法的正確性，使得自然數(shù)上可以有歸納函數(shù)。因此也叫歸納公理。

我們有了嚴(yán)格定義的自然數(shù)，現(xiàn)在可以在這個(gè)定義的基礎(chǔ)上定義加法、乘法和冪運(yùn)算了。我們使用Haskell來(lái)定義這些運(yùn)算：

-- | 先定義幾個(gè)基本函數(shù)，用于給后面的運(yùn)算定義使用

自然數(shù)上的歸納函數(shù)的定義是對(duì)于自然數(shù)n ，對(duì)其進(jìn)行歸納的初始值是z ，每一個(gè)歸納步調(diào)用函數(shù)step 。自然數(shù)n 是由幾個(gè)S 構(gòu)造的，我們就以z 為參數(shù)遞歸調(diào)用幾次step 函數(shù)。比如當(dāng)自然數(shù)n 的值是S (S (S O)時(shí)，這是由3 個(gè)S 構(gòu)造的，于是我們就遞歸調(diào)用3 次step 函數(shù)，于是結(jié)果是step (step (step z)) 。

對(duì)于加法，我們是這樣定義的，給定一個(gè)自然數(shù)m，加上一個(gè)值為S (S O)的自然數(shù)n 時(shí)，其結(jié)果等于值為S (S m)的自然數(shù)。用歸納函數(shù)來(lái)定義就相當(dāng)于初始值z(mì) 是m ，step 是S 也就是succN ，我們對(duì)加數(shù)n 做歸納法，也就是自然數(shù)n 中由幾個(gè)S 構(gòu)造的，我們就遞歸調(diào)用幾步S 。于是有了結(jié)果的值是S (S m)。

當(dāng)m 的值是S O 也就是1 ，n 的值也是S O 即1 時(shí)，我們有(S O) + (S O) = S (S O)，根據(jù)上面的數(shù)的對(duì)應(yīng)關(guān)系，我們有1 + 1 = 2 。完成了證明，解決了我多年來(lái)的疑問(wèn)。

對(duì)于乘法，兩個(gè)自然數(shù)m 和n 相乘，就相當(dāng)于把n 個(gè)m 加起來(lái)。用歸納函數(shù)來(lái)定義就相當(dāng)于初始值是O，step 是(m +) 也就是plus m ，我們對(duì)乘數(shù)n 做歸納法。于是乘以一個(gè)值為S (S O)的自然數(shù)，我們就遞歸調(diào)用兩步遞歸步plus m，于是得到結(jié)果值是plus m (plus m O)，就是m + m。

對(duì)于冪運(yùn)算，則和乘法類似，自然數(shù)m 的n 次冪的值就等于把n 個(gè)m 乘起來(lái)。用歸納函數(shù)來(lái)定義就相當(dāng)于初始值是S O，step 是(m *) 也就是mult m ，我們對(duì)冪數(shù)n 做歸納法。于是求m 的一個(gè)值為S (S O) 的n 次冪的自然數(shù)的值，我們就遞歸調(diào)用兩步遞歸步plus m，于是得到結(jié)果值是mult m (mult m (S O))，就是m * m。

減法的定義比較復(fù)雜，因?yàn)樽匀粩?shù)沒(méi)有負(fù)數(shù)，因此需要比較兩個(gè)數(shù)的大小來(lái)實(shí)現(xiàn)減法，這個(gè)放到后面一起來(lái)定義。

用皮亞諾公理來(lái)定義的自然數(shù)只是自然數(shù)表示的一種形式，我們可以用其他同構(gòu)的形式來(lái)定義和表示自然數(shù)。接下來(lái)我們將使用列表和函數(shù)來(lái)表示自然數(shù)。

• 用列表表示自然數(shù)

列表是包含了同類型元素的一種數(shù)據(jù)類型，多個(gè)同類型的數(shù)據(jù)列在一起，就組成了列表。當(dāng)列表內(nèi)的元素的類型是 () 時(shí)，列表就只剩下長(zhǎng)度信息了，我們可以用其來(lái)表示自然數(shù)。

Haskell中列表的定義如下：

data

列表的類型是[a]，當(dāng)列表內(nèi)的元素的類型也就是a 為() 時(shí)，我們有一個(gè)特殊的列表類型[()]。這個(gè)列表類型的元素是無(wú)具體信息的，其有用的信息就是列表的長(zhǎng)度，因此我們可以使用列表類型[()]來(lái)表示自然數(shù)。比如用[(), (), ()] 來(lái)表示皮亞諾形式的自然數(shù)S (S (S O))。列表表示的自然數(shù)和數(shù)的關(guān)系如下：

0

我們使用Haskell來(lái)定義如下的用列表類型[()] 表示的自然數(shù)運(yùn)算。

-- | 先定義幾個(gè)基本函數(shù)，用于給后面的運(yùn)算定義使用

列表上的歸納函數(shù)的定義是對(duì)于列表n，對(duì)其進(jìn)行歸納的初始值是z ，每一個(gè)歸納步調(diào)用函數(shù)step 。列表n 是由元素組成的，我們就以z 為參數(shù)遞歸調(diào)用幾次step 函數(shù)。比如當(dāng)列表n 的值是[(), (), ()] 時(shí)，這是由3 個(gè)元素組成的，于是我們就遞歸調(diào)用3 次step 函數(shù)，于是結(jié)果是step (step (step z)) 。

對(duì)于加法，直接用兩個(gè)列表的連接運(yùn)算來(lái)定義。即將兩個(gè)列表m 和n 連接起來(lái)就實(shí)現(xiàn)了列表的加法。

對(duì)于乘法，兩個(gè)列表m 和n 相乘，就相當(dāng)于把n 個(gè)m 加起來(lái)。用歸納函數(shù)來(lái)定義就相當(dāng)于初始值是[]，step 是(m +) 也就是plus m ，我們對(duì)列表n 做歸納法。于是乘以一個(gè)值為[(), ()] 的列表，我們就遞歸調(diào)用兩步遞歸步plus m，于是得到結(jié)果值是plus m (plus m [])，就是將兩個(gè)列表m 連接起來(lái)。

對(duì)于冪運(yùn)算，則和乘法類似，列表m 的n 次冪的值就等于把n 個(gè)m 乘起來(lái)。用歸納函數(shù)來(lái)定義就相當(dāng)于初始值是[()]，step 是(m *) 也就是mult m ，我們對(duì)冪數(shù)n 做歸納法。于是求m 的一個(gè)值為[(), ()] 的n 次冪的自然數(shù)的值，我們就遞歸調(diào)用兩步遞歸步plus m，于是得到結(jié)果值是mult m (mult m (S O))，就是m * m。

• 用函數(shù)表示自然數(shù)（丘奇數(shù)）

在純函數(shù)編程語(yǔ)言中（比如Haskell），函數(shù)也是一個(gè)值，因此我們也可以用函數(shù)來(lái)表示自然數(shù)。這種表述方式時(shí)阿隆佐.丘奇發(fā)明的，因此也叫丘奇數(shù)。

我們知道，函數(shù)是可以組合起來(lái)，即我們可以把函數(shù)f 和g 組合起來(lái)得到g . f ，這里運(yùn)算符 . 就是組合運(yùn)算（按普遍的定義，是反序的）。那我們把相同的兩個(gè)函數(shù)f 組合起來(lái)就得到了f . f，把三個(gè)函數(shù)f 組合起來(lái)就得到了f . f . f，以此類推，我們就可以得到n 個(gè)函數(shù)f 的組合f . f . f . f ...。我們可以用函數(shù)f 的組合來(lái)表示自然數(shù)，由幾個(gè)函數(shù)f 組合的函數(shù)就表示自然數(shù)幾，比如用f 表示S O ，用f . f 表示S (S O) ，用f . f . f 表示S (S (S O))。至于自然數(shù)O ，則用函數(shù)id 來(lái)表示。丘奇數(shù)和數(shù)的對(duì)應(yīng)關(guān)系如下：

0

于是就有了如下使用Haskell來(lái)實(shí)現(xiàn)的自然數(shù)的函數(shù)表示的定義和基本運(yùn)算。

-- | 用函數(shù)來(lái)表示自然數(shù)的數(shù)據(jù)類型，就是給定一個(gè)函數(shù)f得到多個(gè)函數(shù)f的組合函數(shù)。

我們用一個(gè)新的數(shù)據(jù)類型Church來(lái)定義丘奇數(shù)，這實(shí)際上就是以函數(shù)f 為參數(shù)得到多個(gè)函數(shù)f 組合的函數(shù)的lambda函數(shù)的封裝類型，其本質(zhì)就是一個(gè)lambda函數(shù)，這個(gè)lambda函數(shù)的返回結(jié)果是多個(gè)函數(shù)f的組合。

當(dāng)類型Church的lambda的函數(shù)參數(shù)是(+1) 時(shí)，如果這個(gè)丘奇數(shù)表示的是自然數(shù)S (S (S O))，那lambda函數(shù)返回的結(jié)果是(+1) . (+1) . (+1)，也是一個(gè)函數(shù)，將這個(gè)函數(shù)應(yīng)用到參數(shù)0，我們得到了3。可以看到類型Church（丘奇數(shù)）本身的定義就是歸納的，因此其歸納函數(shù)iter 的實(shí)現(xiàn)就是將歸納步step 直接作為參數(shù)傳遞給類型Church的lambda函數(shù)，然后將結(jié)果函數(shù)應(yīng)用到初始值z(mì) ，就得到了歸納函數(shù)iter 的結(jié)果。

因?yàn)榍鹌鏀?shù)本身的定義就是歸納的，所以我們就不需要用歸納法來(lái)實(shí)現(xiàn)加法了，直接用Church本身的定義來(lái)實(shí)現(xiàn)加法就可以了。比如當(dāng)丘奇數(shù)m 的值為Church (f -> f . f . f)，丘奇數(shù)n 的值為Church (f -> f . f) 時(shí)，m 加上n 的丘奇數(shù)的lambda函數(shù)返回的結(jié)果是(f . f . f . f . f)，也就是Church (f -> (f . f) . (f . f . f))，因此加法就是由函數(shù)的組合運(yùn)算來(lái)實(shí)現(xiàn)。

類似的，丘奇數(shù)的乘法也使用其本身的定義來(lái)實(shí)現(xiàn)。當(dāng)丘奇數(shù)m 的值為Church (f -> f . f . f)，丘奇數(shù)n 的值為Church (f -> f . f) 時(shí)，m 乘以n 的丘奇數(shù)的lambda函數(shù)返回的結(jié)果是(g -> g . g) (f . f . f)，得到Church ((g -> g . g) . (f -> f . f . f))，結(jié)果是Church (f -> (f . f . f) . (f . f . f))，因此乘法就是由丘奇數(shù)的lambda函數(shù)的組合來(lái)實(shí)現(xiàn)的。

最后，丘奇數(shù)的冪運(yùn)算也可以使用其本身的定義來(lái)實(shí)現(xiàn)。當(dāng)丘奇數(shù)m 的值為Church (f -> f . f . f)，丘奇數(shù)n 的值為Church (f -> f . f) 時(shí)，m 的n 次冪的丘奇數(shù)的lambda函數(shù)返回的結(jié)果是(g -> g . g) (h -> h . h . h)，得到Church (f -> ((g -> g . g) (h -> h . h . h)) f)，將g 替換為(h -> h . h . h) 有Church (f -> ((h -> h . h . h) . (h -> h . h . h)) f)，結(jié)果是Church (f -> (f . f . f) . (f . f . f) . (f . f . f))，因此冪運(yùn)算就是將一個(gè)丘奇數(shù)的lambda函數(shù)應(yīng)用到另一丘奇數(shù)的lambda函數(shù)的方式來(lái)實(shí)現(xiàn)的。

丘奇數(shù)和前面兩個(gè)自然數(shù)表示形式所不同的是丘奇數(shù)的前驅(qū)的實(shí)現(xiàn)比較難，不像皮亞諾形式的和列表形式的那么簡(jiǎn)單直觀。

我們?cè)谇懊嬉呀?jīng)說(shuō)過(guò)，丘奇數(shù)的前驅(qū)就是從由n 個(gè)函數(shù)f 組合成的函數(shù)中去除一個(gè)函數(shù)f ，變?yōu)橛蒼-1 個(gè)函數(shù)f 組合成的函數(shù)。比如丘奇數(shù)的lambda 返回結(jié)果是f . f . f，這個(gè)丘奇數(shù)的前驅(qū)的lambda 返回的結(jié)果是f . f。最簡(jiǎn)單的實(shí)現(xiàn)就是找到函數(shù)f 的反函數(shù)

，于是有 . f . f .f 等于f . f。但是我們沒(méi)有辦法在Haskell中找到任意一個(gè)函數(shù)的反函數(shù)，看來(lái)這個(gè)實(shí)現(xiàn)方式是行不通的。那既然我們做不到逆轉(zhuǎn)世界，那停止世界是可以的，我們可以使用const x 函數(shù)來(lái)停止世界，將x -> f -> f x 用為x -> f -> x 即x -> const x 來(lái)替換，就去除了一次函數(shù)f 的作用，相當(dāng)于沒(méi)有調(diào)用過(guò)函數(shù)f 。順著這個(gè)思路，我們于是有了如下這個(gè)丘奇數(shù)前驅(qū)的實(shí)現(xiàn)。-- 前驅(qū)函數(shù)，從n個(gè)函數(shù)f的組合得到n-1個(gè)函數(shù)f的組合 predChurch n = Church $ f x -> runChurch n (g h -> h (g f)) (const x) id

具體的證明就留給聰明的讀者吧。

• 自然數(shù)的減法和整除的實(shí)現(xiàn)

有了自然數(shù)的前驅(qū)函數(shù)，我們就可以實(shí)現(xiàn)減法了。前面說(shuō)過(guò)，自然數(shù)沒(méi)有負(fù)數(shù)，所以我們需要可以比較兩個(gè)自然數(shù)，當(dāng)自然數(shù)m 小于自然數(shù)n 時(shí)，m - n 的結(jié)果是0 。

我們可以將自然數(shù)實(shí)現(xiàn)為Eq 和Ord 類型類的實(shí)例，就可以比較兩個(gè)自然數(shù)了。Haskell的實(shí)現(xiàn)如下：

instance

我們通過(guò)自然數(shù)的前驅(qū)來(lái)實(shí)現(xiàn)減法，皮亞諾形式的自然數(shù)減法實(shí)現(xiàn)如下所示：

minus

列表形式的自然數(shù)減法實(shí)現(xiàn)如下所示：

minus

丘奇數(shù)的減法實(shí)現(xiàn)如下所示：

minus

自然數(shù)的整除就是通過(guò)減法來(lái)實(shí)現(xiàn)的，具體如下所示：

divide

列表形式的自然數(shù)和丘奇數(shù)使用類似的方式，具體實(shí)現(xiàn)就留給讀者了。

至此，我們從最開(kāi)始的一無(wú)所知的狀態(tài)一步一步的定義了什么是自然數(shù)，然后定義了其上的加、減、乘、整除和冪運(yùn)算這些基本操作，證明了1 + 1 = 2 這個(gè)命題。我們還介紹了自然數(shù)的其他兩種同構(gòu)形式的自然數(shù)定義，即列表表示的自然數(shù)和丘奇數(shù)。

有興趣的讀者可以等待下一篇：Haskell和自然數(shù)之代數(shù)篇。

參考鏈接：

《同構(gòu)--編程中的數(shù)學(xué)》https://github.com/liuxinyu95/unplugged

總結(jié)

以上是生活随笔為你收集整理的haskell 求列表最大值_Haskell和自然数之基础篇的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。