OCaml语言编程基础教程

版权信息

书名：OCaml语言编程基础教程

ISBN：978-7-115-47121-5

本书由人民邮电出版社发行数字版。版权所有，侵权必究。

您购买的人民邮电出版社电子书仅供您个人使用，未经授权，不得以任何方式复制和传播本书内容。

我们愿意相信读者具有这样的良知和觉悟，与我们共同保护知识产权。

如果购买者有侵权行为，我们可能对该用户实施包括但不限于关闭该帐号等维权措施，并可能追究法律责任。

著　　　　 陈　钢　 张　静

责任编辑　陈冀康

人民邮电出版社出版发行　　北京市丰台区成寿寺路11号

邮编　100164 　电子邮件　315@ptpress.com.cn

网址　http://www.ptpress.com.cn

读者服务热线：(010)81055410

反盗版热线：(010)81055315

内容提要

OCaml语言是一种函数式程序设计语言。

本书重点介绍函数式编程的基础知识以及OCaml程序设计的技巧，同时兼顾应用软件开发的需求。全书共8章，前5章讲解OCaml语言的函数式控制结构、数据结构、模块化程序设计、命令式程序设计和图形程序设计；第6章介绍如何把OCaml移植到F#，第7章介绍通过C#开发的用户界面调用OCaml或F#程序，第8章介绍面向对象程序设计。

本书适合想要学习OCaml程序语言或者想要学习函数式编程的读者阅读参考。

序

近年函数式语言和函数式编程迎来了一个新热潮，人们用函数式语言开发出越来越多的应用和系统，Scala、Lisp、Erlang、Dylan、Rust、Haskell、Scheme等语言出现在各种语言使用排行榜中，显示出其重要性和实际价值。在这种情况下，作为计算机专业工作者，学习函数式语言和编程知识也变得越来越重要。

函数式语言与常规过程式语言有同样长的发展历史。在今天还使用较为广泛的语言中，最早的函数式语言是John McCarthy于1958年设计的Lisp，其诞生仅比公认的第一个高级语言Fortran晚一点。Lisp之后近60年里，人们陆续开发了许多函数式语言，其中产生了长期影响的包括ML和Haskell等。在另一相关领域，人们针对硬件设计实现的需要，开发了一批用于描述硬件的函数式语言，其中一些已经实际用于开发各种硬件。近年函数式语言的大发展，主要原因包括软件系统复杂性的快速增长，软件安全问题越来越严重，以及多核硬件和并行编程的需要。函数式语言和相关编程技术在这些方面都有本质性的优势。

函数式语言不仅本身具有实用性，还对一般程序语言和软件开发领域的发展产生了重要影响。大多数人可能不了解这方面的情况，实际上，今天常规语言和编程中的大量概念和技术出自函数式语言和相关编程实践。人们在函数式领域开发和检验了大量语言概念、实现技术和编程技术，这些工作在程序设计和软件技术的发展中起到至关重要的作用。早期的例子如动态存储分配，自动存储回收（废料收集），基于栈的语言实现技术，表和表处理，基于链接的数据结构，递归函数定义，尾递归优化，函数的函数参数（高阶函数），有关数据类型的研究和类型理论，变动性（可变对象和不可变对象），数据驱动的程序设计等。近年另一些概念和机制被频繁地融入各种新编程语言或已有语言的新版本，如lambda表达式、生成器（generator）、闭包、元编程、自反机制、虚拟机和字节码等。

近年人们开发并流行的许多新语言被称为多范式语言，其设计都参考了一些函数式语言的设计，并以某种方式支持函数式编程。例如，已经比较流行的Python和Ruby的设计都受到Lisp和Haskell等函数式语言重要影响；Rust语言的设计明确说明其语言设计受到Erlang、Haskell、OCaml、Scheme、Standard ML等函数式语言的启发；苹果公司开发的新语言Swift从Haskell等语言中学习了许多语言设计的思想。

函数式编程基于表达式和无副作用的函数，不使用赋值等改变状态的操作命令。实际上，在各种常规语言中也可以做函数式编程，一些新语言的社团中也在提倡（在某些场景中）使用函数式编程。这就造成一个情况：我们会看到越来越多的实际程序中包含采用函数式程序思想的片段。函数式编程的知识，可能帮助人更好地理解今天和未来的程序。

这些情况说明，对专业计算机工作者而言，有关函数式语言和函数式编程的知识，将越来越多地从学习中的可选项变成必修项。即使不实际地使用函数式语言编程，对这方面相关问题有些了解，也有利于我们开拓视野，理解新语言和语言中的新特征，了解更多的处理问题和解决问题方法，有利于自己的专业发展。

近几年，国内出版了一些关于函数式程序设计的书，但内容上有些偏颇，对重要语言的覆盖也不够平衡。另外，国人撰写的书籍比较少而译作较多。本书在这两方面都对目前情况有所补偿。作为本书主题的OCaml是ML语言的重要发展分支，是采用静态类型系统的函数式语言的重要代表。该语言不但包含函数式特征，包含命令式特征，还特别支持面向对象编程，支持多种编程范式。人们已经用OCaml开发了一些非常重要的系统。OCaml语言一直处在开发和改进中，官网提供了支持各方面开发的大量程序包，有很强大的用户社团。

本书第一作者陈钢博士多年使用OCaml开发各种软件，有丰富的使用经验，对OCaml的各方面情况和技术有深入的理解。本书全面介绍了OCaml语言和相关的程序开发技术，从最基本的函数式计算结构和数据结构开始，直到各种高级特征的使用，如多语言编程和面向对象的程序开发。本书深入浅出，循序渐进，非常适合初学者从零起步阅读和学习。另一方面，书中不仅讨论了大量语言特征和编程技术问题，也介绍了一些背景和相关理论问题，以帮助读者更清晰地理解函数式编程的思想、技术和方法。本书的出版将大大改善国内计算机工作者学习OCaml语言及其编程技术的基础条件。

OCaml语言是一种非常适合于开发探索性软件系统的语言，其可用程序包中包含了大量在常见语言的库里很少见到的探索性内容。了解相关情况，能拓展我国计算机工作者的眼界，对国内计算机科学技术的发展起到有益的推动作用。

裘宗燕

2018年1月15日

前言

2016年6月14日，华为宣布在法国设立数学研发中心。华为战略与市场总裁徐文伟在揭幕仪式上指出，法国“菲尔茨奖得主多达12位，仅次于美国。数学的研究正在为ICT产业带来全新的突破。”实际情况正是如此。法国在计算机科学方面的一项在国际上有重要影响的成果是OCaml语言，这一语言的诞生与发展得益于法国雄厚的数学基础。

法国菲尔兹奖获得者大都来自巴黎高等师范学院，或与其有关。这个学校占地面积不如中国一所小学，但它却是法国数理化等基础科学的研究中心。20世纪八九十年代，巴黎高等师范学院秉承其数学传统，在范畴论的基础上研发了 λ 演算的一个语义模型，称为“范畴抽象机”（Categorical Abstract Machine），此后又在这一模型的基础上研发了函数式语言ML的一个新的变种，称为Caml。之后，法国人又在Caml语言的基础上增添了面向对象的机制，形成了OCaml语言。后来，OCaml的研发中心转移到INRIA（法国国家信息科学研究中心）。

OCaml语言的诞生和发展都同数学基础密切相关。OCaml语言出现之后，所进行的一项最著名的工作，就是开发Coq定理证明器，它是一个基于高阶带类型 λ 演算的交互式定理证明工具。Coq的主要用途在于两方面，一方面是用于形式化数学（Formalized Mathematics）的研究工作，就是把数学知识用形式化方式表示，并检查数学证明本身的可靠性；另一方面是进行程序的形式化验证。

OCaml语言是一种函数式程序设计语言。函数式语言是一群追求数学美的学者所研发的语言。他们对完美性的重视甚于对实用性的重视，这并不等于说他们不看重实用性，只是他们把完美性放在优先的位置。法国是一个特别注重理想主义的国家，这种理想主义品格也深深地注入到了OCaml语言当中。为了达到数学上的完美性，就需要有更多的付出，同时也会带来更好的长期回报。

函数式语言的发展经历了一个曲折的过程。其间走过很多弯路，遇到很多障碍，也有很多成功的惊喜。如果你喜欢冒险和挑战，愿意接受前进路上的不确定性，对失败和挫折有承受能力，乐于克服困难并享受解决问题之后的喜悦，你应该选择函数式语言。

函数式语言的历史同计算机语言的历史一样长。最早的函数式语言是LISP，它出现在C语言之前。当然，它远不如C语言等命令式语言那样普及。在计算机的发展历史中，人们不断地掀起对函数式语言的热情，但是，在相当长的一段时间内，能够在这个领域中坚持下来的人为数不多，不过，这种情形近年来正在发生改变。

如果想更具体地了解函数式语言的特点，最好的方式是看一个典型的函数式语言程序，并把它同C语言程序做比较。要讲解一个有意义的程序例子，需要先讲解一定的基础知识，这些内容超出了前言的范围。急性子的读者可以翻阅一下2.5.4节中的排序函数的例子。它是一个很能说明函数式语言优缺点的案例。我们把用OCaml实现的排序函数同C语言实现的排序函数做了比较，并且归纳了函数式语言的3个优点：

第一，灵活性和通用性。C排序算法仅仅针对一种特定数据类型的元素进行排序，例如，对整数数组排序。但OCaml写出的排序算法是通用的，不但可以对整数序列排序，而且可以对实数序列、字符串序列，以及各种结构化元素构成的序列进行排序。OCaml能够做到这一点是因为语言中包含了多态类型和高阶函数等成分，这些概念都是C语言没有的。

第二，安全性。C语言编写的排序程序中包含了大量的数组元素访问操作，这类操作很容易出现数组越界错误，从而引起程序崩溃。OCaml的排序程序使用了表数据结构，表操作不会发生类似数组越界这样的严重错误。因此，OCaml的排序程序代码比C排序代码安全。

第三，简洁性。排序的核心操作是一个partition函数。C代码写的partition函数可读性差，而OCaml所写的partition函数简洁易懂，同算法逻辑的吻合很好，代码行数不足C函数的三分之一。

具有上述优点的函数式语言20多年前已经存在。今天的函数式语言具备更丰富的特性，例如，模块化程序设计能力、复杂的类型推导系统等。然而，函数式语言的普及和推广至今还没有完成。这是因为，影响一个语言的推广应用有很多因素，例如，是否有功能丰富的函数库，是否有足够多的成功案例，是否易学易懂，等等。

一个语言的典型应用对语言的普及有很大的影响。C语言被成功用于开发UNIX操作系统，随后，围绕UNIX进行的系统程序开发和应用程序开发都在C语言之上进行。OCaml语言的首个重要应用是Coq定理证明器的开发。同操作系统相比，定理证明器的用户要少得多，而且这些用户并不一定需要用OCaml编程。所以，OCaml语言的推广发展远不如C语言那么快。在很长一段时间内，OCaml的主要用户是一些大学和研究单位，它被用于开发新的定理证明器及其他研究性项目。

同C语言相比，OCaml的发展比较缓慢，但是它一直在稳步前进，用户群也在不断扩大。在现有的函数式语言当中，OCaml是用户最多的语言之一。在应用软件开发中，OCaml的知名度也在不断提高。

OCaml是否容易学习？这个问题因人而异。网上有一位清华学生说，他（她）跟法国OCaml专家学了一段时间，发现学OCaml比零基础学C语言难多了。但是也有同学说，他们一周时间就学会了OCaml。一般而言，一些数学基础好的人比较容易适应OCaml。而对C语言经验丰富的程序员已经养成了一种编程习惯，他们可能反而觉得OCaml难学。因此，学好OCaml要注重培养新的编程习惯，这也是本书写作的重点。

OCaml语言是 λ 演算理论（包括无类型 λ 演算和带类型 λ 演算）的一次出色的应用，同时也是学习λ演算以及基于 λ 演算的众多理论和技术的入门课程。建议有条件的读者把OCaml语言同 λ 演算两门课程结合在一起学习。本书也讲解了一些 λ 演算的基本概念。

事实上，在法国，OCaml语言是学习一系列后续课程的基础课程。这些后续课程包括 λ 演算、类型理论、重写系统、形式语义、程序语言实现方法、高阶定理证明器、进程演算、同步语言、程序分析等。

在互联网时代，能否防范黑客攻击成了软件质量的一个重要指标。在这方面，OCaml语言的优势进一步显现出来。黑客攻击的主要方法是利用软件本身的缺陷入侵到软件内部，而OCaml语言编写的程序可以避免很多C程序中的缺陷，例如缓存溢出和存储泄漏，因此也能够更好地抵抗黑客的攻击。

近20年来各种新型语言。例如Javascript、Go、Scala、Groovy、Elixir、Clojure、Ruby、F#等层出不穷。几乎所有的新语言都深受函数式语言的影响，一些新语言本身就是函数式语言。这些新语言在一定程度上是面向应用的函数式语言，它们在函数式程序设计概念的基础上添加了针对各种专门应用的语言成分。OCaml语言出现在这些新语言之前，它的主要历史功绩是推动了各种函数式程序概念和技术的发展，尤其是语言中的类型系统的发展。它是函数式语言领域做出重要创新的先驱之一，很多新语言中的函数式概念都来自OCaml以及其他一些专业性的函数式语言。因此，对于系统性地学习函数式编程技术，认真学习OCaml语言是很有帮助的。

F#是微软公司开发的OCaml语言变体。它在OCaml基础上添加了大量的具有实用价值的功能，使用户能够利用Windows平台中丰富的库函数，为普通用户提供了很多方便。但是，从语言特性角度看，F#同OCaml依然有差距，例如在模块和函子方面，F#的能力远不如OCaml强大。因此，如果想在函数式程序设计方面得到充分的训练，F#不能替代OCaml。尽管如此，考虑到F#对应用开发的重要性，本书中拿出了一定的篇幅讲OCaml程序怎样移植到F#。

在动手写这本书的时候，国内OCaml教材只有一本《Real World OCaml》【4】的译著，该书对有经验的OCaml程序员很有帮助，但不太适合初学者，在基础训练方面做得不够。在英文教材中，可以考虑的教材有【1，2，3，4，5】。【1，2】是经典的OCaml著作，有权威性，但写作时间比较早，有些程序在最新的OCaml解释器上不能运行，OCaml的一些新发展也未能包含进去；【3】主要适合有经验的OCaml程序员；【5】是专门给初学者写的书，没有包括诸如函子（functor）和面向对象等重要内容。其他一些教材主要讲OCaml语言在某个专业领域的应用，因此并不很适合教学。因此，我们想写一本能够包括OCaml的主要特征，同时能够提供函数式编程基本训练的教材。

教材【1】为函数式语言基本技能训练提供了很好的材料。征得原书作者Guy Cousineau和Micheal Mauny的同意，本书第1章和第2章部分内容翻译自教材【1】。在此对原书的作者表示深切的谢意。同时，我们也增补了很多近年来的新内容。针对国内初学者的特点，本书对函数式编程各方面的概念做了进一步的解释，并增加了OCaml语言同命令式语言的对比。

本书的重点在于讲解函数式编程的基础知识以及OCaml程序设计的技巧，同时兼顾应用软件开发的需求。在写作过程中，很多地方我们把OCaml编程方式同其他语言的编程方式进行比较，便于熟悉其他语言的程序员理解OCaml的特点。我们将看到，同C语言相比，OCaml程序更加精巧，便于进行程序分析；同无类型的函数式语言LISP相比，OCaml增加了类型推导机制，提高了程序的安全性。

本书第1～5章及第8章全部是关于OCaml本身的内容。由于OCaml在用户界面开发等方面不够理想，影响了OCaml的普及。因此第6章和第7章讲了如何通过引入F#和C#来补充OCaml在这方面的不足。F#是微软在OCaml语言基础上开发的一种语言，它同OCaml部分兼容，同时又能利用微软的大量库函数。第6章讲了如何把OCaml移植到F#。第7章讲了怎样通过C#开发的用户界面调用OCaml或F#程序，这个内容也是多语言联合软件开发的一个案例。现代实用软件的开发往往需要结合多种语言的优势。第8章讲了面向对象程序设计。

本书一方面介绍了OCaml程序设计的基本概念以及函数式编程的基本方法，同时尽作者所能介绍了OCaml语言的最新发展，此外还提供了一组规模适度的软件开发案例。3.7节提供了一个质数生成模块案例；4.10节包含了一个四方向链表案例；第5章结合基于模块的开发方法介绍了一个电机作图的案例；第6章结合对F#的介绍讲解了基于F#的电机作图的案例；第7章结合多语言混合设计继续用电机作图的图形化用户界面的设计；8.15节用面向对象方式实现电机作图。

由于作者水平有限，书中错误在所难免，欢迎读者及时指正。

陈钢

航天科工集团

北京京航计算通讯研究所

2018年1月

致谢

感谢我的博士导师Guissepe Longo和Guissepe Castagna。他们的帮助和指导使我不但获得了在法国学习的宝贵机会，而且能够进入程序语言设计这一激动人心的领域。他们在学业上给了我很大的帮助，尤其是在范畴理论和面向对象的程序语言的类型理论方面，使我学到很多重要的理论，他们的帮助使我能够顺利完成博士学位。感谢给我讲授OCaml语言的老师：Guy Cousineau和Micheal Mauny。本书前两章部分内容翻译自他们所写的Caml语言教材。他们是Caml语言的主要发明人，Caml语言是OCaml的前身。感谢给我们讲授λ演算的老师Thérèse Hardin，λ演算是函数式语言的基础；感谢OCaml语言类型理论的老师Xavier Leroy和Didier Rémy，他们也是OCaml语言的主要开发人员；感谢讲授形式化语义的Roberto Di Cosmo老师；感谢讲述构造演算和高阶类型理论的老师Gilles Dowek，构造演算是COQ定理证明器的基础理论，COQ也是用OCaml开发的一个重要的软件。

本书是我在北京京航计算通讯研究所工作期间完成的。感谢集团高红卫等领导对我的工作的鼓励和支持。感谢老所长李艳志和所领导王俊、于林宇、于会、刘军、张津荣、郑德利对我的工作的支持和帮助；感谢舒毅、张静、占银玉，他们在担任我的助手期间做了很多重要的工作。张静在实习期间开始翻译Guy Cousineau和Micheal Mauny的OCaml教材，并且和我一起开始着手这本书的撰写，实习结束后继续花费大量的时间进行本书的撰写和修改工作，非常认真仔细，并且从读者角度提出许多有益的看法，在排版和美化方面做了主要的工作。感谢所内各部门领导李昆、朱琳、王颖、刘伟、王家安、韩旭东、李娜、宋文、魏伟波、魏鑫在我的工作和生活上多方面的帮助；感谢所内同事孟伟、吕宗辉、郑金燕、于润泽、张志刚、王栋、杨楠、张国宇、张明敏、李卓、李丽华、刁立峰、彭鸣、姚可成、高飞、赵静、王佳佳、黄云、宋悦、刘玉峰、李思等在日常工作中的协助。感谢李芳、焦留、杨杰、房静在后勤方面的支持。

感谢裘宗燕教授为本书撰写序言并且提出宝贵意见。感谢孙家广、宋晓宇、蒋颖、顾明、王戟、杨志斌教授，在同他们的合作中，我进一步了解了国内对OCaml语言的需求。

感谢我的妻子胡萍，长期以来她一如既往地支持我的研究工作，在生活和精神上都给了我很大的支持。

陈钢

航天科工集团

北京京航计算通讯研究所

2018年1月16日

第1章　函数式控制结构

OCaml支持函数式、命令式以及面向对象程序设计。但是它的主要特点是支持函数式程序设计。

在函数式程序设计提出了“纯函数”的概念指的是只做输入输出变换，没有副作用的函数。为了说明这一概念，我们先来看两个C函数的例子，第一个：

int f (int a) { return (a+1); }

这个函数的输入值是一个整数a，输出值是a+1。这个函数实现了输入a到输出a+1的变换，除此之外没有其他功能。所以，这个函数是“函数式程序设计”意义上的函数。再看第二个例子：

int g (int a) { b = a; return (a+1); }

这个函数同样把输入的整数a加一之后输出。但是，它还对一个全局变量b进行了赋值，这个操作就称为函数的副作用。因此，g就不是纯函数式程序设计意义下的函数。

函数式程序设计风格的一个重要优点是提高了程序的可靠性和可理解性。它的一个缺点是有时会降低程序的执行效率。

函数式语言的基本控制结构主要有函数定义和函数调用。

核心OCaml程序主要由let定义（definition）和表达式（expression）组成。和C语言相比，OCaml的核心部分严格地说没有“语句”概念。OCaml表达式既起到C语言中表达式的作用，又起到语句的作用。OCaml中的定义类似于C语言中变量声明和函数定义的结合体，它本质上是把一个名字和一个表达式相关联。

表达式的特点就是能够通过计算得到一个值（value）。值是无法继续计算的表达式，函数也是一种值。值都有类型，因此表达式都有类型。OCaml的let定义把变量声明、变量初始化和函数定义等概念整合在一起。本章主要讲OCaml中的表达式以及基本的let定义。表达式和let定义是OCaml解释器能够执行的基本单元。

1.1　OCaml解释器

C语言是基于编译器的语言，而OCaml是基于解释器的语言。对于一个基于编译器的语言，必须写出一个完整的程序才能编译执行。而对于一个基于解释器的语言，程序可以划分为一组可独立执行的代码，解释器可对这组代码顺序执行。基本的OCaml程序由一组定义和一组表达式构成，这些定义和表达式可以在OCaml解释器中按顺序单独执行。OCaml程序也可以编译执行，实用的OCaml应用开发都需要编译。在学习OCaml的时候，我们首先从解释执行开始。程序的解释执行使得语言的学习更为方便。在OCaml解释器中执行OCaml定义和表达式的过程称为交互式会话（interactive session）。

OCaml是一个免费的软件，可以从ocaml.org上下载。在安装了OCaml软件的Linux或Cygwin中，可以通过OCaml命令启动OCaml解释器。在Windows平台上，过去有一个OCamlWin窗口程序，可以在窗口界面中运行OCaml解释器。近几年OCaml的发布方式经常有变化，带窗口界面的OCaml软件不太容易找到。OCaml官方下载页面上现在可以看到三种Window平台下的OCaml安装方案，推荐使用最后一个，即下载OCaml64.exe程序，该程序执行之后会创建一个目录，缺省情况下的目录名是C:\OCaml64，其中包含一个cygwin工作环境。通过在桌面上新创建的OCaml64图标可以启动这个工作环境，它是一个类似linux终端的命令行操作界面。在这个界面中可以执行linux命令，并且可以执行一个opam程序，它是一个用于安装OCaml及相关软件的专用工具。执行opam init将对这个工具做初始化，同时下载并安装最新的OCaml软件。安装完毕之后，可以键入ocaml命令启动OCaml解释系统，如图1-1所示：

图1-1

解释执行OCaml比较好的方式是在XEmacs中安装Tuareg模式，这样不仅可以得到一个支持OCaml编辑的XEmacs模式，而且可以在编辑器中直接运行OCaml解释器。如果没有在本地机器中安装OCaml软件，也可以在网上直接使用在线的OCaml解释器。网站http://try.ocamlpro.com/上不仅提供了可执行OCaml的在线解释器Try OCaml，而且还提供了一些教学材料。

进入OCaml解释器之后就可以进行交互式会话。解释器会显示一个提示符“#”，等待用户输入。此时用户可以输入一个OCaml表达式，用“;;”结尾，按<Enter>键输入到系统中。如果表达式语法正确，解释器会做出一个回应（response），它包括表达式的计算结果，以及对表达式的类型分析结果，前者称为表达式的“值”（value），后者称为表达式的类型（type）。下面是交互式会话的一个例子：

# "Hello World!" ;;
- : string = "Hello World!"

很多语言的教学都从一个Hello World程序开始，这样的程序代表了一个语言中有代表性的最简单的程序。对于OCaml语言，最简单的程序就是"Hello World!"字符串。

在这个例子中，系统的回应分为两部分，第一部分是“- : string”，它表示用户输入表达式的类型是字符串。第二部分是“= "Hello World!"”，它表示输入表达式的计算结果是等号右边的"Hello World!"。

在这个简单的例子中，表达式的值（表达式的计算结果）就是表达式本身，即一个字符串。值得注意的是，系统自动分析出了表达式的类型“string”。

OCaml的类型分析被称为“类型推导”（type inference）或“类型合成”（type synthesis）。它是指通过对表达式的分析自动推导出表达式的类型。这一分析工作是在计算表达式之前做的，因此OCaml的类型系统是静态类型（statically typing）系统。OCaml是强类型（strongly typing）语言，它对代码进行严格的类型检查，保证了程序中不会出现类型错误。在其他语言中，需要对变量和函数进行显式的类型说明，而在OCaml语言中，变量和函数的定义可以不包含类型说明，系统自动推导出它们的类型。类型推导是OCaml语言的重要特色，对此本书会进行重点讲解。

1.2　表达式和let定义

OCaml语言入门很容易，可以把它当作计算器，进行算术表达式的计算。

# 2 + 3 * 5 ;;
- : int = 17

在这个回应中，符号“-”表示这个表达式是由用户输入的，“int”是表达式的类型，它说明这是一个具有整型值的表达式，“17”是表达式的值。

如果想把表达式的计算结果保存起来，并在后续计算中使用，可以通过let结构把表达式的计算结果保存在一个变量中，例如：

# let a = 123 * 456 ;;
val a : int = 56088

这个let结构也称为let定义，或简称定义。它的语法格式是：

let　<变量>　=　<表达式>

其中，变量是一个由小写字母或下划线开头的，由大小写字母、数字和下划线构成的标识符。

对于let定义，系统的回应以“val”开始，表示标识符a是一个变量，用来保存一个值。上面的回应说明，a的类型是int，即整数类型，a的值是56088。

在这里，我们再一次看到了OCaml语言的类型推导能力。在let声明中，并没有说明a的类型，只说明了a将保存表达式123 * 456的计算结果。系统对表达式进行类型分析，推导出这个表达式的类型是整型，从而确定a的类型为整型。

在建立a的定义之后，后续的表达式和定义就可以引用这个变量。例如：

# a + 4 ;;
- a : int = 56092

# let b = a + 5 ;;
val b : int = 56089

在计算一个表达式的时候，表达式内的变量必须在之前已经定义过，不然会产生变量无定义的错误。例如：

# x + 4 ;;
Characters 0-1:
　x + 4 ;;
　^
Error: Unbound value x

let定义起到了其他语言中变量声明的作用，只是它不需要进行变量的类型声明，但是必须给变量一个“初始值”。不允许只声明变量而不给“初始值”。这样做的一个好处就是避免了忘记给变量赋初值的问题。

但是，这里的变量定义和命令式语言中的变量声明是不同的。例如，C语言中，在一个函数体内变量不能重复声明。下面的程序会导致编译错误：

void main () {
　int i = 1;
　int i = 2; 
}

但是在OCaml语言中，一个变量可以合法地重复定义：

# let i = 1 ;;
val i : int = 1
# let i = 2 ;;
val i : int = 2

在这里，let定义看上去和赋值语句相似，但实际上它和赋值过程不一样。在使用赋值语句时，不能对同一个变量赋予不同类型的值。但是，在同一段程序中，可以使用多个let定义，把一个变量和不同类型的值相关联。例如：

# let i = 1.2 ;;
val i : float = 1.2

# let i = "abc" ;;
val i : string = "abc"

# i ;;
- : string = "abc"

也就是说，每做一次定义，就会把之前的定义覆盖掉。因此，let既不是变量声明，也不是变量赋值，而是动态地建立了变量和值的一个关联（variable associated with a value）。我们可以把这个关联看成是变量与值的一个对偶：（变量，值）。程序中的一组let定义建立了变量与值的一个对偶序列，可以写成：

这样一个序列称为“环境”(environment）。在表达式求值时，OCaml到当前的环境中去寻找表达式中变量所关联的值。

从实现角度看，命令式语言中的变量声明是给变量分配一个固定的空间，变量赋值则是对这个空间中内容的修改。而let定义则是给变量动态地分配一个空间。

命令式语言中的一个常见的程序错误就是赋值语句两边的类型不一致。例如，在C语言中可以写出这样的程序：

int main() {
　int i = 1;
　float a = 1.2;
　i = a; // 浮点数赋值给整数
}

由于编译器为不同类型的变量分配的存储空间大小不同，因此数据在不同类型的变量之间传递会造成信息丢失或变形，从而产生错误。在实际应用中，这种错误可能会引起灾难性的后果。1996年6月，欧洲阿丽亚娜5号在发射升空40秒之后爆炸，就是因为浮点数向整数转换时产生了错误。

在OCaml中可以写出同上面的C语言代码表面上相似的程序：

let i = 1 ;;
let a = 1.2 ;;
let i = a ;;

OCaml编译器不会对它报错，同时也不会发生类型转换错误。这是因为程序中的两个i并不占据相同的存储空间，它们可以看成是占据不同存储空间的两个不同的变量，而且具有不同的类型。只是在后一个i定义之后，前一个i自动失效。

OCaml语言的存储自动分配机制和类型推导机制使它成为一个远比C语言更安全的语言。

纯函数式语言的一个标志性特征是没有赋值语句。上面的分析显示，let定义在某些情况下可以替代赋值，但本质上却不同于赋值。

前面所讲的let定义都是顺序执行的，之前定义的变量可以在后面的定义中使用。let定义还有一种并行定义结构，它对一组变量同时定义：

let v1 = e1 
and v2 = e2 
... 
and vn = en

如果一个变量在并行定义的表达式中出现，那么它所取的值是整个并行定义之前给这个变量定义的值，不是并行定义中对这个表达式所定义的值。如果这个变量在并行定义之前没有定义过，那么会出现变量无定义的错误。另外，在并行定义中变量定义的先后顺序不会影响定义结果，所有变量同时被定义。例如：

# let a = 1 ;;
val a : int = 1

# let a = 2　　　　　 （*第一个并行定义*）
　and b = a ;;　　　　(* The same as: let b = a and let a = 2 ;; *)
val a : int = 2
val b : int = 1

# let x = 1　　　　　 （*第二个并行定义*）
and y = x ;;
　Characters 18-19:
　and y = x ;;
　　　　　 ^
Error: Unbound value x

在第一个并行定义的let and结构中，a和b同时被定义，b的值定义为a，此时a的值为1，同时a的值定义为2。正因为a和b是在同一时间被定义，所以b只能取到a在并行定义之前的值，不可能取到并行定义中a的值。在第二个并行定义中，x虽然在并行定义中有定义，但是在并行定义之前并没有定义，因此“let y=x”出错。

注意，OCaml中的注释由“(*”开始，以“*)”结束。

let定义是全局性的。在一个变量被重新定义之前，变量的定义一直有效。下面一节描述一种建立局部定义的方法。

1.3　let局部定义

let定义有一个扩展形式，我们把它称为let局部定义，简称局部定义，其语法格式如下：

let <变量> = <表达式1> in <表达式2>

在这个扩展形式中，变量不再是全局有效的变量，它的作用域局限于<表达式2>。在下面的例子中，首先定义了一个全局有效的变量x，它的值是3；然后在局部定义中，把x的值关联到1，计算x + x的结果是2；在完成这个局部定义的计算之后，x的值又恢复到原来的值3。

# let x = 3 ;;
val x : int = 3

# let x = 1 in x + x ;;
- : int = 2

# x ;;
- : int = 3

局部定义是一种表达式，而不是定义。系统对表达式的回应以“-”开始，而对定义的回应以“val”开始。从语义角度看，let局部定义等价于<表达式2>中把变量全部替换成<表达式1>的结果，即有下述语义等价关系：

这里表示把表达式中的变量全部替换成表达式的结果。例如：

表达式的主要特点就是有一个类型和一个输出值，的类型和输出值就是的类型和输出值。

相比之下，let定义的语义是把一个变量和一个值关联在一起，并且扩展了环境。所以，虽然let定义和局部定义都是由let开始，但却具有不同的语义作用。

此外，正因为局部定义是表达式，所以它可以嵌套使用。例如：

# let x = 1 in
　let y = x + x in
　　x + y ;;
- : int = 3

目前，我们已经看到了两种类型的表达式：一种是算术表达式，另一种是局部定义表达式。在OCaml中，表达式是一个很强大的概念。后面我们将看到，控制语句和函数等复杂结构都是表达式。

一个由OCaml核心语言所写的程序可以由一组let定义和一个表达式构成。也就是说，核心OCaml程序的架构具有下述形态：

let f1 = e1 ;; 
let f2 = e2 ;; 
... 
let fn = en ;; 
e ;;

其中的let定义相当于C语言中全局变量定义和函数定义，最后的e相当于主程序。实际上，一个完整的程序可以不用let定义。例如，上面的程序架构可以直接用let局部定义重写如下：

let f1 = e1 in 
let f2 = e2 in 
... 
let fn = en in 
e ;;

也就是说，一个let局部定义就可以构成一个完整的程序。但是，let定义可以让我们在解释器中以交互式的方式编程，每个let定义能够独立让OCaml接受并执行。另一方面，let定义有助于程序的模块化。一个比较大的应用程序通常由一组程序文件组成，每个文件可以由一组let定义构成，这样的文件可以单独编译。

注意let定义只能用于全局定义，不能在表达式内部使用。因此，在函数和“控制结构”中都不能使用let定义。这也是赋值语句和let定义之间的一个重要区别。在表达式内部只能使用局部定义，它可以在某种程度上实现赋值语句的功能。

虽然let定义（包括局部定义）和赋值语句有很强的相似性，但不能完全取代赋值语句的功能。例如，在命令式语言中，我们通常会用赋值语句去更新一个循环变量。但在纯函数式语言中，无法直接使用这一编程模式。函数式语言有独特的处理循环的方法，学习函数式语言编程需要掌握新的编程模式。

OCaml语言实际上在纯函数式语言的基础上加入了命令式语言的成分，其中也包括命令式的赋值语句。但在OCaml语言的初学阶段，要避免使用命令式编程，首先学好函数式编程技巧。

和let定义相似，局部定义也有并行结构，例如：

# let a = 3 in 
　let a = 2　　　　
　and b = a in (* 也可以写成: let b = a and a = 2 *)
　　a - b ;;　　(* a = 2 , b = 3 *)
- : int = -1

下面先介绍基本的数据类型，然后讲解函数定义。函数的递归定义可以让我们实现循环程序所要达到的功能。

1.4　基本类型

在OCaml语言中，类型是一个非常重要的概念。从语义上看，类型可以直观地理解为一个集合，它包含一组元素。在OCaml语言中，这些元素称为值(value）。“值”是计算过程中所用到的数据以及计算的结果。类型是对值的分类。表达式的类型是表达式所计算出的值的类型。

为了叙述方便，有时我们也称类型中的元素为“对象”。我们会使用术语“对象的类型”以及“对象具有某个类型”。这里所说的“对象”不是面向对象语言中的对象。

程序语言中的类型可以分成两类，一类是系统预定义的基本类型，另一类是在基本类型的基础上构造出的类型。和C语言类似，OCaml的基本类型包括了字符型（char）、整型（int）和浮点型（float）。但是这些类型之间不能直接兼容，例如，不能把char看成是8位整数。但是，可以通过一些预定义的函数进行类型转换。在C语言中，字符串被看成是字符数组，是一个结构类型，但是在OCaml中，字符串是基本类型string。此外，布尔型（bool）也是OCaml中的一种基本类型，它只有两个元素true和false，不是1和0。

在OCaml语言中，除了数据有类型之外，程序也有类型。对于某些没有特别类型的操作，例如打印操作，OCaml专门设置了一个类型unit。

1.4.1　整数类型int

OCaml整数常数的类型是int。也就是说，当我们写下一个整数常数时，系统会自动把它的类型判定为int类型。例如：

# 3 ;;
- : int = 3

在int类型上的四则运算操作符是：+，−，*，/。此外，还有取模运算mod。它们都是二元中缀操作符。每个操作都要作用在两个int类型的整数上，运算的结果也属于int类型。

# 3 * -4 ;;
- : int = -12

# 5 / 2 ;;
- : int = 2

# 5 mod 2 ;;
- : int = 1

整数除法的结果依然是整数。如果要得到更精确的除法结果，需要使用浮点数，见1.4.2节。除法操作“/”和取模操作“mod”之间的关系是：

a = (a / b) * b + (a mod b)

除了用十进制方式书写整数常数外，还可以用十六进制、八进制和二进制的方式书写整数常数。十六进制整数以0x或0X开始，八进制整数以0o或0O开始，二进制常数以0b或0B开始。这里的“0”是数字，“o”和“O”是字母。为了提高可读性，数字之间可以使用下划线。在OCaml会话中，无论用哪一种进制做输入，输出结果都是十进制。例如：

# 0x1 ;;
- : int = 1

# 0Xa1 ;;
- : int = 161

# 0O5 ;;
- : int = 5

# 0b0010 ;;
- : int = 2

# 0b1001_0010 ;;
- : int = 146

关于int类整数的输入和输出函数在后面的章节中会详细讲解。

在32位机中，int中的数实际上是31位带符号整数，而不是32位整数。因此，32位机int类型整数的范围是。在64位机中，int中的数是63位带符号整数。int留出的一位在存储管理程序中使用。

符号常量max_int和min_int分别表示int中的最大整数和最小整数。在32位机上这两个数值是：

# max_int ;;
- : int = 1073741823

# min_int ;;
- : int = -1073741824

当整数计算超出了这两个值的范围时，计算结果会发生错误，但并不会造成系统发生意外终止。例如：

# max_int + 1 ;;
- : int = -1073741824

# max_int * 10 ;;
- : int = -10

如果要进行真正的32位整数计算，可以使用库int32（库模块名的首字母需要大写）。如果要进行64位整数计算，可以使用库int64。32位整数类型是int32，64位整数类型是int64。此外，本机整数的类型是nativeint，它可以是32位整数，也可以是64位整数，取决于机器字长。OCaml没有专门的8位和16位整数类型。char不能当作8位整数使用。

有些类型的数的库中设置了两个基本整数常数zero和one，例如，int32中的零要写成int32.zero，int64中的零要写成int64.zero。不同数类型之间需要用专门的函数进行相互转换。例如int64类型的数转移到int类型的函数是int64，如int（超过int范围的数在转换中会损失信息，详请可查OCaml手册），从int类型到int64的转换函数是int64.of_int。整数都是带符号的（signed），没有无符号的（unsigned）整数。

OCaml 3.07 版之后通过整数常量加后缀的方式表示不同类型的整数。32位整数的后缀是“l”，64位整数的后缀是“L”，本机整数的后缀是“n”。下面是几个例子：

# 99l;;
- : int32 = 99l
# 99L;;
- : int64 = 99L
# 99n;;
- : nativeint = 99n

如果要进行任意精度的整数计算，可以使用库Big_int。

1.4.2　浮点类型float

OCaml只有一种浮点数类型float。它是双精度64位浮点类型，相当于C语言中的double。OCaml语言没有C语言中的32位浮点类型。

浮点常数必须带一个小数点“.”，否则会被视为int类型。例如：

# 1. ;;
- : float = 1.

浮点数中可以使用字母e表示指数。例如：

# 3e2 ;;
- : float = 300.

注意：数值表达式中表示指数的字符“e”后面不能带括号。

# 1e(-10) ;;
Characters 0-1:
　1e(-10);;
　^
Error: This expression has type int
　　　 This is not a function; it cannot be applied.

# 1e-10 ;;
- : float = 1e-010

当用户输入的数中包含小数点“.”或者表示指数的字符“e”或“E”时，系统就会认为是浮点数。

int类型和float类型是两个不相交集合，一个数不能同时具有这两种类型。系统在这两种类型间不能做自动转换。可以用转换函数进行显式类型转换，float_of_int将int类型转换为float类型；int_of_float将float类型转换成int类型。

在做浮点四则运算的时候，所有算术操作符后面都要加上小数点“.”：

# 4e2 *. 2. /. 3. +. 1. ;;
- : float = 267.66666666666669

如果把整数运算和浮点运算混合在一起，OCaml会报告类型错误：

# 1 + 2. ;;
Characters 4-6:
　1 + 2. ;;
　　　^^
Error: This expression has type float but an expression was expected of type int

也就是说，OCaml中的算术操作符没有重载（overloading）机制。重载是指同一个操作符可以作用到不同类型的数据上。

当需要进行整数和浮点数混合计算时，需要在整数和浮点数之间进行转换。例如：

# (float_of_int 1) +. 2. ;;
- : float = 3.

# 1 + (int_of_float 2.6) ;;
- : int = 3

# let a = 10 * 2 in
　(float_of_int a) -. 10.2 ;;
　- : float = 9.8

虽然这样做看起来比较繁琐，但实际编程时并不是一个严重的负担。

为什么OCaml中的算术操作符不能实现重载呢？主要是因为没有找到好的类型推导方法。在C这样的需要显式类型说明的语言中，每个变量的声明都包含了变量的类型。例如，在函数int f (int a) { return a+1 }中，a具有整数类型；在函数float g (float b) { return b+2 }中，b具有浮点类型。因此，可以推导出a+1是整数类型，b+2是浮点类型。在这当中，第一个+1是整数操作，第二个+2是浮点数操作。在OCaml中，使用变量之前可以不用说明变量的类型。例如，我们可以直接写一个函数定义let f a = a + 1（类似于数学中定义函数f(a)=a+1）。如果允许重载，这里就无法判定a的类型，也无法断定a+1是整型还是浮点类型。因此，OCaml规定1只能表示整数1，不能表示浮点1，“+”只表示整数加，不能表示浮点加。由此保证类型推导能够顺利完成。

有很多数学函数只能作用于浮点数，不能直接作用于整数。这些函数有：平方根函数sqrt、正弦函数sin、余弦函数cos、以e为底的指数函数exp、以e为底的对数函数log（大部分数学教材中写为ln）、正切函数tan、反正切函数atan、反正弦函数asin、反余弦函数acos，等等。下面是几个例子：

# sqrt 2. ;; 
- : float = 1.41421356237309515

# sqrt (float_of_int 2) ;;
- : float = 1.4142135623730951

# acos (-1.) ;;
- : float = 3.1415926535897931

注意，在Try OCaml中，“-1.”要写成“-.1.”，否则出错。在Linux版的OCaml和Windows版的OCaml中，这是正确的写法。

下面是稍复杂一点的浮点运算例子：

# let x = sin(1.) and y = cos(1.) in x *. x +. y *. y ;;
- : float = 1.

1.4.3　字符类型char

字符类型char包含0～255个ASCII字符，每个字符必须写在两个单引号“'”之间。

# 'x' ;;
- : char = 'x'

每个字符用一个8位整数实现，但是在OCaml上不能把字符看成8位整数，在字符类型上没有定义算术操作。使用函数int_of_char可以查看字符对应的ASCII码，函数char_of_int则把ASCII码转换到字符：

# int_of_char 'x' ;;
- : int = 120

# char_of_int 120 ;;
- : char = 'x'

# char_of_int (int_of_char 'x') ;;
- : char = 'x'

# char_of_int ((int_of_char 'x') + 1) ;;
- : char = 'y'

char_of_int只对范围内的整数有定义，超出这个范围则会出错：

# char_of_int 256 ;;
Exception: Invalid_argument "char_of_int".

库Char提供了一些char类型上的有用的函数。例如，把字符变成小写字符或大写字符：

# Char.lowercase_ascii 'A' ;;
- : char = 'a'

# Char.uppercase_ascii 'a' ;;
- : char = 'A'

注意，这是OCaml 4.03版之后新增的函数。之前同样功能的函数是lowercase和uppercase。旧函数使用ISO Latin-1字符集，新函数使用US-ASCII字符集。

Char中还有两个函数Char.chr和Char.code，使用方法和作用效果分别与函数char_of_int和int_of_char一致。

1.4.4　unit类型和简单输入输出

纯函数所做的工作是从参数输入到返回值之间的计算，其他工作一概不做。OCaml语言在纯函数式语言的基础上加入了一些属于命令式语言的“语句”，例如打印、赋值、循环等。“语句”的特点是：不产生输出值，但在运行过程中产生某种“副作用”。所谓“副作用”，指的是输入输出，修改系统状态等非函数型操作。为了把这些“语句”融合到函数式语言当中，就要把每一种“语句”改造成函数，因此，就要保证每一种“语句”既有参数输入，又有返回值输出。可是，有些“语句”原本没有参数，也没有返回值，例如打印新行的操作。为了解决这个问题，就引入了unit类型，它只含有一个值“()”。

# () ;;
- : unit = ()

有了这个类型之后，就可以让所有的“语句”都具有类型unit，语句的运行产生一个值“()”。这些函数有点类似于C语言中输出为void的函数。不过，void函数完全不产生输出，但具有unit类型的函数有一个实实在在的输出。例如，打印字符的函数print_char：

# print_char 'a' ;;
a- : unit = ()

在第二行的输出中，最左边的a是print_char打印的结果。由于没有打印换行，后面的系统输出也出现在同一行。

注：截至2018年1月，在线Try OCaml有一个bug，在交互过程中print类的语句的打印结果不出现，并回应“_:unit=<unknown constructor>”。

此外，还有打印整数的函数print_int，打印浮点数的函数print_float和打印新行的函数print_newline。由于所有的函数都必须有一个输入参数，print_newline也不例外，所以规定它的参数就是unit类型的()。一般而言，凡是不需要参数的函数都使用()作为参数。打印操作可以顺序执行，每个操作之间用分号“;”分开：

# print_int 2 ; print_char ' ' ;　print_int (-3) ; print_newline () ;;
2 -3
- : unit = ()

# print_float 3.4 ; print_char ' ' ; print_float 3e4 ; print_newline() ;;
3.4 30000.
- : unit = ()

通过分号连接的一组表达式构成一个表达式，它的输出是最后一个表达式的输出，它的类型也是最后一个表达式的类型。

每个分号前的表达式可以是任意类型。但是，如果不是unit类型，那么OCaml就会发出一个警告：

# 1 ; 2 ;;
Characters 0-1:
　1 ; 2 ;;
　^
Warning 10: this expression should have type unit.

ignore函数把一个非unit类型的输出转换成unit类型的输出，从而取消分号表达式中的警告：

# ignore 1 ; 2 ;;
- : int = 2

从标准输入上读入整数和浮点数的函数分别是：read_int和read_float。这些函数的参数都是unit类型的值()：

# read_int () ;;
2
- : int = 2

其中第二行是用户输入，第三行是系统输出。

注：截至2018年1月，在线的Try OCaml和XEmacs中启动的OCaml解释器都不能完成read类读入操作。

输入的数据可以保存在一个变量里，并且不需要预先对这个变量进行类型说明，直接用let定义即可：

# let a = read_float () in print_float (a +. 2.7) ; print_newline () ;;
2.3
5.
- : unit = ()

其中第二行是用户输入，第三行是print_float打印结果，第四行是系统输出。

OCaml没有专门用于从标准输入读入单个字符的函数。但可以从标准输入直接读入一个字符串：

# let user_name = read_line () ;;
Alice
val user_name : string = "Alice"

1.4.5　字符串类型string与printf函数

在C语言中，字符串是通过字符数组实现的。这种实现方式有两个缺点，第一操作困难，第二很容易引起错误。有时，需要存储的字符串超出了已分配的存储区空间；有时，无用的存储区没有及时回收，造成存储泄漏。黑客常常利用字符串编程中的缺陷进行攻击。例如，对于字符串读入语句，用户可以输入一个超出字符数组预定长度的字符串，这些超长的部分会覆盖原有程序的正常代码，黑客可以通过这种方式给程序植入病毒代码。因此，C语言字符串系统存在安全隐患。

在OCaml中，字符串由系统自动地动态分配存储空间，使用完毕之后，系统会自动回收无用的空间。这种方式不仅大大简化了字符串的操作，而且增强了程序的安全性。

OCaml字符串的类型是string。程序中随时可以创建一个任意长度的字符串，也可以用let定义把一个变量和一个字符串相关联：

# "a short string" ;;
- : string = "a short string"

# let s = "a var of string" ;;
val s : string = "a var of string"

函数print_string用于打印一个字符串。print_endline 也可用于打印字符串，并在打印结束后再打印一个换行符号：

# let s1 = "first " in
　let s2 = "second" in
　print_string s1; print_endline s2 ;;
first second
- : unit = ()

read_line函数用于读入一行字符串。不需为此预先分配输入缓冲区，可以直接用let定义的变量来保存输入结果。只要输入数据量不超过OS为进程分配的存储空间，就不会发生缓冲溢出：

# let a = read_line () in a ;;
my input
- : string = "my input"

输入的字符串也可以不用变量保存而直接使用：

# print_endline (read_line ()) ;;
my input
my input
- : unit = ()

合并两个字符串的操作也非常简单，并且不需要预先安排一个存储区，只需用中缀连接符“^”即可。这样做既不会有缓冲溢出，也不会发生存储泄漏：

# "one plus " ^ "two" ;;
- : string = "one plus two"

# let a = "hello " in 
　let b = "world" in a^b ;;
 - : string = "hello world"

如果字符串中的字符恰好构成一个整数或者一个浮点数，则可以用预定义函数int_of_string和float_of_string将字符串转换成整数或浮点数：

# int_of_string "-23" ;;
- : int = -23

# float_of_string "1.2e3" ;;
- : float = 1200.

反过来，整数和浮点数也可以通过string_of_int和string_of_float转换成字符串：

# string_of_int 12 ;;
- : string = "12"

# string_of_float (-2.3) ;;
- : string = "-2.3"

汉字可以保存在字符串内，旧版OCaml交互式会话中不能直接显示汉字，4.06版中已经可以了。另外，可以通过字符串打印语句输出汉字字符串：

# let a = "汉字显示" ;;
val a : string = "汉字显示"

# print_endline a ;;
汉字显示
- : unit = ()

库String中包含很多有用的字符串操作函数。例如：

String.trim s去掉字符串两端的空格、制表符和换行符：

# String.trim "　one two 
";;
　- : string = "one two"

String.length s输出字符串s的长度：

# String.length "OCaml" ;;
- : int = 5

字符串中的字符可以通过下标访问，第一个字符的下标是零，末位字符的下标是字符串长度减一。String.get通过下标访问字符串中的字符：

# String.get "1234" 1 ;;
- : char = '2'

String.create n创建一个长度为n的字符串，其中包含任意不确定字符：

# String.create 4 ;;
- : string = "\003\000\000\000"

String.make n c创建一个长度为n的字符串，其中字符均为c：

# String.make 4 '-' ;;
- : string = "----"

在Printf库中有一个格式化打印函数printf，它的格式是：

printf <格式化字符串> <参数1> … <参数n>

它功能类似于C语言中的printf函数。printf的第一个参数是一个带打印格式的字符串，其中包含打印控制字符，后面的参数个数和控制字符个数相同。控制符“%i”“%f”“%c”“%s”分别用于打印整数、浮点数、字符和字符串。字符“\t”和“\n”分别用于表示制表符和换行符。下面是一个例子：

# Printf.printf "int %i, float %f, char %c, string %s\n" 3 3.2 'a' "ok" ;;
int 3, float 3.200000, char a, string ok
- : unit = ()

在“%”和控制符之间可以插入数字，用于控制打印宽度，例如：

# Printf.printf "int %4i, float %4.2f, string%4s\n" 12 3.1 "ok" ;;
int　 12, float 3.10, string　ok
- : unit = ()

“%”之后如果紧跟符号“-”，表示将打印的数据左对齐：

# Printf.printf "int %-4i, float %-4.2f, string%-4s\n" 12 3.1 "ok" ;;
int 12　, float 3.10, stringok　
- : unit = ()

1.4.6　bool类型和if表达式

bool类型仅含两个布尔值true和false。布尔值可以进行逻辑运算。OCaml中有一元逻辑操作：not（非）和二元中缀逻辑操作：&&（与）和||（或）。例如：

# not true ;;
- : bool = false

# true && false ;;
- : bool = false

# true || false ;;
- : bool = true

# let a = true in
　let b = false in
　　a && b || not true ;;
- : bool = false

其中，not的优先级最高，其次是&&，然后是||。

比较运算（=，<，>，<=，>=，<>）的输出结果是bool类型。并且，比较运算可以作用在不同类型的数据上：

# 1 < 2 ;;
- : bool = true

# 1. < 2. ;;
- : bool = true

# 'a' < 'b' ;;
- : bool = true

# "abc" < "abd" ;;
- : bool = true

# false < true ;;
- : bool = true
# false < false ;;
- : bool = false
# 11<21 ;;
- : bool = true
# int32.one < int32.zero ;;
- : bool = false

虽然四则运算操作符不可以重载，但是比较运算符却可以重载，它们既可以用在int上，也可以用在float上，甚至还可以用在字符类型和字符串等类型上。只要两个参数的类型相同，就可以使用比较运算。但是，比较运算只能作用在同一类型的表达式上，否则会有类型错误：

# 1 < 2. ;;
Characters 4-6:
　1 < 2. ;;
　　　^^
Error: This expression has type float but an expression was expected of type
　　　　 int

为什么OCaml中的比较操作符能够实现重载呢？这是因为基于比较表达式的类型推理能够实现。我们通过一个例子来说明这个推理过程的基本思路。假设有一个函数，let f a b = a < b（相当于数学函数 f(a,b) = a<b），此时我们不知道a和b的类型，但是我们知道a和b用于比较表达式的两端，因此能够推断出a和b是任意相同的类型，另外，比较表达式的结果一定是布尔类型。具有这种类型的函数称为多态类型函数，OCaml的类型系统有能力表达这种函数。当然，比较运算本身也是多态类型函数，它们的输入参数是两个类型相同的表达式，输出是布尔类型。

# 1 <= 2 && (0 < 1 || 1 < 0) && not (2 < 2) ;;
- : bool = true

上面的相等比较“=”和不等比较“<>”称为结构化比较。对两个结构化数据，它们会比较结构内部的子元素。此外，还有两个称为“物理比较”的操作符“==”和“!=”，物理比较操作符用于比较变量在内存中的存储地址。如果a和b是两个结构化数据并且指向相同的存储地址，那么“a==b”为真，且“a!=b”为假；反之，如果它们不是指向相同的地址，那么“a==b”为假，且“a!=b”为真。对非结构化数据，这两个操作符的作用和“=”及“<>”相同。在已经学过的数据类型中，浮点数和字符串都是结构化数据，整数和字符是非结构化数据。整数在机器中只占据一个机器字，而浮点数在机器中需要几个机器字来表示。因此，整数是非结构化数据，而浮点数是结构化数据：

# let a = "abc" ;;
val a : string = "abc"

# let b = "abc" ;;
val b : string = "abc"
# let c = b ;;
val c : string = "abc"

# a == b ;;
- : bool = false

# a = b ;;
- : bool = true

# a == c ;;
- : bool = false

# b == c ;;
- : bool = true

bool类型的一个重要应用是在if表达式中用作条件表达式的类型。OCaml的if表达式可以看成是C语言中的if语句和形如b?e1:e2的问号表达式的统一和推广。OCaml的if表达式的语法格式是：

if <条件表达式> then <表达式1> [ else <表达式2> ]

其中，<条件表达式>的输出类型必须是布尔值，<表达式1>和<表达式2>的类型可以是任意类型，但是必须相同，它们的类型就是if表达式的类型。例如：

# if 1 < 2 then true && false else true || false ;;
- : bool = false

# if 1 >= 2 then 1 + 2 else 1 - 2 ;;
- : int = -1

if表达式可以不包含else分支，在这种情况下，要求then分支的输出类型是unit，否则会出错：

# if true then print_endline "Ok" ;;
Ok
- : unit = ()

# if true then 3 ;;
Characters 13-14:
　if true then 3 ;;
　　　　　　　 ^
Error: This expression has type int but an expression was expected of type unit

if表达式可以嵌套使用：

# let a = read_int () in
　if a=1 then print_endline "Got 1"
　else if a=2 then print_endline "Got 2"
　else print_endline ("a= "^(string_of_int a)) ;;
2
Got 2
- : unit = ()

1.5　乘积类型和模式匹配初步

乘积类型的概念来源于集合论中的笛卡儿积。给定两个集合A和B，它们的笛卡儿积定义为：

笛卡儿积概念可以推广到任意多个集合：

两个集合构成的笛卡儿积也叫对偶集合，其中的元素称为对偶。在一般情况下，笛卡儿积中的元素称为元组。由于构造笛卡儿积的操作符是乘法符号，所以笛卡儿积也称集合的乘积。

在OCaml语言中，构造乘积类型的操作符是“*”。类型A和类型B的乘积类型记为A*B。构造乘积类型的元素的操作符是逗号“,”。如果a属于类型A，b属于类型B，那么“a, b”属于类型A*B。二元乘积可以很自然地推广到多元乘积。二元乘积类型中的元素称为对偶，多元乘积类型中的元素称为元组，对偶也是两个元素的元组：

# "Number", 1 ;;
- : string * int = ("Number", 1)

# "pi", 3.14, 5 ;;
- : string * float * int = ("pi", 3.14, 5)

可以构造元组的元组：

# 1, (2, 3), ((4, 5), 6) ;;
- : int * (int * int) * ((int * int) * int) = (1, (2, 3), ((4, 5), 6))

函数fst和snd分别取一个对偶的第一个和第二个分量：

# fst (1, 2) ;;
- : int = 1

# snd (1, 2) ;;
- : int = 2

# let a = 1, (2, 3) in
　fst (snd a) ;;
　- : int = 2

对于有3个以上分量的元组，函数fst和snd不能直接使用：

# fst (1, 2, 3) ;;
Characters 4-11:
　fst (1, 2, 3) ;;
　　　　^^^^^^^
Error: This expression has type 'a * 'b * 'c
　　　　but an expression was expected of type 'd * 'e

访问一般元组内部成分的一种方法是使用一种基于模式匹配的扩展的let局部定义：

# let a = 1, 2, 3 in
　let x, y, z = a in
　　z, y, x ;;
- : int * int * int = (3, 2, 1)

在“let x, y, z = a”中，等号左边的“x, y, z”称为模式（pattern），变量x、y和z称为模式变量（pattern variables）。这个let等式构成一个模式匹配操作，把x、y和z分别关联到1、2和3。

模式中的变量必须互不相同，否则会出错：

# let a = 1, 2, 3 in
　let x, y, x = a in
　x, y, x ;;
　　Characters 25-26:
　let x, y, x = a in
　　　　　　^
Error: Variable x is bound several times in this matching

如果只需要元组中的某些分量，则不需要的模式变量可以用“_”代替：

# let (x, _) = (3.25, 2) ;;　　 (* 求横坐标 *)　
val x : float = 3.25
# let a = 1, 2, 3 in
　let _, _, x = a in
　　x ;;
- : int = 3

很多复杂结构都可以使用模式匹配，基于元组的模式匹配是其中的一种。它的匹配过程是把元组模式和等式右边具有相同结构的表达式的值相比较，从而把模式变量关联到相应的元组分量。模式匹配是一种很强大的机制，它可用于访问任意复杂元组结构中任意位置的元素：

# let a = 1, ((2, 3), 4) in
　let _, ((_, y), z) = a in
　 y, z ;;
- : int * int = (3, 4)

最后，需要注意的是，以下类型：

t1 * t2 * t3　　　　(t1 * t2) * t3　　　　t1 * (t2 * t3)

是3种不同的类型。第一个是一个三元组，第二个和第三个都是二元组，其中第二个的第一个元素是一个二元组，第三个的第二个元素是一个二元组。

1.6　函数和函数类型

在函数式语言中，函数是核心概念。在纯函数式语言中，函数没有副作用，即在函数内部不能对全局变量进行赋值。函数的作用体现在函数的输入输出关系上。函数的参数是函数的输入，返回值是函数的输出。OCaml语言在纯函数式语言的基础上加入了命令式语言的成分，函数中也加入了副作用的操作。但是，在学习的开始阶段，我们要把注意力放在纯函数编程方面。

和C语言相比，OCaml的函数有几个特点。

1）函数调用不带括号，传统的函数调用形如：f (a1, a2, …, an)。在OCaml中写作：f a1 a2 … an。

2）函数体的最后一个表达式的计算结果就是函数的输出，不需要另外写return语句。

3）函数可以有函数名，也可以没有，无名函数称为函数表达式，有名函数相当于一个let定义，把一个变量名和一个函数表达式相关联。

4）函数也是一种表达式，确切地说，它是一种值（值是表达式的特例）。因此，函数可以作为其他函数的输入参数，也可以作为其他函数的输出值，这一机制称为高阶函数。

5）函数的输入参数类型和输出值类型合在一起构成函数的整体类型，也称函数的类型。

6）函数定义时函数的输入输出类型可写也可不写；如果不写，系统会自动推出函数的类型。

7）多参数函数在调用时可以只作用在一部分参数上，称为部分作用。

1.6.1　简单函数

单参数函数的基本定义方式如下：

let f x = exp

它定义了一个名为f的函数，参数是x，函数体是表达式exp。

在定义之后，系统会自动推导出函数参数和函数输出值的类型。假设系统分析出x的类型是A，exp的类型是B，那么函数f的类型为A -> B。这一类型关系通常写成f : A -> B。

箭头“->”是函数类型构造符，它从两个类型A和B出发，构造出一个函数类型A->B。这一记号来源于数学中函数空间的记号。在集合论中，给定两个集合A和B，那么A->B是从A到B的所有函数的集合。

多参数函数的定义是单参数函数定义格式的推广：

let f x1 ... xn = exp

它定义了一个名为f的函数，参数是x1,…,xn，函数体是表达式exp。

假设系统分析出参数x1,…,xn的类型分别是A1,…,An，函数体exp的类型是B，那么函数f的类型为f : A1 -> A2 ->…An -> B。用自然语言可以描述为：“函数f的输入参数的类型分别为A1，A2，…，An，函数输出的类型为B。”

如果函数f的类型是A->B，表达式exp的类型是A，那么f可以合法地作用到exp上，写成f exp，它的类型是B。如果exp的类型不是A，那么系统会发现f exp有类型错误。OCaml不能做自动类型转换，因此，如果exp的类型是整数，A的类型是浮点数，f exp依旧会产生类型错误。下面举例说明：

# let add1 x = x + 1 ;;
val add1 : int -> int = <fun>

它定义了一个名为add1的函数，它的参数是x，函数体是x + 1。同时，add1被看成是一个变量，它的类型是int->int，它的值用<fun>抽象表示。add1的值是函数体，但是函数体通常比较复杂，因此采用抽象的表示方法。

add1只能作用在整型表达式上面：

# add1 2 ;;
- : int = 3
# let a = 1 and b = 2 in add1 (a + b) ;;
- : int = 4

当输入参数和函数参数类型不匹配时会产生类型错误：

# add1 2.1 ;;
Characters 5-8:
　add1 2.1 ;;
　　　 ^^^
Error: This expression has type float but an expression was expected of type
　　　 int

多参数函数可以有两种定义方式，第一种是前面给出的定义格式：

# let add3 a b c = a + b + c ;;
val add3 : int -> int -> int -> int = <fun>

# add3 1 2 3 ;;
- : int = 6

第二种是把多个参数合并到一个元组中，定义输入参数为一个元组的函数：

# let plus3 (a, b, c) = a + b + c ;;
val plus3 : int * int * int -> int = <fun>

# plus3 (1, 2, 3) ;;
- : int = 6

注意，这些函数定义的时候都没有写参数的类型和输出值的类型，系统自动推导出函数的类型。

对于第一种形式的函数定义，可以把函数作用到一部分参数中，这种作用方式称为部分作用（partial application）或部分求值（partial evaluation）。例如：

# add3 1 ;;
- : int -> int -> int = <fun>

部分作用的结果是输出一个函数，这个函数可以作用到剩余参数上。在上例中，表达式（add3 1）是一个双变元函数，它可以作用到两个整数上：

# let g = add3 1 in
　g 2 3 ;;
　- : int = 6

函数体内的变量分为局部变量和自由变量。局部变量是函数定义中引入的变量，包括函数参数，由let局部定义引入的变量，以及后面将要讲到的模式变量。除此之外的变量都是自由变量（free variable）。自由变量不仅包括取值为数据的变量，还包括取值为函数的变量。例如，在函数定义中调用了一个预定义函数sin，那么函数sin也被看作是函数内部的自由变量，因为它并不是函数体内声明的变量。函数内引用的自由变量必须在函数定义之前已经定义，否则会出错。

一般而言，在调用函数进行计算时，函数内自由变量的取值有两种处理方法。一种方法是动态取值，也称为动态作用域（dynamic scoping），即自由变量的值取为函数调用时可见的值。另一种方法是静态取值，也称静态作用域（static scoping），还称为字典域（lexical scoping），即自由变量的取值为函数定义时可见的值。OCaml语言采用静态作用域。下面的例子说明了静态取值的过程：

# let var1 = 1 ;;
val var1 : int = 1

# let f x = x + var1 ;;　　(* 定义一个形如f(x) = x + var1的函数 *)
val f : int -> int = < fun>

# f 2 ;;　　(* 求f(2) 的值 *)
- : int = 3

# let var1 = 10 ;;　　　　(* 重定义var1，将var1与整数10关联 *)
val var1 : int = 10

# f 2 ;;　　(* f(2) 的值并没有因为var1的重定义而改变 *)
- : int = 3

在最后一个函数调用f 2的计算中所用到的var1 所取的值是第一个var1定义的值，var1 = 1。如果采用动态作用域，那么此时的var1将取var1 = 10。例子中的两个用let定义的var1是两个不同的且没有任何关系的var1 ，如同第二个var1叫作a，效果是一样的。

例1：构造计算平面中两点(a,b)和(c,d) 间距离的函数distance：

# let square x = x *. x ;;
val square : float -> float = <fun>

# let distance (a, b) (c, d) = sqrt ( square (a -. c) +. square (b -. d) ) ;;
val distance : float * float -> float * float -> float = <fun>

# distance (-.3. , -.4.) (0. , 0.) ;;
- : float = 5.

上面的做法定义了两个全局函数square和distance。如果要把square作为distance的局部函数，可以这样写：

# let distance (a, b) (c, d) = 
　　let square x = x *. x in
　　sqrt (square (a -. c) +. square (b -. d)) ;;
val distance : float * float -> float * float -> float = <fun>

局部定义square仅在函数体distance内部有效。

例2：模拟硬件全加器。

首先构造半加器，然后用半加器构造全加器。半加器电路图如图1-2所示。

图1-2　半加器电路图

半加器有两个输入和两个输出。其中，输出包括“和”s和进位c，计算公式是：

OCaml没有xor异或操作符，但xor异或可用不等式实现：a xor b = a <> b：

# let half_adder (a, b) = 
　let s = a <> b　 (* xor *)
　and c = a && b in
　　(s, c) ;;
val half_adder : bool * bool -> bool * bool = <fun>

用true代表1，false代表0，把半加器测试一遍：

# half_adder (false, false);;
- : bool * bool = (false, false)

# half_adder (true,　false);;
- : bool * bool = (true, false)


# half_adder (false, true);;
- : bool * bool = (true, false)


# half_adder (true,　true);;
- : bool * bool = (false, true)

用两个半加器可以构造一个全加器，如图1-3所示。

图1-3　构造全加器

# let full_adder (input_a, input_b, carry_in) =
　let s, carry_out = half_adder (input_a, input_b) in
　let sum, c　　　 = half_adder (carry_in, s) in
　　sum, (carry_out || c) ;;
val full_adder : bool * bool * bool -> bool * bool = <fun>

用true代表1，false代表0，把全加器测试一遍：

# let fff = full_adder (false, false, false)
　let tff = full_adder (true, false, false)
　let ftf = full_adder (false, true, false)
　let ttf = full_adder (true, true, false)
　let fft = full_adder (false, false, true)
　let tft = full_adder (true, false, true)
　let ftt = full_adder (false, true, true)
　let ttt = full_adder (true, true, true) ;;
　val fff : bool * bool = (false, false)
　val tff : bool * bool = (true, false)
　val ftf : bool * bool = (true, false)
　val ttf : bool * bool = (false, true)
　val fft : bool * bool = (true, false)
　val tft : bool * bool = (false, true)
　val ftt : bool * bool = (false, true)
　val ttt : bool * bool = (true, true)

如果读者有使用VHDL或Verilog进行硬件设计的经验，会发现这里对全加器的描述比硬件语言对全加器的描述更为简洁。事实上，用函数式语言描述硬件是国际上的一个重要研究方向，并且在半导体公司中有许多实际应用。例如，Xilinx公司用函数式语言LAVA构造复杂的FPGA电路，INTEL公司用内部开发的函数式语言进行算术电路的描述和形式化验证。

上面的全加器用布尔值做输入输出，不便于阅读，可以为它们做一个包装，成为使用0和1做输入/输出的全加器，其中定义了整数转布尔值的函数i2b（缩写自：int to bool）和布尔值转整数的函数b2i（缩写自：bool to int）：

# let full_adderi (input_a, input_b, carry_in) =
　let i2b i = if i=0 then false else true in
　let b2i b = if b then 1 else 0 in
　let a = i2b input_a in
　let b = i2b input_b in
　let cin = i2b carry_in in
　let s, c = full_adder (a, b, cin) in
　　(b2i s), (b2i c) ;;
val full_adderi : int * int * int -> int * int = <fun>

# full_adderi (1, 1, 1) ;;
- : int * int = (1, 1)

1.6.2　函数表达式

前一节描述了带函数名的单参数函数的定义方法：

let f x = exp

即

let <函数名> <参数> = <表达式>

这一定义可以改写成一个等价定义：

let f = function x -> exp

即

let <函数名>　= function <参数> -> <表达式>

此时，等号的右端是一个函数表达式（function expression）。我们有时把函数表达式称为无名函数。

例如，函数let add1 x = x + 1可以改写成：

# let add1 = function x -> x + 1 ;;
val add1 : int -> int = <fun>

这两种方法效果相同。只是，第二种定义方法和最初介绍的let变量定义具有相同的格式：

let <函数名> = <表达式>

其中，<表达式> 的格式是：

function <参数> -> <表达式>

函数表达式是表达式的一种，因此它与其他表达式具有同样的地位，可用于同样的场所。在英文中把这一特征称为first class citizen，中文有时翻译成“首类对象”。例如，上面的定义显示，函数表达式可以像其他表达式一样出现在变量声明的右端。此外，它也可以像函数名一样直接作用到参数上。例如：

# (function x -> x + 1) 2 ;;
- : int = 3

函数表达式的概念起源于演算。在演算中，函数表达式写成，称为函数抽象，或简称抽象（abstraction），也称表达式。这一概念首先在函数式语言中使用，近年来比较先进的语言，例如Java语言和C#语言都引入了表达式。在函数式语言中使用表达式非常自然，也非常方便。

多变元函数可以由单变元函数表达式嵌套构成，例如：

# let plus = function x -> (function y -> x + y) ;;
val plus : int -> int -> int = <fun>

这里定义的plus相当于：

# let plus x y = x + y ;; 
val plus : int -> int -> int = <fun>

函数表达式的前一种定义格式更为基本。实际上，在计算机内部，后一种表达方式要转换成前一种表达方式。

有了函数表达式，我们就更容易理解“部分作用”的概念。以plus 1为例，它的计算过程实际上相当于下面的等式变换：

plus 1 
= (function x -> (function y -> x + y)) 1 
= (function y -> 1 + y)

因此，plus 1是一个单变元的函数，它还可以作用到下一个变元上，例如：

(plus 1) 2 
=　(function y -> 1 + y) 2 
= 1 + 2 = 3

这里所描述的计算过程，在演算中称为“规约”（reduction）。一个表达式不断地规约直到不能继续规约时所得到的结果就称为“值”。因此，函数表达式实际上也是一种特殊的值。例如，plus 1不是一个值，因为它还可以继续规约；而function y -> 1 + y就是一个值，因为它不能继续规约。OCaml的计算过程，就是把一个可以规约的表达式一直转换到不可规约的值。值是特殊的表达式。

一个有n个参数的函数表达式的一般形式是：

function x1 -> (function x2 … (function xn -> exp) …)

如果x1的类型为A1，x2的类型为A2，…，xn的类型为An，且exp的类型为B，那么这个函数表达式的类型为：

A1 -> (A2 -> … -> (An -> B) …)

它可以简写为：

A1 -> A2 -> … -> An -> B

也就是说，在类型的箭头表达式中，箭头是右结合的。

function表达式只能包含一个参数，因此多参数函数表达式的书写和阅读都比较繁琐。为了简化，OCaml提供了一个直接书写多参数函数的fun表达式：

fun x1 … xn -> exp

它所定义的函数和前面用多个function所定义的函数相同，类型也是：

A1 -> A2 -> … -> An -> B

下面是用fun定义的plus函数，

# let plus = fun x y -> x + y ;;
val plus : int -> int -> int = <fun>

本节用3种方式所定义的plus是完全相同的，其实际效果都是把变量plus和函数表达式function x -> (function y -> x + y)相关联，类型也完全相同，都是int -> int -> int。

多参数函数表达式还可以用元组来构造，例如：

# let plus2 = function (x, y) -> x + y ;;
val plus2 : int * int -> int = <fun>

不过，用这种方式构造的函数表达式和前面的plus函数在函数结构和类型上都不一样，调用方式也不一样：

# plus 1 2 ;;
- : int = 3

# plus2 (1, 2) ;;
- : int = 3

注意，第二种方式不能进行部分作用，因为它只有一个对偶类型的参数。

1.6.3　function和fun比较

fun可以有多个参数，但function不可以：

# fun x y -> x + y ;;
- : int -> int -> int = <fun>

# function x y -> x + y ;;
Characters 11-12:
　function x y -> x + y ;;
　　　　　　 ^
Error: Syntax error

function可以直接做模式匹配，但fun不可以：

# function true -> 1 | false -> 0 ;;
- : bool -> int = <fun>

# fun true -> 1 | false -> 0 ;;
Characters 14-15:
　fun true -> 1 | false -> 0 ;;
　　　　　　　　^
Error: Syntax error

前面讲到，等号“=”可用于比较各种结构类型。但是，它不能用于比较两个函数是否相等：

# (fun x -> x) = (fun x -> x) ;;
Exception: Invalid_argument "equal: functional value".

1.6.4　高阶函数

一旦把函数看成表达式，就给程序语言带来了一个重大的变化。凡是表达式可以使用的场所，都可以使用函数。表达式可以作为函数的输入参数，所以函数也可以作为其他函数的输入；表达式可以作为函数的输出，所以函数也可以作为其他函数的输出。这样就很自然地产生了高阶函数的概念。高阶函数就是输入参数为函数或者输出值为函数的函数。

举个例子，函数h将f映射到，它可以定义为：

# let h f x = (f x) /. x ;;
val h : (float -> float) -> float -> float = <fun>

函数h有两个参数，第一个参数是函数f，它是定义在浮点数上的函数，输出值也是浮点数，因此它的类型是float -> float；第二个参数是一个浮点数。

在定义这个函数的时候，我们并没有明确说明两个参数的类型，OCaml的类型分析系统自动推导出函数的类型。首先，它看到一个浮点除法运算符，因此推断出x必须是浮点类型float。然后，根据表达式f x的形式，推断出f是一个函数，并且它的输入参数的类型是float，又因为f x也是浮点除法的一部分，所以f的输出也是浮点数，所以f的类型是float -> float。按这种方式，最终推导出h的类型。

高阶函数和类型推导有着密不可分的关系。如果没有类型推导，就难以判断一个含有高阶函数表达式的结构是否合法。OCaml语言是由ML语言演变过来的，ML语言的一个重要创新就是它的类型推导系统。ML语言是英国爱丁堡大学的Robin Milner发明的，他因此获得了1991年的图灵奖。

下面是函数h的一次调用：

# h sin 0.1 ;;
- : float = 0.99833416646828155

h不仅是一个输入参数为函数的高阶函数，而且它的输出值也为函数。前面讲过函数可以部分作用，部分作用的结果实际上就是输出一个函数：

# let k = h sin ;; 
val k : float -> float = <fun>

所以，h sin的结果是一个类型为float -> float的函数，这个函数可以作用到一个浮点数上：

# k 0.00001 ;; 
- : float = 0.999999999983333221

例1：把布尔值函数转变为整数值函数。

在1.6.1节，我们首先构造了一个布尔值的全加器，后来为了输入和输出的方便，又经过包装把它改变成一个整数值的全加器。如果要把每一个布尔值函数都进行这样的包装，显然比较繁琐。下面定义一个高阶函数，把一个任意的三元组输入、二元组输出的布尔函数包装成一个使用整数元组的函数：

# let pack_int f =
　let i2b i = if i=0 then false else true in
　let b2i b = if b then 1 else 0 in
　　function (a, b, c) ->
　　　let x, y = f ((i2b a), (i2b b), (i2b c)) in
　　　(b2i x), (b2i y) ;;
val pack_int :
　(bool * bool * bool -> bool * bool) -> int * int * int -> int * int = <fun>

这样我们就能自动地把包括全加器在内的任何一个三元组输入、二元组输出的布尔函数转变成一个整数函数，例如：

# let full_adderi = pack_int full_adder ;;
val full_adderi : int * int * int -> int * int = <fun>

# full_adderi (1, 1, 1) ;;
- : int * int = (1, 1)

例2：构造一个全加器测试函数，它的输入是一个全加器函数，要求遍历所有可能的输入，对每个输入用全加器函数进行计算，并打印出测试结果：

# let adder_testbench f =
　let ck a b c = 
　　let s, carry = f (a, b, c) in
　　　Printf.printf "%i,%i,%i => %i,%i\n" a b c s carry in
　　ck 0 0 0;
　　ck 0 0 1;
　　ck 0 1 0;
　　ck 0 1 1;
　　ck 1 0 0;
　　ck 1 0 1;
　　ck 1 1 0;
　　ck 1 1 1;;
val adder_testbench : (int * int * int -> int * int) -> unit = <fun>

局部定义的函数ck的输入是两个加数a、b和一个进位c，然后调用全加器函数f算出和s和进位carry，打印出“a,b,c => s,c”：

# adder_testbench full_adderi ;;
0,0,0 => 0,0
0,0,1 => 1,0
0,1,0 => 1,0
0,1,1 => 0,1
1,0,0 => 1,0
1,0,1 => 0,1
1,1,0 => 0,1
1,1,1 => 1,1
- : unit = ()

1.6.5　递归函数

循环是程序语言中的一个常用结构，但是纯函数式语言没有循环结构，需要通过循环完成的工作可以通过递归函数（recursive function）来完成。递归函数就是函数名在函数体内出现的函数。在OCaml语言中，递归函数也用let结构定义，但是要加上关键字rec。下面是递归函数定义的格式：

let rec <函数名> <参数1> … <参数n> = <表达式>

下面举一个递归定义阶乘函数的例子：

在OCaml中写作：

# let rec factorial n =
　　 if n = 0 then 1 else n * factorial (n - 1) ;; 
val factorial : int -> int = <fun>

# factorial 3 ;; 
- : int = 6

函数的递归定义和数学中的递归定义非常相似，递归定义的函数也可以像数学中的等式变换那样推导出运算结果，例如：

factorial 3 
= 3 * factorial 2 
= 3 * 2 * factorial 1 
= 3 * 2 * 1 * factorial 0 
= 3 * 2 * 1 * 1 
= 6

函数式程序便于做等式推导，这给程序的形式化验证带来了很大的便利。形式化验证就是用数学定理证明方法去证明一个软件的正确性。为了做到这一点，往往先要用一种数学性质良好的语言去描述软件。为此，很多软件系统的形式化验证都是先用函数式语言重写软件，然后在定理证明器中进行形式验证。例如，澳大利亚用形式化方法证明了一个操作系统SEL4的正确性。他们首先用函数式语言Haskell描述和实现了这个操作系统，然后在定理证明器Isabelle中证明这些描述的正确性。

前一节讲了无名函数，因为递归需要用到函数名，所以在OCaml中递归函数不能直接用无名函数的方式定义。

对于用递归方程定义的函数，在OCaml中特别容易实现。但是需要注意尽量减少递归次数，以提高计算效率。

例1：构造一个计算的函数，其中a是浮点数，n是整数。对于这个问题，常规的做法是利用方程组：

# let rec power_fun1 a n =
　　 if n = 0
　　 then 1.
　　 else power_fun1 a (n-1) *. a ;;
val power_fun1 : float -> int -> float = <fun>

# power_fun1 3. 5 ;;
- : float = 243.

对于参数n，这一解法的递归调用次数为n。如果用下面等式进行计算，每次递归调用把参数n除以2，就能把计算次数降低到log n。例如，取n=8，上面的解法需要8次递归，而下面的解法只需要3次递归：

# let sq x = x *. x ;;
val sq : float -> float = <fun>

# let rec power_fun2 a n =
　　 if n = 0
　　 then 1.
　　 else if (n mod 2 = 0)
　　　　　　 then sq (power_fun2 a (n/2))
　　　　　　 else a *. sq (power_fun2 a (n/2)) ;;
val power_fun2 : float -> int -> float = <fun>

# power_fun2 2. 8 ;;
- : float = 256.

例2：构造一个计算两个正整数的最大公约数的函数。

在编写递归函数求解数学问题时，在可能的情况下，首先把算法写成递归方程，然后再写递归函数。求解最大公约数的欧几里得算法可以写成：

# let rec gcd a b =
　if b=0
　then a
　else if a<b
　then gcd b a
　else gcd b (a mod b) ;;
val gcd : int -> int -> int = <fun>

# gcd 9 12 ;;
- : int = 3

例3：构造一个函数，使之能够判断整数是否为质数。

解决这个问题的算法需要用到两个参数i和incr，其中i是要判断的数，incr是一个循环变量，初值为2，每次递归调用时加一，直到大于i/2。用C语言编写需要循环的程序时，通常也引入辅助的循环变量，在循环开始时赋初值，并在每次循环时通过赋值语句更新循环变量。用纯函数式语言编写这类程序的一个技巧是通过额外的函数参数来引入循环变量，在函数调用时给这个变量赋初值，并在每次递归调用时更新循环变量。

解法一：引入辅助变量incr构造递归程序。

# let rec is_prime i incr =
　　 if i < 2 || i mod incr = 0
　　 then false
　　 else
　　　　if incr > i / 2
　　　　then true
　　　　else is_prime i ( incr + 1 ) ;;
val is_prime : int -> int -> bool = <fun>

# is_prime 997 2　;;
- : bool = true

在函数调用is_prime 997 2中，参数2相当于循环变量incr的初始值，在函数体内的递归调用is_prime i ( incr + 1 )中更新了循环变量，类似C语言中对循环变量的赋值更新：incr = incr +1。

然而，最终用户应该使用一个不含赋值变量的函数。为此，可以把上面的函数作为主函数中的一个辅助函数。

解法二：引入辅助函数，使得主程序中只包含一个输入变量。

# let is_prime i =
　let rec is_prime_aux i incr =
　　if i<2 || i mod incr = 0
　　then false
　　else 
　　　if incr > i / 2
　　　then true
　　　else is_prime_aux i (incr+1)
　　　in
　　　is_prime_aux i 2 ;;
val is_prime : int -> bool = <fun>

# is_prime (991 * 997) ;;
- : bool = false

1.6.6　相互递归函数

如果函数f1要调用函数f2，而且函数f2也要调用f1，那么这样的函数就是相互递归函数（mutually recursive functions）（也称联立递归）。一般情况下，我们可以定义任意多个相互递归函数。在OCaml中，相互递归函数的定义格式如下：

let rec <函数名1> <参数表1> = <表达式1> 
and　　 <函数名2> <参数表2> = <表达式2> 
... 
and　　 <函数名n> <参数表n> = <表达式n>

例如，我们可以用相互递归方法同时定义两个函数even和odd，一个判别偶数，另一个判别奇数：

# let rec even n = if n = 0 then true else odd(n-1)　　　 
and odd　n = if n = 0 then false else even(n-1) ;; 
val even : int -> bool = <fun> 
val odd : int -> bool = <fun>

相互递归函数的调用方法和一般的函数一样：

# even 3 ;;
- : bool = false

# odd 3 ;;
- : bool = true

在OCaml语言中，逻辑运算符&&和||是顺序计算的，在C和C++中也叫短路。如果e1为false，表达式“e1 && e2”就直接输出false，不会计算e2；如果e1为true，表达式“e1 || e2”就直接输出true，也不会计算e2。利用这一特性，上面的函数还可以进一步简化：

# let rec even n = n=0 || odd (n-1)
　and odd n = n<>0 && even (n-1) ;;
val even : int -> bool = <fun> 
val odd : int -> bool = <fun>

1.6.7　模式匹配表达式

模式匹配对复杂结构进行分解，从中提取出子部分。在讲乘积类型的1.5节中，我们已经接触了一种基于模式匹配的let定义：

let <模式> = <表达式1> in <表达式2>

如果已有定义let a = 1, 2, 3 ，那么有：

# let x, y, z = a in y ;;
- : int = 2

一般情况下，我们可以通过match-with结构构造一个模式匹配表达式。它不仅可以用于复杂结构的分解，而且也用于构造多条件分支结构，实现C语言中的switch语句的功能。但是switch并没有模式匹配的能力，因此match结构更加强大。它的一般格式是：

match <表达式> with 
　| <模式1> -> <表达式1> 
　| <模式2> -> <表达式2> 
　　　... 
　| <模式n> -> <表达式n>

其中，with后的第一个“|”可以省略，但之后的“|”必须存在。模式匹配从上到下顺序执行。<表达式>依次和各个模式匹配，对第一个成功匹配的<模式i>，执行它右边的<表达式i>，并且把执行结果作为match结构的输出。这些表达式的输出类型必须相同，这个类型也是整个match表达式的输出类型。编程时，最好让各个模式覆盖所有的可能性，如果有遗漏，OCaml也会给出结果，但会发出警告信息。

最简单的模式是常量，例如：

# let neg x =
　match x with
　　| true -> false
　　| false -> true ;;
val neg : bool -> bool = <fun>

模式可以使用通配符“_”，它用于匹配任意数据。

# let is_zero n =
　match n with
　　| 0 -> true
　　| _ -> false ;;
val is_zero : int -> bool = <fun>

输入的<表达式>可以是结构化类型，因此，模式也可以是结构化的。例如输入表达式是二元乘积类型，那么采用对偶模式。

# let xor z =
　match z with
　　　(false, false) -> false　　　　(* 第一个“|”可以省略 *)
　　| (false, true) -> true　
　　| (true, false) -> true 
　　| (true, true)　-> false ;;
val xor : bool * bool -> bool = <fun>

对于这个函数，类型系统从模式的结构自动分析出表达式z的类型是乘积类型bool * bool，因此xor的类型是bool * bool -> bool。

上面的函数使用了一个类型为对偶的变元，对于两个变元的函数也可以用模式匹配方式定义：

# let xor x y =
　match x,y with
　　　(false, false) -> false　 
　　| (false, true) ->true　
　　| (true, false) -> true 
　　| (true, true) -> false ;;
val xor : bool -> bool -> bool = <fun>

对于结构化的输入数据，通配符“_”可以用于匹配结构的任何一个子部分，也可用于匹配整个输入。

异或函数xor也可以改写为：

# let xor x y =
　match x,y with
　　　(false, false) -> false　 
　　| (true, true) -> false
　　| _, _ -> true ;;　　(* 通配符可以用于匹配任何一个子部分 *)
val xor : bool -> bool -> bool = <fun>

# let xor x y =
　match x,y with
　　　(false, false) -> false　 
　　| (true, true) -> false
　　| _ -> true ;;　　　　(* 通配符可以用于匹配任何一个子部分 *)
val xor : bool -> bool -> bool = <fun>

# let xor x y =
　match x,y with
　　　(false, u) -> u　　(* 在模式中可以使用变量 *)
　　| (true, u) -> not u ;;
val xor : bool -> bool -> bool = <fun>

模式中的变量是局部变量，它仅在本模式右端的表达式内有效。因此，在不同的模式中可以使用相同的模式变量，它们之间互不影响。但是，在同一模式中不能出现两个相同的变量，这样的模式称为线性模式。下面是一个违反线性模式的例子：

# let errxor x y =
　match x y with
　　| u, u -> false
　　| _, _ -> true ;;
　　　Characters 42-43:
　　　| u, u -> false
　　　　　 ^
Error: Variable u is bound several times in this matching

模式匹配要对所有情况全部覆盖，系统会自动分析模式匹配的完整性。在不完整的情况下会发出警告：

# let incomplete_neg x = 
　　match x with
　　　| false -> true ;;
　　Characters 28-62:
　....match x with
　　　　| false -> true..
Warning 8: this pattern-matching is not exhaustive.
Here is an example of a value that is not matched:
true
val incomplete_neg : bool -> bool = <fun>

系统会接受不完整的模式匹配表达式，但执行到未设置的条件时会产生错误：

# incomplete_neg true ;;
Exception: Match_failure ("//toplevel//", 303, 4).

运行时产生的错误信息有时并不完整，因此不容易进行错误定位。所以编程时要尽量避免不完整的模式匹配。

match表达式可以嵌套使用，此时需要给内嵌的match表达式加上括号，否则系统会把原本属于上一层match的模式误认为属于下一层match的模式，造成错误。下面是用嵌套match所写的xor：

# let xor x y =
　match x with
　　| false ->
　　(match y with
　　　 | false -> false
　　　 | true　-> true)
　　| true ->
　　(match y with
　　　 | false -> true
　　　 | true　-> false) ;;
val xor : bool -> bool -> bool = <fun>

对于字符类型数据，可以使用字符区间模式:

<字符>..<字符>

例如：

# let f (c:char) : string =
　match c with
　　| '0'..'9' -> "digit"
　　| 'a'..'z' -> "lowercase char"
　　| 'A'..'Z' -> "uppercase char"
　　| _　　　　-> "other char";;
　　　　　val f : char -> string = <fun>
# f '3';;
- : string = "digit"

模式匹配表达式有一种扩展形式，就是在模式之后加入一个可选的when表达式：

match <表达式> with 
　| <模式1> [when <条件1>] -> <表达式1> 
　| <模式2> [when <条件2>] -> <表达式2> 
　　　... 
　| <模式n> [when <条件n>] -> <表达式n>

要激发形如“<模式i> [when <条件i>]”，除了表达式要同<模式i>匹配之外，还要去表达式满足<条件i>。

作为一个例子，我们用when来定义xor:

# let xor x y = 
　match x,y with
　　| _,_ when x=y -> false
| _,_ -> true ;;
val xor : 'a -> 'a -> bool = <fun>

能够用match完成的工作通常也能够用条件语句完成，但是match的执行速度更快。

1.7　多态类型

目前，我们所使用的函数类型都是“单态”的，也就是说，函数参数的类型和输出值的类型都是固定的。可是，有些函数的行为与其参数的类型无关，它们可以作用在不同类型的参数上。例如，前面提到的fst函数，它返回一个对偶的第一个元素。它与对偶分量的类型无关，无论哪种类型的对偶都可以使用。例如(1, true)属于int * bool类型，(2.3, 1)属于float * int类型。因此，fst函数既具有int * bool -> int类型，又具有float * int -> float类型。实际上，fst函数具有无穷多的类型，只要这些类型具有A * B -> A这样的形式即可。这种函数称为多态函数，所具有的类型称为多态类型。

1.7.1　类型变量

为了描述多态类型，需要引入类型变量，也就是取值为类型的变量。多态类型就是类型中包含类型变量的类型，多态函数是具有多态类型的函数。多态类型代表了一组类型（实际上是无穷多的类型）。fst函数是一个具有多态类型的函数：

# fst ;;
- : 'a * 'b -> 'a = <fun>

为了区别于其他变量，OCaml语言中的类型变量都用以单引号“'”开头的变量表示，'a和'b都是类型变量。fst的类型显示，它的输入参数是由任意类型'a和任意类型'b所构成的二元乘积类型，函数输出必须和这个乘积类型的第一个类型'a相同。

对于表达式fst (1, true)，系统首先分析出这个对偶具有int * bool。然后在fst的类型'a * 'b -> 'a中把'a代换成int，把'b代换成bool，得到类型int * bool -> int，从而得到fst (1, true)的类型是int。

在类型分析的时候，要把多态类型中的类型变量替换成合适的类型，这个过程称为类型的例化。例如，在表达式fst (1, true)中，fst函数的类型例化为：int * bool -> int。在对多态类型的学习过程中，需要了解多态函数中的多态类型是怎样例化的。

# fst ((1.2, (false, 3)), "ok") ;;
- : float * (bool * int) = (1.2, (false, 3))

这里，fst类型例化成：(float*(bool*int))*string-> float*(bool*int)

类型变量不仅可以代换成具体类型，而且可以代换成多态类型。

# fst ((function x -> x), 1) ;;
- : '_a -> '_a = <fun>

这里，fst的类型例化为(('_a ->'_a) , int) -> ('_a->'_a)。这里类型变量中的下划线并没有特殊的意思，只是可用于构造类型变量的合法符号之一。

取对偶的第二个分量的函数snd也是多态函数：

# snd ;;
- : 'a * 'b -> 'b = <fun>

用户可以自定义多态类型的函数。例如：

# let get_middle (x, y, z) = y ;;
val get_middle : 'a * 'b * 'c -> 'b = <fun>

系统会根据函数的形式自动推导出它的多态类型。

一个常见的多态类型函数是复制函数id。

# let id = fun x -> x ;;
val id : 'a -> 'a = <fun>

# id 3 ;;
- : int = 3

# (id id) (id 3) ;;
- : int = 3

最后一个表达式中有3个id，它们各自例化成不同的类型。为了说明其中的类型分析过程，我们从最后一个id开始考察，它的类型例化为int->int，id 3的类型是int，因此(id id)的类型例化为int->int，从而第二个id的类型也例化为int->int。最后得到第一个id的类型例化结果是：(int->int)->(int->int)。

下面的高阶函数compose用于构造两个函数的复合函数：

# let compose (f, g) = fun x -> f (g x) ;;
val compose : ('a -> 'b) * ('c -> 'a) -> 'c -> 'b = <fun>

# let square x = x * x ;;
val square : int -> int = <fun>

# in compose (square, square) 3 ;;
- : int = 81

前面讲过，对于两个变量的函数，有两种写法，第一种写法是使用两个参数，例如“let f x y =…”，第二种是使用一个对偶参数，例如“let f (x,y) = …”。第一种写法的函数类型形如“A->B->C”，第二种写法的函数类型形如“A*B->C”。下面定义的curry函数把第二种函数转换成第一种函数：

# let curry f = fun x -> fun y -> f (x, y) ;;

下面分析curry函数的类型。curry函数带有一个参数f。等号右边的“fun x -> fun y -> f (x, y)”是一个无名函数，函数参数是x，函数的输出“fun y -> f (x, y)”也是一个无名函数，这个函数的参数是y，输出是“f (x, y)”，由此得出，参数f是一个函数，它的输入参数是对偶类型。虽然推导到这里仍旧看不出x和y的类型，但是我们可以暂时用变量类型表示x和y的类型，即假设x的类型是“'a”，y的类型是“'b ”，其中'a 和 'b可以代表任意的类型，f作用在(x, y)后的结果也用变量类型表示为“'c”。

综上所述，参数f的类型是'a * 'b -> 'c，参数x的类型是'a，参数y的类型是'b，f(x, y) 的类型是'c。最后得出函数curry的类型是一个多态类型：('a * 'b -> 'c) -> ('a -> 'b -> 'c) 。

最后我们在OCaml中测试一下推导的结果：

# let curry f = fun x -> fun y -> f (x, y) ;;
val curry : ('a * 'b -> 'c) -> 'a -> 'b -> 'c = <fun>

# curry fst ;;
- : '_a -> '_b -> '_a = <fun>

1.7.2　类型推导

表达式本身不含类型信息，OCaml的类型系统能够从表达式出发自动推导出表达式的类型，这个过程称为“类型推导”（type inference）或“类型合成”（type synthesis）。如果类型推导过程失败，说明这个表达式存在类型不匹配问题，OCaml会给出一个类型错误信息。如果表达式e的类型为tp，则记为e:tp。

类型推导要解决的第一个问题是怎样表示一个表达式的类型。前面已经看到，一个表达式可以有很多类型。例如fun (x,y) -> x的类型有int*float -> int，('a *int) *string -> 'a*int等。但是，我们不需要把一个函数的所有类型全都列举出来，只需要写出它的最通用的类型（most general type）即可。

一个类型tp称为一个表达式e的最通用类型当且仅当e的所有类型都可以通过对tp中的类型变量做类型替换得到。例如，fun (x,y) -> x最通用的类型是'a*'b -> 'a。如果，把'a换成int，'b换成float，可以得到int*float->int，把'a换成'a*int，'b换成string，可以得到('a *int) *string -> 'a*int。在变量替换过程中，可以把类型变量替换成一个具体类型表达式，也可以替换成一个多态类型。

一个表达式的最通用类型代表了这个表达式的所有类型。OCaml推导出的类型是最通用的(most general)。

下面以compose函数为例，直观地说明类型推导过程。首先，我们把compose的定义改写成let <函数名> = <函数表达式>的形式。由此得到compose所关联的函数表达式为，它包含了3个变量f、g和x。我们暂且称它们的类型为，和。

因为g作用于x，可以推断是形如的类型，由此得出表达式的类型是。又因为f作用于，我们推断是形如的类型，这样表达式的类型就是。由此得到表达式的类型是，且表达式的类型是。

类型推导算法的基础是归一算法（unification algorithm）。它的主要思路是列出表达式的类型所需要满足的一组类型等式，也称类型约束（constraints），然后用归一算法求解。算法细节在其他地方详细介绍。

类型推导的一个难点是同一变量会在表达式中多次出现。在这种情况下，对变量的每次出现都会推导出一个类型。对于由fun或function所引入的变量，如果同一变量的不同出现具有不相容的类型，那么类型推导会失败，并报出错误信息。例如，在表达式(fun f -> f 1, f true)中f出现了两次，第一次输入参数的类型是int，第二次输入参数的类型是bool，也就是说，f的类型要用两个类型来表示: int->'a和bool->'a。然而，OCaml的类型系统只能为每个表达式推导出一个通用类型，其他类型要从这个通用类型经过变量替换得到。前面的类型推理过程达不到这一要求，因此，OCaml系统无法接受这一表达式，就会产生类型错误：

# fun f -> f 1, f true ;;
Characters 16-20:
　fun f -> f 1, f true ;;
　　　　　　　　　^^^^
Error: This expression has type bool but an expression was expected of type
　　　　 int

这里，类型系统首先从子表达式f 1分析出f的类型是int -> int，然后它假设第二个子表达式f true中f的类型也是int -> int，再检查它的参数true，发现参数的类型是bool，不是int，因此认为存在类型错误。

上面的分析是针对以fun函数方式引入的变量。如果一个变量以let定义的方式引入，那么它的多次出现可以具有不同的类型。

在表达式的类型推导过程中，要确定每一个变量的类型。在有些表达式中，一个变量可以在多个位置出现，不同位置上的变量具有不同的类型。例如，在表达式let f = fun x -> x in (f 1, f true)中的f。首先，从f = fun x -> x中得到f的类型是多态类型'a->'a，然后对这个多态类型做两次例化，通过f 1得到f : int->int，通过f true得到f : bool->bool。整个表达式最终的类型是int*bool。

在第二个例子和第一个例子中有一个相同的子表达式(f 1, f true)，f在其中出现了两次。为什么第一次类型推导失败，而第二次的类型推导就成功呢？原因是两个f所包含的信息不同，在第一个例子中的f不包含定义信息，只能通过f的应用过程去分析f的类型。第二个例子通过let引入了函数f的具体实现，能够获得f的定义，由此能够推断出f是一个多态类型。第二个例子等价于用表达式((fun x -> x) 1, (fun x -> x) true)替换let id = fun x -> x in (id 1, id true)，两个子表达式(fun x -> x) 1和(fun x -> x) true都能独立推断类型。

1.8　λ演算对函数式语言的影响

函数式语言起源于演算。演算结构简单，但可以清晰地说明和分析函数式语言中的许多概念。原始的[\lambda ]演算通过3种方式构造表达式（假设e是一个表达式）。

1）变元：。

2）抽象(abstraction)：。

3）应用(application)：。

抽象简称抽象。就是函数表达式function x -> e。起到函数调用（function call）的作用，但是在演算中称为“应用”(application)，有时也写做“作用”。

这里的可以看成是单参数函数。多参数函数通过多层抽象来实现。例如，，相当于function x -> function y -> e。多变元函数调用可以通过多重应用实现，例如。左结合的应用可以去掉括号，即表达式应用左结合：

OCaml沿用了这一规则。函数应用包含两个表达式，其中和都可以是抽象，所以函数可以作为其他函数的参数。

演算通过一些简单的规则来表示计算的过程。最主要的规则是归约（-reduction），它把函数作用过程用变量替换来表示：

记号表示：表达式中的所有变量x都用表达式替换。例如：

左边的表达式中，函数作用到另一个函数上。作用结果是把第一个函数的函数体中的x替换成第二个函数。这是高阶函数的一个最简单的例子。归约反映了高阶函数的基本计算过程。所以演算是高阶函数的抽象模型。

let-in结构实际上是一种特殊的表达式：

从一个表达式出发，经过多次归约，会得到一个不可归约的表达式，形如。这个表达式在演算中称为值（value），这个计算过程称为求值。归约是一个函数式语言的基本计算步骤。

理论上，演算可以模拟任何计算。可以用表达式对自然数编码，对各种数据结构编码，以及对可计算函数编码，从而模拟任何计算。在计算能力方面，演算等价于图灵机。这方面的内容远远超出了本书的范围。在学习OCaml的时候也不需要对此深究。

为了进行有实际意义的计算，在演算中加入了一些“常数”。这些常数即包括整数、实数、布尔量等基本数据，也包括各种预定义的函数名，例如加法函数、乘法函数等。预定义函数的计算规则称为规则，计算过程称为归约。例如：

在演算的基础上加上类型，就构成带类型的演算。类型推导问题可以在带类型的演算中进行研究。

如果一个表达式e具有类型，则记为。纯演算中，基本类型由类型变量、类型常量和箭头类型组成。类型表达式中的括号是右结合的，即

OCaml沿用了这一规则。

带类型的演算中引入了多种结构类型。其中最基本的就是乘积类型，其中的元素是对偶。

函数作用的优先级最高，同时逗号的优先级最低。例如：

# sqrt 9. *. 4. ;;
- : float = 12.

# sqrt (9. *. 4.) ;;
- : float = 6.

# true || false, 3+2, sqrt 25. ;;
- : bool * int * float = (true, 5, 5.)

从纯演算发展到函数式语言，需要进行一系列的扩展。在此不再详述。

1.9　中缀操作符与前缀操作符

算术运算中用到多个中缀操作符，例如“+”和“*”等。这些操作符也是函数，但是它们不能像其他函数表达式一样使用。例如，中缀操作符本身不是一个值，而且它们也不能作为函数的参数：

# + ;;
Characters 1-3:
　+ ;;
　　^^
Error: Syntax error

# (function x -> x) + ;;
Characters 17-19:
　(function x -> x) + ;;
　　　　　　　　　　 ^^
Error: Syntax error

OCaml提供了一种把中缀操作符改为前缀操作符的方法，即在操作符外面加上括号，这样得到的前缀操作符可以像其他函数一样使用：

# (+) ;;
- : int -> int -> int = <fun>

# (function x -> x) (+) ;;
- : int -> int -> int = <fun>

这一做法有一个例外，就是乘法符号。由于OCaml的注释从“(*”开始到“*)”结束，因此直接使用“(*)”会出错，需要在“*”两端加上空格。

# (*) ;;
File "", line 1, characters 0-3:
Error: Comment not terminated

# ( * ) ;;
- : int -> int -> int = <fun>

OCaml也允许用户定义中缀操作符。它们必须由特殊字符（=，<，>，@，^，|，&，+，-，*，/，$，%）构成，定义函数时在符号之外加上括号。例如，使用中缀记号法表示函数复合（composition），即将函数和复合为。可以定义一个中缀操作符“@@”。

# let (@@) f g = fun x -> f (g x) ;;
val (@@) : ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b = <fun>

# (not @@ not) true ;;
- : bool = true

1.10　同构函数和柯里化

两个函数f和g为同构函数（isomorphic function）当且仅当存在两个函数h和k，使得h(f)=g，k(g)=f，并且k @@ h = id，h @@ k = id。函数h、k称为同构映射。可以认为同构函数本质上相同。下面两个函数是同构函数：

# let f = fun (x, y) -> x + 2 * y ;;
val f : int * int -> int = <fun>

# let g = fun x y -> x + 2 * y ;;
val g : int -> int -> int = <fun>

这两个函数都含有两个输入参数x和y，函数体相同，只是参数定义方式不同。

可以定义一个函数curry，把多参数函数转变为单个元组参数的函数，这个过程也称为“柯里化”；还可以定义curry的逆函数uncurry，把单个元组参数的函数转变为多参数函数。即curry把类型为“'a * 'b -> 'c”的函数转变成类型为“'a -> 'b -> 'c”的函数，uncurry则把类型为“'a -> 'b -> 'c的函数转变成“'a * 'b -> 'c”类型的函数。

# let curry f x y = f (x, y) ;;
val curry : ('a * 'b -> 'c) -> 'a -> 'b -> 'c = <fun>

# let uncurry f (x, y) = f x y ;;
val uncurry : ('a -> 'b -> 'c) -> 'a * 'b -> 'c = <fun>

有了这两个函数，就能够说明函数f和函数g是同构函数，即curry f = g，uncurry g = f。所以curry和uncurry构成一对同构映射。

下面的perm和perm'也是同构映射。它们把一个函数的两个参数位置对调。

# let perm f (x, y) = f (y, x) ;;
val perm : ('a * 'b -> 'c) -> 'b * 'a -> 'c = <fun>

# let perm' f x y = f y x ;;
val perm' : ('a -> 'b -> 'c) -> 'b -> 'a -> 'c = <fun>

1.11　循环迭代函数

在包括C语言在内的所有命令式语言中都有循环语句，它是绝大部分程序语言中的基本结构。由于OCaml提供了递归和高阶函数，因此可以定义出循环迭代函数。

C语言中的for语句主要用于构造具有固定迭代次数的循环。下面定义一个迭代函数iteration，能够起到类似的作用。它具有n和f两个参数，其中，f是一个单参数函数，它的输入类型和输出类型相同，n是整数，表示迭代次数。iteration n f表示函数，即把f迭代n次。

# let rec iteration n f =
　　if n = 0
　　then fun x -> x 
　　else f @@ (iteration (n-1) f) ;;
val iteration : int -> ('a -> 'a) -> 'a -> 'a = <fun>

iteration的类型分析过程如下。关键字rec说明iteration是递归函数，该递归函数带有两个参数n和f。if条件中的n = 0说明n是int类型。then分支上只有一个fun x -> x函数，它的类型为'a -> 'a，所以then分支类型是'a -> 'a。由于then分支和else分支的类型必须相同，所以要检查then分支是否也具有类型'a -> 'a。else分支是两个函数f和iteration (n-1) f的复合，因此f的输入类型同iteration (n-1) f的输出类型必须一致，而且f的输出类型也必须同iteration的输出类型一致。由此可以推断，f和iteration (n-1) f的类型都是'a -> 'a。综上所述，参数n的类型是int，参数f的类型是'a -> 'a，函数iteration的类型是int -> ('a -> 'a) -> 'a -> 'a。

# iteration 4 (fun x -> x * x) 2 ;;
- : int = 65536

我们也可以引入一个参数x作为迭代的初始值重新定义这个函数。

# let rec iteration n f x =
　　if n = 0
　　then x
　　else f (iteration (n-1) f x) ;;
val iteration : int -> ('a -> 'a) -> 'a -> 'a = <fun>

例1：定义一个以线性时间计算斐波那契数的函数。

斐波那契数的递归定义是：

直接根据这个定义进行的斐波那契数的计算会导致指数级的计算时间。如果在两个连续的斐波那契数的对偶上进行迭代计算，就可以得到一个线性时间的计算过程：

此处函数f将对偶(x, y)映射到对偶(x+y, x)。下面根据这一算法借助iteration定义fib函数：

# let fib n = fst (iteration n (fun (x, y) -> (x+y, x)) (1, 0)) ;;
val fib : int -> int = <fun>

# fib 50 ;;
- : int = 1037658242

C语言中另一种常用的循环是while循环。它不使用固定的迭代次数控制循环，而是通过判断循环终止条件进行循环控制，从而实现一种不确定循环次数的循环（for语句虽然也能实现这种循环方式，但以迭代循环为主）。下面定义的loop函数，它的第一个参数p是一个谓词（predicate），作用是判断循环终止条件，当判断结果为真时，停止循环，否则循环继续；第二个参数f是循环体内进行的计算；第三个参数x是循环初始值。这个函数的作用大致相当于C代码：

y = x; while (not p(y)){ y = f(x); } 

# let rec loop p f x = if (p x) then x else loop p f (f x) ;;
val loop : ('a -> bool) -> ('a -> 'a) -> 'a -> 'a = <fun>

不确定循环次数的循环比固定迭代次数的循环更为通用，后者实际上是前者的特例。实际上，我们能够用loop函数来构造iteration函数：

# let iteration n f x = snd (loop (fun (p, x) -> n = p)
　　　　　　　　　　　　　(fun (p, x) -> (p+1, f x))
　　　　　　　　　　　　　(0, x)) ;;
val iteration : int -> ('a -> 'a) -> 'a -> 'a = <fun>

例2：已知在区间上的连续单调函数f，和符号相反，用二分法找函数f的一个根。二分法是一个循环求解过程，每次循环计算区间中点处的函数值，并选取与中点处函数值异号的端点，由该端点和中点构成新的子区间，再进入下一次循环，循环体用函数do_better实现。循环的终止条件是区间宽度小于一个预定的小数，终止条件的判别用函数is_ok实现。每次循环区间宽度减半。找到解的迭代次数接近于。下面给出二分法函数dicho（dichotomy的缩写）的定义。

# let dicho (f, a, b, epsilon) =
　let is_ok (a, b) = abs_float (b -. a) < epsilon in
　let do_better (a, b) = 
　　let c = (a +. b) /. 2.0 in
　　　if (f a) *. (f c) > 0. 
　　　then (c, b)
　　　else (a, c)
　in
　　loop is_ok do_better (a, b) ;;
val dicho : (float -> float) * float * float * float -> float * float = <fun>

下面是通过求函数的根求解π的近似值的例子。

# dicho ((fun x -> cos (x /. 2.)), 3.1, 3.2, 1e-10) ;;
- : float * float = (3.1415926535613838, 3.1415926536545165)

例3：假设有可导函数f，在给定区间上和符号相反，如果f'和f''不为零且有恒定的符号（即函数连续并且待求的零点是孤立的）用牛顿迭代法（Newton’s Method）求f在区间的零点。

解：假设是函数f上的一点。若，那么函数f在点处的切线交x轴于。在牛顿迭代法中，我们用进行迭代。根据已有的数学定理，在题目条件下，区间上牛顿迭代法必定收敛。

首先我们定义一个函数deriv，它的输入是一个函数f和一小段时间间隔dx，输出是一个近似导函数。

# let deriv (f, dx) x = (f(x +. dx) -. f(x)) /. dx ;;
val deriv : (float -> float) * float -> float -> float = <fun>

牛顿迭代法函数定义如下：

# let newton (f, start, dx, epsilon) =
　　 let f' = deriv (f, dx) in
　　 let is_ok x = abs_float (f x) < epsilon
　　 and do_better x = x -. f x /. f' x in
　　 loop is_ok do_better start ;;
val newton : (float -> float) * float * float * float -> float = <fun>

例如，要求的近似值，可以用牛顿迭代法求余弦函数在1.5附近得到的的近似解再乘以2得到。

# newton (cos, 1.5, 1e-10, 1e-10) *. 2. ;;
- : float = 3.14159265360829

同样，我们可以对函数log(x)-1在2.7附近使用牛顿迭代法，求出e的近似解。

# newton ((fun x -> log x -. 1.), 2.7, 1e-10, 1e-10) ;;
- : float = 2.718281828459046

例4：广义求和。本例探讨怎样构造函数进行连加和连乘的计算。第一种方式是直接构造。例如，sigma函数计算了函数f在区间[a,b]上的值：

# let rec sigma f (a, b) =
　　 if a > b then 0
　　 else (f a) + sigma f (a+1, b) ;;
val sigma : (int -> int) -> int * int -> int = <fun>

由于连加和连乘两种计算很相似，可以构造一个通用函数summation，然后通过参数代换得到连加和连乘函数。summation的第一个参数是(incr, test)，它们分别用于变量增值和判断什么时候停止递归。第二个参数是对偶(op, e)，它们给出了基本的累计函数和累计开始时的初始值。

# let rec summation (incr, test) (op, e) f a =
　　 if test a then e
　　 else op (f a) (summation (incr, test) (op, e) f (incr a)) ;;
val summation :
　('a -> 'a) * ('a -> bool) ->
　('b -> 'c -> 'c) * 'c -> ('a -> 'b) -> 'a -> 'c = <fun>

在整数区间上增量为1的求和函数summation_int可以表示为：

# let summation_int (op, e) f a b =
　　 summation ((fun x -> x + 1),(fun x -> x > b)) (op, e) f a ;;
val summation_int : ('a -> 'b -> 'b) * 'b -> (int -> 'a) -> int -> int -> 'b = <fun>

根据上面的函数，我们也可以构造出参数f的类型是(int -> float)的函数和。

# let sigma = summation_int ((+.), 0.) ;;
val sigma : (int -> float) -> int -> int -> float = <fun>

# let pi = summation_int (( *. ), 1.) ;;
val pi : (int -> float) -> int -> int -> float = <fun>

注意，上段代码中的“( *. )”部分，“(”和“*”间一定要有空格，不然系统会认为是注释的开始，会一直等到输入“*)”退出注释。

我们可以使用函数pi定义阶乘函数n !。

# let fact = pi float_of_int 1 ;;
val fact : int -> float = <fun>

# fact 10 ;;
- : float = 3628800.

最终，得到数列的部分和。

# sigma (fun n -> 1.0 /. fact n) 0 20 ;;
- : float = 2.7182818284590451

在一段浮点区间上，增量为的求和函数可以表示为：

# let sum (op, e) f a b dx =
　　 summation ((fun x -> x +. dx), (fun x -> x > b)) (op, e) f a ;;
val sum :
　('a -> 'b -> 'b) * 'b -> (float -> 'a) -> float -> float -> float -> 'b =　<fun>

在上述函数的基础上，我们可以得到一个数值积分函数（numeric integration function），如下：

# let integrate f a b dx =
　　 sum ((+.), 0.) (fun x -> f(x) *. dx) a b dx ;;
val integrate : (float -> float) -> float -> float -> float -> float = <fun>

# integrate (fun x -> 1. /. x) 1. 2. 0.001 ;;
- : float = 0.69389724305995926

1.12　本章小结

OCaml语言是由Caml语言发展而来的。本章介绍了OCaml语言的核心部分，同时也是Caml语言的核心。经过多年发展，OCaml在语法方面做了不少改变，例如Caml中原来有一种where结构，现已不复存在。因此，很多Caml程序在OCaml中不能运行。但语言核心的本质性结构依旧保留。

OCaml语言的理论基础是带类型的演算。OCaml表达式把传统语言中的表达式、语句和程序融合在一起。本章介绍了算术表达式、逻辑表达式以及函数调用（在OCaml中称为application，译作“作用”或“应用”）表达式。OCaml表达式的内涵比命令式语言表达式更为丰富，尤其是把函数抽象也作为一种表达式；甚至，传统的条件语句、顺序执行语句、打印语句以及后面章节将要介绍的各种语句都是表达式。此外，还有模式匹配表达式match。

表达式都能进行计算，也就是求值。表达式计算的过程来源于演算中的归约。归约过程就是把一些归约规则作用于表达式并且产生新的表达式，类似于代数中的等式推导。如果归约到一个再也不能归约的表达式，就称这个表达式为值。归约过程可能不终止，这种情况相当于函数调用时的无穷递归。在写递归函数的时候，要注意防止无穷递归。如果递归过程过长，OCaml会把计算过程强行终止并报告stack_overflow的错误。

表达式的一个重要特征是具有“值”和类型。不仅传统的数据是值，而且函数也是一种值，甚至语句也有值“()”。

因为函数是值，所以函数就可以作为其他函数的参数，也可作为表达式的计算结果，这就是高阶函数。此外，可以用let定义把变量和函数表达式相关联，建立函数定义。递归函数要用let rec结构定义。let和and组合可以对变量进行并行定义或建立相互递归函数定义。

每种值都有类型。本章介绍了基本的数据类型：int、float和bool。OCaml中的浮点类型比较特殊，浮点数都必须包括一个“.”，所有的浮点运算符也必须带有“.”作为后缀。语句类型unit是用于输入和输出的类型。字符串在OCaml语言中是一种基本类型。在预定义类型的基础上，能构造几种构造类型。本章介绍了其中的两种，一种是乘积类型，其元素是对偶和元组。另一种是函数类型。之后还会介绍更多类型。

有些函数具有多态类型。多态类型是包含了类型变量的类型。它表示一个类型的集合。多态类型函数可作用于不同类型的数据。

OCaml语言的一个重要特点是具有类型推导能力。对于一个表达式，OCaml的类型推导系统能够自动推导出它最通用的类型，一个函数的最通用的类型可以通过类型代换得到该函数的任意一个类型。本章通过一些具体例子描述了类型推导的原理。

1.13　练习

1．请问下面的代码是否正确？如果不正确，解释原因；如果正确，指出运行结果：

let　a = 1　and 
let　b = 2　and 
let　c = 3 
in 
let d = a+b+c in 
　d;;

2．请问下面的代码是否正确？如果不正确，解释原因；如果正确，指出运行结果：

 (let a = 1 in a + 2) * (let b = 2 in b + 2);;

3．请问下面的代码是否正确？如果不正确，解释原因；如果正确，指出运行结果：

let a = 1 and 
　b = 
　 let a = 2 in a + a and 
　 c = 3 
in 
let d = a+b+c in 
　d;;

4．请问下面的代码是否正确？如果不正确，解释原因；如果正确，指出运行结果：

0x1 + 0b1 + 0B1 + 0x1 + 0_1 ;;

5．请问下面的代码是否正确？如果不正确，解释原因；如果正确，指出运行结果：

(if false then true else true) < true;;

6．请问下面的代码是否正确？如果不正确，解释原因；如果正确，指出运行结果：

let a = 1 and b = 2;; 
if a<b then 
　let a = 3 
else 
　let a = 4;;

7．请问下面的代码是否正确？如果不正确，解释原因；如果正确，指出运行结果：

if true then 1<2;;

8．请问下面的代码是否正确？如果不正确，解释原因；如果正确，指出运行结果：

"Lemma" + 1;;
'x' + 1;;
"Lemma" ^ '1';;

9．下面的程序是否有类型错误？如果有，请指出错误位置并解释原因：

let a = "hello" in 
let a = 2 in 
　a + "world";;

10．下面的程序是否有类型错误？如果有，请指出错误位置并解释原因：

let a = 1 and b = 2． in 
let c = b + 3.0 in 
let d = a + 1.0 in 
 c + d;;

11．下面的程序是否有类型错误？如果有，请指出错误位置并解释原因：

int32.zero + int32.one;; 

1E0 +．1e0 +．1e(-1);;

12．分析下列表达式的类型，并验证答案。

1）

2）

13．请给出下面两个表达式的计算结果：

let a = 1．in 
　float_of_int (int_of_float a ) = a;; 

let a = 1. in 
　float_of_int (int_of_float a ) == a;;

14．假设a为int型的整数，下面的表达式是否永远成立？

a < a + 1;;

15．用二元组实现复数，定义复数的加、减、乘、除运算。

16．用元组实现3×3实数矩阵，实现下列矩阵操作：

• 矩阵转置。
• 矩阵加法。
• 矩阵乘法。
• 矩阵的行列式。
• 转置伴随矩阵。
• 逆矩阵。

17．用4个全加器构造一个四位加法器。

18．设计一个针对全加器的通用测试函数FullAdderTest，它的第一个参数是全加器函数，第二个参数是所有测试输入所构成的一个元组，第三个参数是对每个输入所对应的预期输出。通用测试函数把全加器作用到每个输入上，然后同预期输出对比。如果所有测试都通过，打印“all tests passed”，否则打印出现错误的所有输入。写出这一函数的类型。

19．写一个针对四位加法器的通用测试函数，并测试四位加法器函数，分析这个测试函数的类型。

20．写一个针对由8个元素构成的元组的通用排序函数sort_tuple8，它的第一个参数是8个元素的元组，第二个参数是一个比较函数compare，它满足下述条件：

分析这个函数的类型。

21．分析下面表达式中compose函数的类型例化。

　 let add1 x = x+1 in compose (add1, id) 2 ;;