值,类型及其他玩意儿

2.1 值和类型

Haskell是一门纯粹的函数式编程语言(purely functional language),因此,所有计算都是通过对表达式(expression)进行求值来完成的。

每个值都有相应的类型,比如说,对于原子型值(atomic values),有数字值(integer)5,字符值(character)'a',以及函数(function)x -> x+1,等等;而对于结构型值(structured values),则有列表(list)如[1, 2, 3],或点对(pair)('b', 4),等等。

正如表达式定义了值一样,类型表达式(type expression)也定义了类型值(type value),或者简单点说,类型表达式定义了类型(type)。

以下是一些类型表达式的例子:对于原子型值,有Integer类型,表示无限精度(infinite-precision)的数字值;Char类型,表示字符值;Integer->Integer,表示函数从Integer类型映射(mapping)到Integer类型,等等。

而对于结构型值,则有[Integer]类型,表示一个只包含数字值的列表;以及(Char,Integer)类型,表示一个由字符值和数字值组成的点对;等等。

在Haskell中,所有的值都是第一类的(first-class)——它们可以作为参数被传入到函数,作为计算结果而被返回,或是放置在(placed in)数据结构中,诸如此类。

另一方面,Haskell的类型,是第一类的。

类型指派

类型可以在某种程度上描述值,而为值关联相应的类型称之为类型指派(typing)。

用我们之前举过的类型和值为例,以下是一些类型指派的例子:

::

  1. 5 :: Integer
  2. 'a' :: Char
  3. inc :: Integer -> Integer
  4. [1, 2, 3] :: [Integer]
  5. ('b', 4) :: (Char, Integer)

其中::符号可以读作“值。。。的类型是。。。”,比如,我们可以将5 :: Integer读作“值5的类型是Integer”,或者,再简单点,直接说:“数字值5”。

函数定义

在Haskell中,函数一般通过一系列方程(equation)来定义(define)。

比如函数inc可以用以下这条方程来定义:

::

  1. inc n = n+1

其中,方程是声明(declaration)的首个例子,另一种声明称之为类型签名声明(§4.4.1 <http://www.haskell.org/onlinereport/decls.html#type-signatures>_)(type signature declaration),可以用于对函数进行显式的类型指派。

比如说,我们可以使用类型签名声明,为inc函数指派类型Integer -> Integer

::

  1. inc :: Integer -> Integer
  2. inc n = n+1

我们将在第三章中介绍函数定义。

求值

当我们希望在数学上表示对一个表达式:math:e_1求值,从而得到另一个表达式(或值):math:e_2的时候,我们会使用符号:

:math:e_1 \Rightarrow e_2

比如,像这样:

::

  1. inc (inc 3) => 5

静态类型系统

Haskell的静态类型系统(static type system)定义了类型和值之间的形式关系(§4.1.4 <http://www.haskell.org/onlinereport/decls.html#type-semantics>_(formal relation),它确保Haskell程序都是类型安全(type safe)的,也即是说,Haskell程序不会遇上类型不匹配(mismatch type)的问题。

举个例子,我们不能对两个字符串进行加法操作,因为表达式'a'+'b'类型不合法(ill-type)的。

众所周知,静态类型的主要好处是可以在编译期间(compile-time)发现类型错误,帮助用户理解程序,并生成更高效的执行码。

当然,类型系统不能发现所有的错误,比如表达式1/0就是类型合法(typable)的,但执行这个表达式却会引发一个错误。

另一方面,类型系统还必须保证用户显式指派的类型的正确性。而实际上,除少数几种状况之外,强大的Haskell允许我们省略一切类型签名,类型系统能为我们推导(infer)出正确的类型。

尽管如此,对像是inc那样的函数使用类型签名也没什么坏处,毕竟除了指定类型之外,类型签名还有文档化和增强可读性的作用。

.. note::

  1. 请注意,我们对类型标识符使用了首字母大写的形式,像是`Integer``Char`,但对于值,则使用了小写形式,如`inc`
  2. 这不仅仅是一个约定俗成的规矩那么简单,而是Haskell语法所强制要求的。
  3. 实际上,Haskell中的标识符是区分大小写的,`foo``fOo``fOO`代表完全不同的标识符。

2.2 多态类型

Haskell同样也引入了多态类型(polymorhpic type),它们某种程度上是对所有类型的全局量化(universally quantify)。

多态类型表达式主要用于描述类型的系(family)。

举个例子,[a]是一个系,该系表示对任何类型a来说,[a]是包含a类型的一个列表。

比如说,[1, 2, 3]就是一个包含数字值的列表,而['a', 'b', 'c']则是一个包含字符值的列表,甚至可以有包含数字值列表的列表,等等。

再比如说,表达式[2, 'b']就不是一个合法的例子,因为一个列表没有办法同时储存两种不同类型的值,换句话说,它们不能用[a]表示。

.. note::

  1. 在前面的例子中,我们用小写字母`a`表示**类型变量**(type variable),以便和特定的类型如`Int`区分开来。
  2. 进一步来说,因为Haskell只有全局量化类型,因此,没有必要显式地写出全局量化符号(symbol),像前面的例子中,我们就简单地用`[a]`表示所有可能储存在列表内的值的类型。
  3. 换句话来说,所有类型变量都被隐式地全局量化了。

多态列表

列表是函数式语言中常用的数据结构之一,也很适用于讲解多态类型。

列表[1, 2, 3]在Haskell中,实际上是列表1:(2:(3:[]))的一种简便表示方式。其中[]代表空列表,而中序操作符(infix operator):则用于组合起一个元素和一个列表,就像Lisp中的nilcons一样。

另外,因为:操作符是右结合(right associative)的,我们也可以将列表改写为1:2:3:[]

作为一个对列表进行处理的例子,我们来定义一个求列表中元素个数的一个函数:

::

  1. length :: [a] -> Integer
  2. length [] = 0
  3. length (x:xs) = 1 + length xs

以上的定义还是相当直观的:对于一个空列表来说,它的长度为0;而对于非空列表来说,它的长度就是1加上剩余子列表的长度,其中子列表的长度为length xs

另一方面,length函数的定义还引出了Haskell的一个重要方面:模式匹配(pattern matching)。

模式匹配

在方程左边包含的像是[]x:xs的东西,称之为模式,当相应的函数(这里是length)被实际使用的时候,这些模式就会被用于测试是否和实际参数(actual parameters)相匹配。

比如说,[]模式只匹配空列表;而x:xs模式则匹配至少有一个元素的列表,它将x与列表的首个元素绑定,而xs则和x元素之后的所有剩余元素绑定。

一旦左边(left-hand side)的方程模式匹配成功,那么对应的右边(right-hand side)的表达式就会被求值,并作为计算结果返回。

如果一个模式匹配不成功,Haskell就尝试匹配下一个模式,以此类推,直到找到一个匹配的模式为止。假如所有的模式都不匹配的话,则抛出一个错误。

使用模式匹配来定义函数在Haskell非常常见,作为用户,你应该尽可能多熟悉一些常用的模式,我们会在第四章继续探讨这个问题。

再论多态

length还是一个多态函数的例子,它可以被用于任何类型的列表,比如说[Integer][Char]或是[[Integer]]

::

  1. length [1,2,3] => 3
  2. length ['a','b','c'] => 3
  3. length [[1],[2],[3]] => 3

以下是两个我们今后会经常用到的另外两个多态函数:head返回列表中的首元素,而函数tail则返回除首元素之外的其他元素。

::

  1. head :: [a] -> a
  2. head (x:xs) = x
  3. tail :: [a] -> [a]
  4. tail (x:xs) = xs

不像length函数,headtail函数都没有处理参数为空空列表时的情况,当一个空列表作为实际参数被传入headtail中的时候,将引起一个错误。

主要类型

从多态类型中我们也能看到,一些类型比另一些类型更具有一般性。比如类型[a]就比[Char]更具一般性,因为前者可以代表“任何类型的列表”,而后者只能代表“字符值列表”。

换句话说,在有需要的情况下,[Char]类型可以作为[a]类型的其中一种,从[a]类型中派生(derived)出来。

Haskell的多态特性不但强大,还非常灵活,主要是因为Haskell的类型系统拥有两种重要的特性:首先,Haskell确保所有类型良好(well-type)的表达式都有唯一的主要类型(unique principal type);其次,主要类型可以自动地推导出来(§4.1.4 <http://www.haskell.org/onlinereport/decls.html#type-semantics>_)。

和传统的单型语言(monomorphic type language)如C语言相比,Haskell的多态特性提高了代码的表达能力,而类型推导则将程序员从繁琐的类型定义中解放出来。

最后,我们称某个类型为一个表达式或一个函数的主要类型,说的是这个类型符合最小泛化类型(least general type)的原则,它包含且该表达式的所有实例。

比如说,我们可以说函数head的主要类型是[a]->a[b]->aa->a,或a,但它们都过于泛化了;而其他一些类型,比如[Integer]->Integer则过于特例化(specific)。

唯一主要类型是Hindley-Milner类型系统 <http://en.wikipedia.org/wiki/Type_inference#Hindley.E2.80.93Milner_type_inference_algorithm>_的一个标志性特性,该类型系统是Haskell、ML、Miranda等语言的类型系统的根基。