趣味编程：从字符串中提取信息（参考答案 - 下）
2009-10-22 01:04 by 老赵, 17784 visits昨天我们观察了如何使用基于状态机的顺序解析方式来提取字符串中的信息，不过由于winter-cn的做法和我原始的想法不谋而合，但实现的更为清晰，因此我在不献丑的同时，又设法使用另外一种方式来解决这个问题。后来又看到许多朋友给出了各种各样的做法，有普通拆分的方式，有利用正则表达式的做法。于是最后，我“不得不”使用一种特别的方式：F#来编写这么一段解析逻辑。从中我们也可以看到F#在做一些解析工作时的方便之处，在今后我还会谈一下它对我编写C#代码时的启发。
在我看来，F#的解析逻辑相对前文的做法更容易理解一些，其中有个重要因素便是F#的语言特性，如自然的“元组”使用方式和直观的模式匹配语法。它可以帮助我们使用更精简的代码，更“声明式”而不是“过程式”的代码来解决问题。这个文章会涉及到F#的一些“基础”，我会在接下来的过程中慢慢谈到这些。
首先，第一个“概念”便是F#乃至普通函数式编程中最常见（没有之一）的数据结构：不可变的链表。在前一次“趣味编程”中，我们我们还对这样的链表进行了快速排序。不可变的链表是一个典型的单向链表，它的结构大致是这样的：
可见，这是一种递归的数据结构。每个链表会包含一个元素的“值”，以及另一个链表对象（在上图中，每个框就是一个链表对象）。对于每个链表对象来说，这个“值”便是它的“头（Head）”，而内部的链表对象则是它的“尾（Tail）”。不过方便起见，一个链表往往也会使用一种非递归的方式来表示，尤其是在书写的时候：
1 :: 2 :: 3 :: []
在F#中，图中的链表可以表示为上面这种形式。“::”符号在F#中表示链表的“头”和“尾”（即另一个链表）的连接操作。也就是说，连接符号的左运算数是一个元素，而右运算数是这个元素同类型的链表——嗯，泛性的链表。因此你可以理解，上面这个表达式的最后一个元素是一个空链表，而且连接符号是右关联的（也就是说，对连续的运算符，是从右往左依次计算的）。不过，这个表示方法还是不够简洁，在F#中还可以用下面几种方式来表示相同的链表：
[1; 2; 3] 1 :: [2; 3] 1 :: 2 :: [3]
也就是说，在F#中，一个链表可以表示为使用方括号包含的元素序列，元素之间使用分号隔开。这个表示法就简单多了。
链表在F#中有着非常重要的意义，我们可以对它使用非常直观的模式匹配方式来进行处理。因此，我们输入的字符串也会先被转化为一个“存放字符的链表”再进行处理——至于转化方式我们慢慢再说。假设我们已经得到了这样的链表，如这样的字符串：
"CPU-3.0G--Color-red-green-black--Price-2000-4000--Weight-'5-'--keywords-'levis'"
即可转化为这样的链表（自然中间省略了很多元素）：
'C' :: 'P' :: 'U' :: '-' :: '3' :: ... :: 'l' :: 'e' :: 'v' :: 'i' :: 's' :: '\'' :: []
而我们的最终结果，便是这样一个parse方法：
let rec parse groups chars = // 1 match chars with // 2 | [] -> groups |> List.rev // 3 | '-' :: '-' :: cs -> parse groups cs // 4 | _ –> // 5 let (g, rest) = readTokenGroup [] chars // 6 parse (g :: groups) rest // 7
以上7行代码便是parse函数的完整逻辑：
- 定义一个递归（rec）的parse方法，接受两个参数：groups（当前得到的token group链表）和chars（需要解析的字符链表）。
- F#中模式匹配的起始语法，匹配目标是chars参数，即需要解析的字符链表
- 如果chars为空链表（即“[]”），则意味着没有需要解析的内容了，于是将链表逆序输出。
- 如果chars链表的前两个字符都是“-”，则意味着它们是token groups之间的分隔符，于是忽略它们，继续解析char的剩余部分（cs）。
- 如果是其他任何情况——下划线“_”表示任意匹配
- 调用readTokenGroup方法解析一个完整的token group，输入一个空链表和chars数组，得到一个元组。第一个元素为解析出的token group，第二个元素为chars链表在token group后的剩余部分。
- 此时，g包含第6行解析得到的token group，rest为剩余字符链表。于是递归调用parse方法继续解析rest，其中第一个参数（当前得到的token group链表）为g并入原始groups后的结果。
从中我们可以看出F#中的许多独到之处：
- 函数的定义是不需要指明参数的，同样也不需要指明返回值。F#编译器有着完整的类型推演（Type Inference）能力可以自动得到每个函数的实际签名。
- F#的模式匹配可以使用多条规则，其中每条规则中“->”左侧为匹配条件，右侧为匹配结果。
- 模式匹配左侧，既是“验证”又是“赋值”——确切地说是“绑定”。如第4行代码中，在验证chars前两个字符为“-”的同时，将char链表从第3个元素开始的部分绑定至cs中，于是在“->”符号右侧便可以使用cs了。
- “纯正”的函数式编程中没有循环，如果要实现如C#中的循环效果，则需要使用递归。如parse便是一个递归函数，它会调用自身继续解析readTokenGroup返回的剩余部分。此外，这里还是“尾递归”。
- 函数式编程中不需要return命令，因为函数式编程不同于命令式编程，不是由“语句”组成的，函数体也是另外的函数调用。如模式匹配的最后一条规则中，返回的便是parse函数递归调用的结果。
- 由于链表的结构，向链表的前端添加元素是最为快速的（O(1)时间复杂度），因此我们每次都向groups参数头部添加数据，直到最后返回之前，才使用List模块的rev函数将链表逆序后输出。
- ……（将视您的返回补充更多）
那么我们又该如何使用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 [] chars parse' (g :: groups) rest text |> List.ofSeq |> parse' []
请注意，上面的parse函数已经变成了parse'（最后有个单引号），并且它是新的parse方法的“内部方法”——F#使用缩进来表示“代码的层次”，于是parse'函数便不会对外部公开了，它可以视为parse函数的辅助函数。而parse函数的返回值便是我们需要的结果：一个list<list<string>>对象（根据OCaml的写法，也可以写做string list list）。那么“|>”符号又是做什么的呢？它的作用是将一个参数“输入”给一个函数。例如，以下两种方式是完全等价的：
f x // F#中函数调用不需要括号
x |> f
因此，您可以把“|>”视为交换参数和函数顺序的方式。那么它的意义又是什么呢？其实，对于高级的函数式编程语言，如F#和Haskell，它们的许多特性的目的只有一个：帮助程序员开发出更易于理解的代码。例如，其实parse方法的最后一行也可以写做：
parse' [] (List.ofSeq text)
但是它就没有目前的写法来的流畅：把text传输给List.ofSeq函数，再把结果传输给parse作为最后一个参数（其实这里还用到了curry操作，不过您可以暂时不关心它）。因此，F#的许多函数都会把某个关键的参数放在最后，目的就是便于开发人员写出这种流畅的代码出来。其实，在设计C#类库的时候，我们也会有类似的考虑。至于List模块中的ofSeq方法，则是将一个seq<'a>对象——即IEnumerable<T>转化为T类型的链表。
第一个例子主要是用来展示一些F#中的语言特性，但没有涉及到太多的逻辑。接下来的进度就会比较快了，例如我们在parse’函数里使用的readTokenGroup函数便是如下定义：
// readTokenGroup函数有两个参数，tokens和chars， // tokens表示当前group中已经收集到的token（字符串链表），而 // chars表示待解析的字符（字符链表） let rec private readTokenGroup tokens chars = match chars with // 如果是空链表 | [] // 或者前两个字符都是分隔符“-”, // 则表示当前token group已经解析完了， // 于是将tokens逆序后输出（理由同parse'方法） | '-' :: '-' :: _ -> (tokens |> List.rev, chars) // 如果第一个字符为分隔符“-”，则忽略它， // 继续解析字符链表的剩余部分 | '-' :: cs -> readTokenGroup tokens cs // 如果发现这个token group中的第一个token以单引号开头， // 则表明是一个使用单引号包裹的，带有特殊字符的token， // 于是使用readToken函数读取这个token，得到一个元组， // 其第一个字符为读到的token，rest为剩余部分， // 再递归调用readTokenGroup函数处理rest。 | '\'' :: cs -> let (t, rest) = readToken true [] cs readTokenGroup (t :: tokens) rest // 如果是其他字符，同样使用readToken方法读取第一个token， // 不过传入的第一个参数为false，表明不在引号内， // 其余逻辑和上一个模式的处理方式相同 | _ -> let (t, rest) = readToken false [] chars readTokenGroup (t :: tokens) rest
readTokenGroup的职责是读取一个完整的token group，它会的返回值为一个元组，包含了表示一个token group的list<string>对象和字符串链表的剩余部分。其中会用到readToken来读取单个token。请注意，如果遇到了以单引号开头的token，它传给readToken函数的参数是不带这个单引号的——也就是说，readToken所接受的字符串链表永远不会包含第一个用于包裹token的单引号的。至于readToken函数代码如下：
// readToken有三个参数， // inQuote表示是否正在读取引号内的token， // tokenChars表示已经收集的token字符， // restChars表示待解析的字符链表。 let rec private readToken inQuote tokenChars restChars = let chars2Token chars = new string(chars |> Array.ofList |> Array.rev) if inQuote then match 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) else match restChars with | [] | '-' :: _ -> (chars2Token tokenChars, restChars) | '\'' :: _ -> failwith "start quote unexpected." | c :: cs -> readToken false (c :: tokenChars) cs
我想，经过了上面两个函数的详细说明之后，readToken函数已经没有什么特殊的语法了——可能构造字符的辅助函数char2Token算一个，它是将一个字符链表转化一个数组，再逆序后用于构造一个字符串。还有便是使用failwith抛出一个异常。readToken的逻辑应该还是非常直观的，因此我在这里没有进行注释。不过，如果您对这段内容有所疑惑的话，也可以提出，如果有较多朋友认为注释还是有必要的话，那么我也会对此进行补充。
至此，F#代码的实现就完成了，您可以在此浏览全部代码：http://gist.github.com/215256。在我看来，使用F#的模式匹配来操作链表可以得到非常紧凑而直观的代码，我们只需要按照正常的“读取思路”进行解析便可以了。做到这一点和F#的语言特性不无关系，而C#要实现这样的功能，可能就需要大量的if...else了。不过，F#的语言特性也给了一些C#编程方面的启发。此外，F#本身的这种链表操作方式也有一些天生的缺陷存在，它也是实际开发过程中不可回避的一点——不过这些话题都是有待以后讨论的内容，目前就先谈到这里吧。
F#已经明确成为.NET 4.0中的一等公民了，它的重要程度甚至高于.NET上的Python和Ruby语言实现。因为它是真正意义上一们.NET平台上从未有过的语言，一门函数式编程语言。它有许多特性可以简化我们的开发生活，我认为它很可能是未来和C#配合最为紧密的语言了。因此，如果您想要学习新的语言，不妨试着尽早开始接触F#吧。
![睡觉了[未注册用户]](http://www.gravatar.com/avatar/d6f82e1c0b4bd7b9828e796186c7938b.jpg?d=http%3a%2f%2fblog.zhaojie.me%2fimages%2fprofile.gif&s=50)
赵先生，请珍惜生命，早点睡觉！
夜夜笙歌是对亲人极不负责任的一种行为！