王垠：编程的宗派( 三 ) 总是有人喜欢争论这类问题

函数式编程的另一个贡献，是它们的类型系统。函数式语言对于类型的思维，往往非常的严密。函数式语言的类型系统，往往比面向对象语言来得严密和简单很多，它们可以帮助你对程序进行严密的逻辑推理。然而类型系统一是把双刃剑，如果你对它看得太重，它反而会带来不必要的复杂性和过度工程。这个我在下面讲讲。
各种“白象”（white elephant）所谓白象， “white elephant” ，是指被人奉为神圣，价格昂贵，却没有实际用处的东西。函数式语言里面有很好的东西，然而它们里面有很多多余的特性，这些特性跟白象的性质类似。
函数式语言的“拥护者”们，往往认为这个世界本来应该是“纯”（pure）的，不应该有任何“副作用” 。他们把一切的“赋值操作”看成低级的做法。他们很在乎所谓尾递归，类型推导， fold ， currying ， maybe type等等。他们以自己能写出使用这些特性的代码为豪。可是殊不知，那些东西其实除了能自我安慰，制造高人一等的幻觉，并不一定能带来真正优秀可靠的代码。
纯函数半壶水都喜欢响叮当。很多喜欢自吹为“函数式程序员”的人，往往并不真的理解函数式语言的本质。他们一旦看到过程式语言的写法就嗤之以鼻。比如以下这个C函数：
int f(int x) {int y = 0;int z = 0;y = 2 * x;z = y + 1;return z / 3;}很多函数式程序员可能看到那几个赋值操作就皱起眉头，然而他们看不到的是，这是一个真正意义上的“纯函数” ，它在本质上跟Haskell之类语言的函数是一样的，也许还更加优雅一些。
盲目鄙视赋值操作的人，也不理解“数据流”的概念。其实不管是对局部变量赋值还是把它们作为参数传递，其实本质上都像是把一个东西放进一个管道，或者把一个电信号放在一根导线上，只不过这个管道或者导线，在不同的语言范式里放置的方向和样式有一点不同而已！
文章插图
对数据结构的忽视函数式语言的帮众没有看清楚的另一个重要的，致命的东西，是数据结构的根本性和重要性。数据结构的有些问题是“物理”和“本质”地存在的，不是换个语言或者换个风格就可以奇迹般消失掉的。函数式语言的拥护者们喜欢盲目的相信和使用列表（list），而没有看清楚它的本质以及它所带来的时间复杂度。列表带来的问题，不仅仅是编程的复杂性。不管你怎么聪明的使用它，很多性能问题是根本没法解决的，因为列表的拓扑结构根本就不适合用来干有些事情！
从数据结构的角度看， Lisp所谓的list就是一个单向链表。你必须从上一个节点才能访问下一个，而这每一次“间接寻址” ，都是需要时间的。在这种数据结构下，很简单的像length或者append之类函数，时间复杂度都是O(n)！为了绕过这数据结构的不足，所谓的“Lisp风格”告诉你，不要反复append ，因为那样复杂度是O(n2) 。如果需要反复把元素加到列表末尾，那么应该先反复cons ，然后再reverse一下。很可惜的是，当你同时有递归调用，就会发现cons+reverse的做法颠来倒去的，非常容易出错。有时候列表是正的，有时候是反的，有时候一部分是反的…… 这种方式用一次还可以，多几层递归之后，自己都把自己搞糊涂了。好不容易做对了，下次修改可能又会出错。然而就是有人喜欢显示自己聪明，喜欢自虐，迎着这类人为制造的“困难”勇往直前
富有讽刺意味的是，半壶水的Lisp程序员都喜欢用list ，真正深邃的Lisp大师级人物，不知道什么时候应该使用记录（结构）或者数组。在Indiana大学，我曾经上过一门Scheme（一种现代Lisp方言）编译器的课程，授课的老师是R. Kent Dybvig ，他是世界上最先进的Scheme编译器Chez Scheme的作者。我们的课程编译器的数据结构（包括AST）都是用list表示的。期末的时候， Kent对我们说：“你们的编译器已经可以生成跟我的Chez Scheme媲美的代码，然而Chez Scheme不止生成高效的目标代码，它的编译速度是你们的700倍以上。它可以在5秒钟之内编译它自己！” 然后他透露了一点Chez Scheme速度之快的原因。其中一个原因，就是因为Chez Scheme的内部数据结构根本不是list 。在编译一开头的时候， Chez Scheme就已经把输入的代码转换成了数组一样的，固定长度的结构。后来在工业界的经验教训也告诉了我，数组比起链表，确实在某些时候有大幅度的性能提升。在什么时候该用链表，什么时候该用数组，是一门艺术。