F#與FP
Written by Allen Lee
做回你自己
每當提到内向的性格,人們就會聯想到"沉默,不愛說話"、"孤僻,不善交際"、"神秘,不夠open"等個性特征。就連一些知名的心理學詞典也使用了消極的描述來定義内向,比如說,《心理學詞典》(Dictionary of Psychology)把内向描述為"專注于自己的思想,回避社會交往,傾向于逃離現實世界",而《心理學國際詞典》(The International Dictionary of Psychology)則把内向定義為"一種主要的人格特質,其特征是專注于自我,缺少社交能力,以及較為消極被動"。人們把内向的性格視為一種有問題的人格特質,而我們的社會也不斷強調外向的性格才是健康發展的自然結果,無怪乎很多性格内向的人都羞于承認自己的本真,并承受着巨大的社會壓力。
類似的情況也發生在函數式程式設計的身上。我曾經在hubFS.net看到一篇文章,作者說某天他告訴同僚自己在業餘時間裡做了一些函數式程式設計,而得到的回應卻是:"Functional programming - isn't that the long haired, dope smoking end of computing?"這個描述讓我聯想到一個性格非常内向的人,整天把自己關在房間裡做計算,不理發、不洗澡、吃喝随便,偶爾出來買點東西就像野人出山,招來無數奇怪目光。如果這就是人們對函數式程式員的印象,那麼你就不必對人們說函數式程式設計語言是數學家的語言或者隻适合在大學裡做研究時使用感到奇怪了。
難道内向的性格真的一無是處嗎?非也。最近在讀《内向者優勢》,它不但讓我了解到内向的性格和外向的性格之間的差異隻是由于不同的大腦機制,而且讓我認識到内向的性格所具有的珍貴品性——"高度集中注意力的能力,對每個相關人員因變化而受到影響的體會,觀察力,擺脫限制、思考問題的習性,作出不尋常決定的意志力,以及使外界放緩腳步的潛力"。我曾經在鄭辛遙的《智慧快餐》上讀到這樣一句話:
做人累,大多是因為扮演了另一個自己。
或許,性格内向的人應該重新發現自身固有的價值,而不是試圖把自己改造成性格外向的人。
同樣地,函數式程式設計也應該有它自己的一片天空。Michael L. Scott在《Programming Language Pragmatics》裡介紹函數式程式設計的概念時曾經提到"Many programmers—probably most—who have written significant amounts of software in both imperative and functional styles find the latter more aesthetically appealing"。這段時間,由于F#的學習,我也如饑似渴地閱讀着各種介紹函數式程式設計的文章,有時候我不禁在想:我們是否對函數式程式設計有太多先入為主的偏見,以至于我們無法更深入、更完整地了解它呢?如果是的話,那就太可惜了,因為我們否定函數式程式設計的同時也會錯過那些本應得到重視的價值。或許,我們應該嘗試了解函數式程式設計在哪些方面能有更出色的表現,而不是一味地排斥它。
今天的主角——函數
在我印象裡,map函數通常用來把一組元素按照一定的規則映射成另一組元素,例如,下面的代碼把一個整數清單映射成由對應元素的平方組成的清單:
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsIyZuBnLxAlRG9FO0MjMflDM1IzMw8CXlVGbw92bs5WZsxWYvwVbvN2Xzd2bsJmbj9CXt92YuM3ZvxmYuNmLzV2Zh1Wavw1LcpDc0RHaiojIsJye.png)
圖 1
有一次,我在《Programming Language Pragmatics》介紹高階函數(10.5 Higher-Order Functions)的那節裡看到map函數的一個"新玩法":
圖 2
箭頭左邊是這個map函數在Scheme裡的用法,而箭頭右邊則是輸出結果。這次,它接受兩個輸入清單,映射規則是一個二進制函數,将會應用到這兩個清單裡位置對應的兩個元素,而運算結果将會放在輸出清單的對應位置上。想想看,如果讓你來實作這個map函數,程式設計語言不限,你會怎麼做?(嘿,我建議你先想一下如何在你喜歡的語言裡實作這個map函數,然後再繼續讀下去。)
那天晚上,我躺在床上睡不着,突然來勁,就起來寫下這段代碼:
代碼 1
這是什麼?函數嗎?哪些是參數?類型是什麼?傳回值呢?函數體怎麼看?……冷靜點!且聽我慢慢道來。
首先,map确實是一個函數,而且是一個高階函數,你可能已在别的地方聽過這個術語了,所謂的高階函數就是指至少滿足下列一個條件的函數:(1)接受一個或多個函數作為輸入;(2)輸出一個函數。讀到這裡,你可能會感到疑惑:"map函數什麼時候接受函數作為輸入啦?"沒看出來是吧?仔細觀察代碼1,是不是充滿了"類型不明"的符号?當你試圖從頭到尾閱讀這段代碼時,有沒有頭暈、胸悶、呼吸急速、手腕無力等感覺?如果有,那麼你很可能患了"顯式類型聲明依賴綜合症"。哈哈,開個玩笑而已。
接着,把map函數的簽名和圖2裡的代碼做一個比對,不難看出,f、l和r就是map函數的參數,其中,f是用于表示映射規則的二進制函數,l和r則是兩個參與運算的輸入清單,然而,f、l和r具體又是什麼類型呢?或許,你曾聽說,F#的一大亮點就是它的類型推斷系統,現在正是考驗這個系統的最佳時機,看看它會把f、l和r三個參數以及函數的傳回值推斷成什麼類型。在F# Interactive裡輸入map函數的代碼,你将會看到如下輸出:
圖 3
這就是map函數的類型,你沒聽錯,這确實是map函數的類型,它包含了參數和傳回值的類型資訊:
- f:('a -> 'a -> 'b)
- l:'a list
- r:'a list
- 傳回值:'b list
其中,'a和'b是類型參數,'a list也可以寫成list<'a>。由此可見,F#的類型推斷系統已經成功推斷出l和r兩個參數以及傳回值的類型是F#的(泛型)清單,至于f,類型推斷系統則從map的代碼中分析出它是一個二進制函數。由于map函數的代碼并未表明f的傳回值和參數的類型相同,于是類型推斷系統分别用兩個不同的類型參數來表示它們,換句話說,f的傳回值和參數的類型可以相同,也可以不同。
然後,我們來看看map函數的實作。如果你對F#的文法還不是很了解,看不懂map函數的代碼,那不要緊,我們暫時把文法放下,用我們自有的邏輯思維去嘗試了解。"match…with…",字面意思就是"把…和…做個比對",于本例,我們可以把它了解成"把 (l, r) 和下列情況做個比對",緊接着,代碼列出了三種情況以供比對:
- 第一種情況:l和r皆為空清單(在F#裡,"[]"用于表示空清單,事實上,類型推斷系統正是看到"[]"才得知l和r的類型是F#的清單),此時,map函數将會傳回一個空清單。
- 第二種情況:這裡是整個map函數最有意思的地方,我們不再停留在清單的表面特征上,而是深入到它的内部結構,我們通過"lh::lt"來描述可以進一步分解成"頭"(lh)和"尾"(lt)的清單,把分解出來的"頭"(lh和rh)傳給f函數(f lh rh),把分解出來的"尾"(lt和rt)遞歸傳給map函數(map f lt rt),并通過"::"運算符把這兩個函數的運算結果連接配接起來。在這裡,我們可以看到,"::"運算符既可以用來分解清單,又可以用來合成清單,"->"左邊是變換之前的形态,右邊則是變換之後的形态,短短的一句話卻包含了"了解"、"分解"和"再合成"三個步驟,如果你看過《鋼之煉金術師》這部動畫,你會發現,這其實就是動畫裡面描述的煉金術的三大步驟。
- 第三種情況:其實它描述了兩種情況,一種是l比r長,另一種是r比l長,即一個可以繼續分解,另一個不能,無論是哪種情況,都意味着運算無法繼續,于是我們抛了一個異常。
實際上,這種比對的實作方式有個正式的名字,叫做"模式比對",你可以試着把每種情況都了解成從一種形态到另一種形态的變換,或許這樣更容易接受。由于我們要以遞歸的方式使用map函數,于是我們需要在聲明它的時候使用rec關鍵字。
最後,我們在F# Interactive裡仿照圖2的做法試一下map函數:
圖 4
乘法運算符的參數和傳回值的類型是相同的,下面,我們換一個參數和傳回值的類型不同的函數來看看:
代碼 2
這個函數傳回一個Tuple,裡面包含了a、b的值和它們的積,把圖4的乘法運算符換成g函數再試一下:
圖 5
現在,假如我要把輸出清單以"2 * 3 = 6"(拿第一個元素來舉例)的方式顯示,那麼我應該怎樣做呢?F#提供了一個List.iter函數,它用途和List<T>.ForEach方法相似,我們可以向List.iter函數傳遞一個匿名函數,對每個元素調用printfn函數,問題是,我如何才能從每個元素裡分解出我想要的三個數值呢?細心觀察輸出清單,你會發現,每個元素都符合 (x, y, z) 模式,于是,我們可以通過把每個元素"比對"到這個模式,提取我們想要的資料(假設result是輸出清單):
圖 6
假如我隻需輸出每個元素的第三個數值,那麼我可以通過"_"符号忽略其餘兩個數值:
圖 7
從這裡可以看出,模式比對的更深層意義其實是在了解資料結構的基礎上對資料進行分解和提取,而非通常認為的switch的山寨版。
調用函數
一般而言,在調用函數(或方法)時,我們都會提供它所需的全部參數,或許,這種做法已經作為一種常識固化到我們的行為了,以至于我在這裡顯式地提及它可能讓人有點不可思議。
試想一下,假如函數的參數是在不同的時間從不同地方擷取的呢?比如說,map函數的三個參數分别有三個不同的使用者在三個不同的時間提供,換言之,每次隻能提供一個參數。
這時候,有同學建議建立兩個輔助函數來"固定"map函數的頭兩個參數:
代碼 3
這個方案不錯,夠簡單,但存在一個小小的限制,拿map_with_g_and_l函數來舉例,它的建立要在l這個參數已經存在的情況下才能完成,換言之,我得先把這些參數以變量的形式定義在某個地方,然後用它們來建立這些輔助函數,當我需要更改函數的參數時,我隻需改變這些變量的值。說到這裡,熟悉面向對象的同學可能會說:"你應該把這三個參數封裝到一個對象裡!"這個主意不錯,我們可以用F#的Record Type來試一下(如果你對它不熟悉,可以先閱讀《從C# 3.0到F#》的相關章節補充一些基礎知識):
代碼 4
接着,我們執行個體化一個Map<'a, 'b>對象:
代碼 5
值得提醒的是,在F#裡,null字面量對于函數和清單來說并非正常的值,是以它們不允許你直接使用null字面量,包括比較和指派,但null字面量可以作為它們在異常情況下的值,代碼4和代碼5示範了兩種使用null字面量的變通做法(事實上,F#不推薦使用null字面量,如果你确實有需要表達"可空"值,你可以使用F#的Option Type,有興趣的同學可以使用Option Type重構代碼4試試看)。然後,我們分别設定l和r的值,并調用Invoke方法:
代碼 6
對于熟悉指令式程式設計和面向對象程式設計的同學來說,上面這個思維過程是自然而然的,但熟悉函數式程式設計的同學可能會覺得我們把簡單的問題複雜化了。在函數式程式設計語言裡,函數預設支援柯裡化(Currying),這使得分階段提供參數成為可能:
代碼 7
說到這裡,你可能會問:"代碼7和代碼3有什麼差別?"最簡單的回答是:代碼7的函數是計算出來的,而代碼3的函數是定義出來的。無法了解?别着急,要了解這個差別,你得先搞清楚函數為何可以接受部分參數,而柯裡化又是怎麼一回事。
拿g函數(代碼2)來舉例,要使它支援分開提供參數,我們應該把它寫成這樣:
代碼 8
從上面代碼可以看出,g函數的參數實際上隻有一個,它會傳回一個匿名函數,這個匿名函數的參數也是一個。換言之,如果我的函數有N個參數,我就要在裡面嵌套N-1個匿名函數,這種寫法顯然不夠直覺(比較一下代碼2和代碼8)。那麼,柯裡化又是什麼呢?它在這裡起到什麼作用?在HaskellWiki上,柯裡化的定義是這樣的:
Currying is the process of transforming a function that takes multiple arguments into a function that takes just a single argument and returns another function if any arguments are still needed.
讀到這裡,我想你已經明白了,柯裡化使以代碼2的方式寫的g函數獲得以代碼8的方式寫的效果。換言之,在F#裡,代碼2和代碼8是等效的。
那麼,計算出來的函數和定義出來的函數又有什麼差別呢?為了讓你能夠看清它們的差別,我們把代碼8的g函數修改一下:
代碼 9
接着,我們在F# Interactive裡分别以代碼7和代碼3的方式使用這個g函數:
圖 8
h1是計算出來的函數,h2是定義出來的函數,請留意"slot"的輸出位置,當我們計算h1時,g函數裡的"printfn "slot""已被執行,而往後對h1的調用将不再執行這句;當我們定義h2時,g函數裡的"printfn "slot""未被執行,而往後每次調用h2都将執行這句。發現差別了嗎?當我們計算h1時,g函數的一部分已被執行了!你能想象得出一個函數能被分部執行意味着什麼嗎?事實上,計算h1的過程有個正式而且非常貼切的名字,叫做"Partial Application"。至此,我想你應該感受到代碼7和代碼3有着本質的不同了。
組合函數
接下來,我們考慮一個新的需求,我在一個檔案裡儲存了這些資料:
圖 9
我要在控制台輸出如下結果:
圖 10
對照圖9和圖10,我們不難發現,圖10輸出的是圖9的兩列資料的積為偶數的算式,從圖9到圖10經曆了如下過程:
圖 11
假如上述過程的每個步驟都對應着一個函數,那麼,完成整個過程将會需要如下六個函數:
代碼 10
現在的問題是,你會如何調用這些函數?一個常見的做法是:
圖 12
然而,F# 提供了一個很特别的運算符——"|>",它使你可以用如下方式調用這些函數:
圖 13
嘿!發現什麼了嗎?看看圖11,再看看圖13,我相信你已經看到我所看到的東西了。假如我要用一個函數來表示圖11的過程呢?一個常見的做法是:
代碼 11
此刻,我相信你應該很想知道process_and_print函數能否像圖13那樣保留圖11的"形狀",當然可以!F#提供了另一個很特别的運算符——">>",它使你可以用如下方式組合這些函數:
代碼 12
如果說供應鍊展現了從采購原材料到把最終産品送到消費者手中的整個過程,那麼代碼12的"資料鍊"則展現了從讀取原始資料到把最終結果輸出控制台的整個過程。當我們把整條鍊架好後,剩下的就是"提供原材料"了:
圖 14
進階話題
回到我們的map函數,有同學說它可能會導緻堆棧溢出,嗯,的确有這種可能,怎麼辦?我們可以把它改成"尾遞歸"(Tail Recursion):
代碼 13
此外,你還可以通過本地函數"隐藏"它的實作:
代碼 14
如果你想更深入地了解尾遞歸,我推薦你去看Chris Smith的《Understanding Tail Recursion》。
你也可以把它改成CPS(Continuation-Passing Style):
代碼 15
如果你對CPS沒有了解,我推薦你去看Matthew Podwysocki的《Recursing on Recursion - Continuation Passing》和wesdyer的《Continuation-Passing Style》。
接下來幹嘛呢?布置作業!假設我有一個清單的清單:
let have = [['a';'b';'1'];['c';'d';'2'];['e';'f';'3']]
我想把它變成這樣:
let want = [['a';'c';'e'];['b';'d';'f'];['1';'2';'3']]
我該怎麼做?這道題目是在Jomo Fisher的部落格上找到的,那裡有很多人給出不同語言的實作,你可以用你最擅長的語言來試一下。
包容"新"事物
函數式程式設計已經不算什麼新事物了,可它為何就是普及不起來呢?是因為它不貼近實際?是因為它的理論門檻太高?還是因為我們有了更好的選擇?在給出我的看法之前,我想和你分享一個我在傑拉爾德·溫伯格的《咨詢的奧秘——咨詢師的百寶箱》裡看到的小故事:
某鐵路公司的官員拒絕了群眾在某處設立停靠站的要求,因為在進行一番研究後,他們發現沒有任何旅客在停靠時間内在該站台等候——當然,因為那時該列車并不準備停靠該站,旅客沒有任何等待的理由。
你能看出個中的沖突嗎?因為某個站台沒有設立停靠站,是以旅客沒有在此等候,因為沒有旅客在此等候,是以該站台無需設立停靠站,這是什麼邏輯?溫伯格把這個"邏輯"總結為"鐵路悖論":
因為服務太差,人們對更好服務的要求被予以拒絕。
試想一下,如果用人機關總以缺乏經驗為由拒絕招收應屆畢業生,那麼他們就會失去增長工作經驗的機會,進而導緻更多用人機關以此為由拒絕招收他們。經驗是過去的寫照,它無法代表現在,更不能預示未來,很多企業一邊用狹窄的眼光來看待人才,一邊又大喊沒有人才,每當此時,我都會不禁想起鄭辛遙在《智慧快餐》裡提到的一個問題:
缺乏人才,還是缺乏容納人才的機制?
函數式程式設計通常被認為是"學院之物",它隻适用于學術研究,是以人們認為沒有必要讓它進入"現實世界",它也是以失去踏出學院大門的機會。試問,你可曾靜下心來了解過函數式程式設計?抑或是跟随衆人的看法重演一次"小馬過河"?
自從微軟宣布把F#産品化,很多人就開始問F#和C#哪個更好?為何他們如此關注這個問題?為何他們認為F#和C#是相斥而不是相承的?當今社會,競争激烈之程度遠勝以往,優勝劣汰的觀念也深深紮根于人們的思想之中,新舊更替的現象更是見慣不怪,以至于人們在面對新事物時的第一反應幾乎都是"它将要取代什麼"。當今社會,發展迅猛之程度令人咂舌,人們要承受的東西似乎已經太多了,以至于稍稍停下來做點有益思考的時間都支付不起,更别說了解另一個可能有着巨大差異的世界觀。無力包容多個不同的世界觀會迫使你必須從中選擇一個,而這又會在你的潛意識種下這樣一個觀念:我必須選擇最好的那個。這個觀念的異化會導緻你選擇程式設計語言就像奴才選主子一樣,必須謹慎決定,以免選錯了主子會連累自己的将來。試問,是程式設計語言為程式員服務,還是程式員為程式設計語言奴役?
牛頓說物體具有維持原來狀态的慣性,人的思維和行為又何嘗不是呢?李子勳在《心靈飛舞》裡說:
每一種理論給人的視覺與感覺覺建立了一種關聯現實,我們越是欣賞一種理論,我們受到這種理論的制約也越多,我們的視覺與感覺覺也越窄。如果我們還有無意識地否定其他理論的心理傾向,那麼我們基本上就可以被稱為某種理論的"囚徒"。越是深刻地相信和依賴一種理論,人們的認知能力越會被理論慢慢地縮窄到一個非常可憐的境地,直到完全失去心靈與感覺的自由。
還記得自己有過多少次為了符合某個理論而采取某個措施而不是為了解決某個問題而選擇某個理論嗎?不同的程式設計思想就像看待事物的不同角度,無論你今天用哪個角度來看待事物,多一個選擇總是有好處的,隻要你沒有在這些選擇中迷失方向。