昨天我們觀察了如何使用基于狀態(tài)機(jī)的順序解析方式來提取字符串中的信息，不過由于winter-cn的做法和我原始的想法不謀而合，但實現(xiàn)的更為清晰，因此我在不獻(xiàn)丑的同時，又設(shè)法使用另外一種方式來解決這個問題。后來又看到許多朋友給出了各種各樣的做法，有普通拆分的方式，有利用正則表達(dá)式的做法。于是最后，我“不得不”使用一種特別的方式：F#來編寫這么一段解析邏輯。從中我們也可以看到F#在做一些解析工作時的方便之處，在今后我還會談一下它對我編寫C#代碼時的啟發(fā)。

在我看來，F#的解析邏輯相對前文的做法更容易理解一些，其中有個重要因素便是F#的語言特性，如自然的“元組”使用方式和直觀的模式匹配語法。它可以幫助我們使用更精簡的代碼，更“聲明式”而不是“過程式”的代碼來解決問題。這個文章會涉及到F#的一些“基礎(chǔ)”，我會在接下來的過程中慢慢談到這些。

首先，第一個“概念”便是F#乃至普通函數(shù)式編程中最常見（沒有之一）的數(shù)據(jù)結(jié)構(gòu)：不可變的鏈表。在前一次“趣味編程”中，我們我們還對這樣的鏈表進(jìn)行了快速排序。不可變的鏈表是一個典型的單向鏈表，它的結(jié)構(gòu)大致是這樣的：

可見，這是一種遞歸的數(shù)據(jù)結(jié)構(gòu)。每個鏈表會包含一個元素的“值”，以及另一個鏈表對象（在上圖中，每個框就是一個鏈表對象）。對于每個鏈表對象來說，這個“值”便是它的“頭（Head）”，而內(nèi)部的鏈表對象則是它的“尾（Tail）”。不過方便起見，一個鏈表往往也會使用一種非遞歸的方式來表示，尤其是在書寫的時候：

1 :: 2 :: 3 :: []

在F#中，圖中的鏈表可以表示為上面這種形式。“::”符號在F#中表示鏈表的“頭”和“尾”（即另一個鏈表）的連接操作。也就是說，連接符號的左運(yùn)算數(shù)是一個元素，而右運(yùn)算數(shù)是這個元素同類型的鏈表——嗯，泛性的鏈表。因此你可以理解，上面這個表達(dá)式的最后一個元素是一個空鏈表，而且連接符號是右關(guān)聯(lián)的（也就是說，對連續(xù)的運(yùn)算符，是從右往左依次計算的）。不過，這個表示方法還是不夠簡潔，在F#中還可以用下面幾種方式來表示相同的鏈表：

[1; 2; 3] 1 :: [2; 3] 1 :: 2 :: [3]

也就是說，在F#中，一個鏈表可以表示為使用方括號包含的元素序列，元素之間使用分號隔開。這個表示法就簡單多了。

鏈表在F#中有著非常重要的意義，我們可以對它使用非常直觀的模式匹配方式來進(jìn)行處理。因此，我們輸入的字符串也會先被轉(zhuǎn)化為一個“存放字符的鏈表”再進(jìn)行處理——至于轉(zhuǎn)化方式我們慢慢再說。假設(shè)我們已經(jīng)得到了這樣的鏈表，如這樣的字符串：

"CPU-3.0G--Color-red-green-black--Price-2000-4000--Weight-'5-'--keywords-'levis'"

即可轉(zhuǎn)化為這樣的鏈表（自然中間省略了很多元素）：

'C' :: 'P' :: 'U' :: '-' :: '3' :: ... :: 'l' :: 'e' :: 'v' :: 'i' :: 's' :: '\'' :: []

而我們的最終結(jié)果，便是這樣一個parse方法：

let rec parse groups chars = // 1match chars with // 2| [] -> groups |> List.rev // 3| '-' :: '-' :: cs -> parse groups cs // 4| _ –> // 5let (g, rest) = readTokenGroup [] chars // 6parse (g :: groups) rest // 7

以上7行代碼便是parse函數(shù)的完整邏輯：

定義一個遞歸（rec）的parse方法，接受兩個參數(shù)：groups（當(dāng)前得到的token group鏈表）和chars（需要解析的字符鏈表）。

F#中模式匹配的起始語法，匹配目標(biāo)是chars參數(shù)，即需要解析的字符鏈表

如果chars為空鏈表（即“[]”），則意味著沒有需要解析的內(nèi)容了，于是將鏈表逆序輸出。

如果chars鏈表的前兩個字符都是“-”，則意味著它們是token groups之間的分隔符，于是忽略它們，繼續(xù)解析char的剩余部分（cs）。

如果是其他任何情況——下劃線“_”表示任意匹配

調(diào)用readTokenGroup方法解析一個完整的token group，輸入一個空鏈表和chars數(shù)組，得到一個元組。第一個元素為解析出的token group，第二個元素為chars鏈表在token group后的剩余部分。

此時，g包含第6行解析得到的token group，rest為剩余字符鏈表。于是遞歸調(diào)用parse方法繼續(xù)解析rest，其中第一個參數(shù)（當(dāng)前得到的token group鏈表）為g并入原始groups后的結(jié)果。

從中我們可以看出F#中的許多獨(dú)到之處：

• 函數(shù)的定義是不需要指明參數(shù)的，同樣也不需要指明返回值。F#編譯器有著完整的類型推演（Type Inference）能力可以自動得到每個函數(shù)的實際簽名。
• F#的模式匹配可以使用多條規(guī)則，其中每條規(guī)則中“->”左側(cè)為匹配條件，右側(cè)為匹配結(jié)果。
• 模式匹配左側(cè)，既是“驗證”又是“賦值”——確切地說是“綁定”。如第4行代碼中，在驗證chars前兩個字符為“-”的同時，將char鏈表從第3個元素開始的部分綁定至cs中，于是在“->”符號右側(cè)便可以使用cs了。
• “純正”的函數(shù)式編程中沒有循環(huán)，如果要實現(xiàn)如C#中的循環(huán)效果，則需要使用遞歸。如parse便是一個遞歸函數(shù)，它會調(diào)用自身繼續(xù)解析readTokenGroup返回的剩余部分。此外，這里還是“尾遞歸”。
• 函數(shù)式編程中不需要return命令，因為函數(shù)式編程不同于命令式編程，不是由“語句”組成的，函數(shù)體也是另外的函數(shù)調(diào)用。如模式匹配的最后一條規(guī)則中，返回的便是parse函數(shù)遞歸調(diào)用的結(jié)果。
• 由于鏈表的結(jié)構(gòu)，向鏈表的前端添加元素是最為快速的（O(1)時間復(fù)雜度），因此我們每次都向groups參數(shù)頭部添加數(shù)據(jù)，直到最后返回之前，才使用List模塊的rev函數(shù)將鏈表逆序后輸出。
• ……（將視您的返回補(bǔ)充更多）

那么我們又該如何使用parse方法來解析text呢？事實上，我們使用的是這個方法：

let parse (text : string) =let rec parse' groups chars = match chars with| [] -> groups |> List.rev| '-' :: '-' :: cs -> parse' groups cs| _ ->let (g, rest) = readTokenGroup [] charsparse' (g :: groups) resttext |> List.ofSeq |> parse' []

請注意，上面的parse函數(shù)已經(jīng)變成了parse'（最后有個單引號），并且它是新的parse方法的“內(nèi)部方法”——F#使用縮進(jìn)來表示“代碼的層次”，于是parse'函數(shù)便不會對外部公開了，它可以視為parse函數(shù)的輔助函數(shù)。而parse函數(shù)的返回值便是我們需要的結(jié)果：一個list<list<string>>對象（根據(jù)OCaml的寫法，也可以寫做string list list）。那么“|>”符號又是做什么的呢？它的作用是將一個參數(shù)“輸入”給一個函數(shù)。例如，以下兩種方式是完全等價的：

f x // F#中函數(shù)調(diào)用不需要括號 x |> f

因此，您可以把“|>”視為交換參數(shù)和函數(shù)順序的方式。那么它的意義又是什么呢？其實，對于高級的函數(shù)式編程語言，如F#和Haskell，它們的許多特性的目的只有一個：幫助程序員開發(fā)出更易于理解的代碼。例如，其實parse方法的最后一行也可以寫做：

parse' [] (List.ofSeq text)

但是它就沒有目前的寫法來的流暢：把text傳輸給List.ofSeq函數(shù)，再把結(jié)果傳輸給parse作為最后一個參數(shù)（其實這里還用到了curry操作，不過您可以暫時不關(guān)心它）。因此，F#的許多函數(shù)都會把某個關(guān)鍵的參數(shù)放在最后，目的就是便于開發(fā)人員寫出這種流暢的代碼出來。其實，在設(shè)計C#類庫的時候，我們也會有類似的考慮。至于List模塊中的ofSeq方法，則是將一個seq<'a>對象——即IEnumerable<T>轉(zhuǎn)化為T類型的鏈表。

第一個例子主要是用來展示一些F#中的語言特性，但沒有涉及到太多的邏輯。接下來的進(jìn)度就會比較快了，例如我們在parse’函數(shù)里使用的readTokenGroup函數(shù)便是如下定義：

// readTokenGroup函數(shù)有兩個參數(shù)，tokens和chars， // tokens表示當(dāng)前group中已經(jīng)收集到的token（字符串鏈表），而 // chars表示待解析的字符（字符鏈表） let rec private readTokenGroup tokens chars = match chars with // 如果是空鏈表| [] // 或者前兩個字符都是分隔符“-”, // 則表示當(dāng)前token group已經(jīng)解析完了，// 于是將tokens逆序后輸出（理由同parse'方法）| '-' :: '-' :: _ -> (tokens |> List.rev, chars)// 如果第一個字符為分隔符“-”，則忽略它，// 繼續(xù)解析字符鏈表的剩余部分| '-' :: cs -> readTokenGroup tokens cs // 如果發(fā)現(xiàn)這個token group中的第一個token以單引號開頭，// 則表明是一個使用單引號包裹的，帶有特殊字符的token，// 于是使用readToken函數(shù)讀取這個token，得到一個元組，// 其第一個字符為讀到的token，rest為剩余部分，// 再遞歸調(diào)用readTokenGroup函數(shù)處理rest。| '\'' :: cs -> let (t, rest) = readToken true [] csreadTokenGroup (t :: tokens) rest // 如果是其他字符，同樣使用readToken方法讀取第一個token，// 不過傳入的第一個參數(shù)為false，表明不在引號內(nèi)，// 其余邏輯和上一個模式的處理方式相同| _ ->let (t, rest) = readToken false [] charsreadTokenGroup (t :: tokens) rest

readTokenGroup的職責(zé)是讀取一個完整的token group，它會的返回值為一個元組，包含了表示一個token group的list<string>對象和字符串鏈表的剩余部分。其中會用到readToken來讀取單個token。請注意，如果遇到了以單引號開頭的token，它傳給readToken函數(shù)的參數(shù)是不帶這個單引號的——也就是說，readToken所接受的字符串鏈表永遠(yuǎn)不會包含第一個用于包裹token的單引號的。至于readToken函數(shù)代碼如下：

// readToken有三個參數(shù)， // inQuote表示是否正在讀取引號內(nèi)的token， // tokenChars表示已經(jīng)收集的token字符， // restChars表示待解析的字符鏈表。 let rec private readToken inQuote tokenChars restChars =let chars2Token chars = new string(chars |> Array.ofList |> Array.rev)if inQuote thenmatch restChars with| '\'' :: [] -> (chars2Token tokenChars, [])| '\'' :: '-' :: cs -> (chars2Token tokenChars, '-' :: cs)| '\'' :: '\'' :: cs -> readToken true ('\'' :: tokenChars) cs| c :: cs -> readToken true (c :: tokenChars) cs| _ -> let rest = new string(restChars |> Array.ofList);failwith ("expect an close quote but failed. rest: " + rest)elsematch restChars with| []| '-' :: _ -> (chars2Token tokenChars, restChars)| '\'' :: _ -> failwith "start quote unexpected."| c :: cs -> readToken false (c :: tokenChars) cs

我想，經(jīng)過了上面兩個函數(shù)的詳細(xì)說明之后，readToken函數(shù)已經(jīng)沒有什么特殊的語法了——可能構(gòu)造字符的輔助函數(shù)char2Token算一個，它是將一個字符鏈表轉(zhuǎn)化一個數(shù)組，再逆序后用于構(gòu)造一個字符串。還有便是使用failwith拋出一個異常。readToken的邏輯應(yīng)該還是非常直觀的，因此我在這里沒有進(jìn)行注釋。不過，如果您對這段內(nèi)容有所疑惑的話，也可以提出，如果有較多朋友認(rèn)為注釋還是有必要的話，那么我也會對此進(jìn)行補(bǔ)充。

至此，F#代碼的實現(xiàn)就完成了，您可以在此瀏覽全部代碼：http://gist.github.com/215256。在我看來，使用F#的模式匹配來操作鏈表可以得到非常緊湊而直觀的代碼，我們只需要按照正常的“讀取思路”進(jìn)行解析便可以了。做到這一點和F#的語言特性不無關(guān)系，而C#要實現(xiàn)這樣的功能，可能就需要大量的if...else了。不過，F#的語言特性也給了一些C#編程方面的啟發(fā)。此外，F#本身的這種鏈表操作方式也有一些天生的缺陷存在，它也是實際開發(fā)過程中不可回避的一點——不過這些話題都是有待以后討論的內(nèi)容，目前就先談到這里吧。

F#已經(jīng)明確成為.NET 4.0中的一等公民了，它的重要程度甚至高于.NET上的Python和Ruby語言實現(xiàn)。因為它是真正意義上一們.NET平臺上從未有過的語言，一門函數(shù)式編程語言。它有許多特性可以簡化我們的開發(fā)生活，我認(rèn)為它很可能是未來和C#配合最為緊密的語言了。因此，如果您想要學(xué)習(xí)新的語言，不妨試著盡早開始接觸F#吧。

from:?http://blog.zhaojie.me/2009/10/code-for-fun-tokenizer-answer-2-fsharp.html

總結(jié)

以上是生活随笔為你收集整理的趣味编程：从字符串中提取信息（参考答案 - 下）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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