為甚麼是 Functional Programming?– call by need

call-by-need 是另外一點值得強調的部份。程式基本上只能作有限的計算,而回傳資料也總是有限的,所以不大可能在程式語言中,有個值完整代表無理數,或者是無窮的資料,只是有限的估計而已。是這樣嗎?

well … 在 call-by-need 代表有需要值才會被計算。所以如果有一個常數函數,總是回傳資料 0 ,那麼即使傳入的參數,在 imperative language 中的運算方式不會停止,但我們仍可以得到結果。因為我們不需要去計算參數的資料,就可以得到結果了。

但這跟無窮有什麼關係呢?因為這樣的特性,所以即便我們有無窮的資料,但我們總是可以看到有限的片段,而不需要將所有的資料算出來。例如底下的 Haskell 程式

from :: Nat -> [ Nat ]
from n = n : from (n + 1)

from 是一個函數從 Nat 到 Nat 的串列用 [ Nat ] 代表,他的開頭第一個元素是  n 接下來是 from (n + 1) 該串列,而展開 from (n + 1) 的定義,又會得到它開頭是 n + 1 並且串接一個 from (n + 2),不斷展開下去,我們得到

from n = n : n + 1 : n +2 : … : n + k : …

一直下去沒完沒了,在 imperative language 中我們避免這樣的函數,因為會讓程式進入無窮迴圈。但是在 Haskell 這樣的函數並不會直接被計算,除非你要 Haskell 展開這個函數。而我們可以定義一個函數,取出至多前面 k 個元素形成新的串列如

take :: Nat -> [Nat] -> [ Nat ]
take n [] = []
take 0 xs = []
take n xs = (head x) : (take (n – 1) (tail xs))

前面兩個代表兩種情況,一個是給定的串列是空的話,那麼就傳回空串列,第二個則是說當要取的個數為零的話,我們也回傳空串列,最後當串列不是空的而且個數也不為零,那麼我們就取出第一個元素,並且接上 take (n – 1) (tail xs)。最後的 tail xs 代表是第一個之後的串列。

所以呢,我們可以寫 take 3 (from 4) 得到 4 : 5 : 6 : [] 這樣的串列,也就是依序是 4, 5, 6 的串列,最後的 [] 代表著串列的結束。為甚麼?take 3 (from 4) ,會先展開 from 4 成 4 : from 5,然後套用第三個敘述變成 4 : take 2 (from 5),再來是 4 : 5 : take 1 (from 6) , 4 : 5 : 6 : []。中間跳了一些步驟,有興趣可以再從網路找找資料。

另外,我們也可以定義一個自己接自己的串列如

itself :: [Nat]
itself = 3 : itself

就寫程式的方便性而言,我們不寫一個函數產生 n 到 m ,而是結合前面兩個函數來得到 n 到 m,一來重複使用我們的函數,二來會比直接寫一個 n 到 m 來得直覺一些(如果習慣這樣的方式的話)。但我們也會注意到,from n 本身是無窮的資料,但我們仍然可以得到一些資訊。從這邊得到一個,即便是無限也是有限的估計,或者說無限其實是所有有限資訊的聯集。

雖然這些還不夠精確,但希望會有個概念,在程式裡頭仍然可以擁有概念上無限的資料結構,或者當作是有限資料的極限點。不過這有機會再說吧。

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s