Haskell2010中文报告

欢迎喜欢Haskell的朋友共同翻译这份报告。英文版在这里

Simon Marlow (编著)

版权声明 本报告的出版者和发布者授意报告属于整个Haskell社区，如果包括这份声明在内的内容被完整的复制，那么它将被授权做拷贝及分发，并不限拷贝或分发行为的目的。报告的修订版本也可以被自由的拷贝及分布，但必须明确表明这是修改版本，而不是Haskell 2010语言的一个定义。

目录

前言

“Some half dozen persons have written technically on combinatory logic, and most of these, including ourselves, have published something erroneous. Since some of our fellow sinners are among the most careful and competent logicians on the contemporary scene, we regard this as evidence that the subject is refractory. Thus fullness of exposition is necessary for accuracy; and excessive condensation would be false economy here, even more than it is ordinarily.”

Haskell B. Curry and Robert Feys in the Preface to Combinatory Logic [3], May 31, 1956

1987年9月，在Oregon州Portland举办的函数式语言与计算机体系结构(FPGA)大会上有个会议，讨论了当时函数式语言社区的一些问题：有超过一打的惰性、纯函数式语言，但所有这些语言在表达能力与语义上都相似。会议达成了强烈的一致：如果缺乏一个共同的标准，将会妨碍这类语言的流行。会议决定组成一个委员会来设计这个通用语言，使得新的思想能够更快的得到响应，真实的应用开发有稳固的基础，并且能支撑更多人使用函数式语言。本文档即介绍那次会议及随后日子里，委员会的工作成果：一个叫做Haskell的纯函数式语言。语言的命名是为了纪念逻辑学家Haskell B.Curry ，正是他为我们提供了语言的逻辑基础。

目标

委员会的最初目标是设计一个能够满足下列约束的语言：

1. 能适用于教学、科研以及工业应用，包括构建大型系统。
2. 通过发布形式语法和形式语义来完全定义
3. 能够自由获取。任何人都有权利去实现语言并将其分布到有兴趣的人
4. 基于得到广泛共识的想法
5. 能够减少函数式编程语言的不必要多样性

Haskell2010: 语言与库

委员会的初衷是让haskell作为语言设计研究的基础，而希望它的扩展或变体来集成一些实验性的功能。

事实上，Haskell从最初版发布后就一直在衍进发展中。到1997年中期，haskell语言已经有了5个主要版本(从1.0-1.4)。在1997年Amsterdam的Haskell工作组会议上，人们决定定义一个新的稳定变体，这就是"haskell98"，于1999年2月发布。bug修订版本在2002年成为“修订版haskell98报告“。

在2005年的hasekll工作组会议，人们又达成一致：官方语言的一些扩展被广泛使用(并被多个实现支持)，是时候定义新一代的语言标准并将其编纂成册，反映当今Haskell的发展。

于是，Haskell的主要工作可以理解为相对保守地扩展Hasekll 98, 仅吸纳一些透彻理解、一致认可的功能特色。这也是为了得到一个"稳定“的语言，同时又能体现这些年来在语言设计研究上的大量进展。

通过这些年来在设计上的经验，人们认识到对语言做一次性的大修改，任务量巨大，很难一下完成。最好的办法是逐步地、增量地修改，每一个版本都只集成已经透彻理解的扩展和修改。Haskell2010是这种工作方式下的第一个版本，新的版本将逐年发布。

Haskell98 扩展

下面列出Haskell 2010相对于Haskell 98最显著的修改：

• 外部函数接口
• 层次化模块命名，比如，Data.Bool
• 模式保护

移除的语言功能：

• (n+k)模式语法

Haskell资源

Haskell的WEB站点[1]给出了许多有用资源的链接，包括:

• 语言和库定义的在线版本
• Haskell的教程资源
• Haskell邮件列表细节
• Haskell实现
• Haskell工具和库的贡献
• Haskell的应用
• 用户贡献的wiki主页
• Haskell的新闻和事件

语言构建

活跃在社区里的研究者和应用程序员们共同创建了Haskell，并不断维护。而这其中，服务于语言委员会和库委员会的人们，贡献了巨大的时间和精力。下面列出这些贡献者以及他们的工作单位(时任)

• Arvind (MIT)
• Lennart Augustsson (Chalmers University)
• Dave Barton (Mitre Corp)
• Brian Boutel (Victoria University of Wellington)
• Warren Burton (Simon Fraser University)
• Manuel M T Chakravarty (University of New South Wales)
• Duncan Coutts (Well-Typed LLP)
• Jon Fairbairn (University of Cambridge)
• Joseph Fasel (Los Alamos National Laboratory)
• John Goerzen
• Andy Gordon (University of Cambridge)
• Maria Guzman (Yale University)
• Kevin Hammond [editor] (University of Glasgow)
• Bastiaan Heeren (Utrecht University)
• Ralf Hinze (University of Bonn)
• Paul Hudak [编辑] (Yale University)
• John Hughes [编辑] (University of Glasgow; Chalmers University)
• Thomas Johnsson (Chalmers University)
• Isaac Jones (Galois, inc.)
• Mark Jones (Yale University, University of Nottingham, Oregon Graduate Institute)
• Dick Kieburtz (Oregon Graduate Institute)
• John Launchbury (University of Glasgow; Oregon Graduate Institute; Galois, inc.)
• Andres Löh (Utrecht University)
• Ian Lynagh (Well-Typed LLP)
• Simon Marlow [编辑] (Microsoft Research)
• John Meacham
• Erik Meijer (Utrecht University)
• Ravi Nanavati (Bluespec, inc.)
• Rishiyur Nikhil (MIT)
• Henrik Nilsson (University of Nottingham)
• Ross Paterson (City University, London)
• John Peterson [编辑] (Yale University)
• Simon Peyton Jones [编辑] (University of Glasgow; Microsoft Research Ltd)
• Mike Reeve (Imperial College)
• Alastair Reid (University of Glasgow)
• Colin Runciman (University of York)
• Don Stewart (Galois, inc.)
• Martin Sulzmann (Informatik Consulting Systems AG)
• Audrey Tang
• Simon Thompson (University of Kent)
• Philip Wadler [编辑] (University of Glasgow)
• Malcolm Wallace (University of York)
• Stephanie Weirich (University of Pennsylvania)
• David Wise (Indiana University)
• Jonathan Young (Yale University)

标示为[编辑]的人担任协调编辑员，贡献了语言的一个或多个修订。

其他人也做了许多有益的贡献，这些贡献虽然不大，但都非常实际。下面是他们的列表： Hans Aberg, Kris Aerts, Sten Anderson, Richard Bird, Tom Blenko, Stephen Blott, Duke Briscoe, Paul Callaghan, Magnus Carlsson, Mark Carroll, Franklin Chen, Olaf Chitil, Chris Clack, Guy Cousineau, Tony Davie, Craig Dickson, Chris Dornan, Laura Dutton, Chris Fasel, Pat Fasel, Sigbjorn Finne, Michael Fryers, Peter Gammie, Andy Gill, Mike Gunter, Cordy Hall, Mark Hall, Thomas Hallgren, Matt Harden, Klemens Hemm, Fergus Henderson, Dean Herington, Bob Hiromoto, Nic Holt, Ian Holyer, Randy Hudson, Alexander Jacobson, Patrik Jansson, Robert Jeschofnik, Orjan Johansen, Simon B. Jones, Stef Joosten, Mike Joy, Wolfram Kahl, Stefan Kahrs, Antti-Juhani Kaijanaho, Jerzy Karczmarczuk, Kent Karlsson, Martin D. Kealey, Richard Kelsey, Siau-Cheng Khoo, Amir Kishon, Feliks Kluzniak, Jan Kort, Marcin Kowalczyk, Jose Labra, Jeff Lewis, Mark Lillibridge, Bjorn Lisper, Sandra Loosemore, Pablo Lopez, Olaf Lubeck, Christian Maeder, Ketil Malde, Michael Marte, Jim Mattson, John Meacham, Sergey Mechveliani, Gary Memovich, Randy Michelsen, Rick Mohr, Andy Moran, Graeme Moss, Arthur Norman, Nick North, Chris Okasaki, Bjarte M. Østvold, Paul Otto, Sven Panne, Dave Parrott, Larne Pekowsky, Rinus Plasmeijer, Ian Poole, Stephen Price, John Robson, Andreas Rossberg, George Russell, Patrick Sansom, Michael Schneider, Felix Schroeter, Julian Seward, Nimish Shah, Christian Sievers, Libor Skarvada, Jan Skibinski, Lauren Smith, Raman Sundaresh, Josef Svenningsson, Ken Takusagawa, Wolfgang Thaller, Satish Thatte, Tom Thomson, Tommy Thorn, Dylan Thurston, Mike Thyer, Mark Tullsen, David Tweed, Pradeep Varma, Keith Wansbrough, Tony Warnock, Michael Webber, Carl Witty, Stuart Wray, and Bonnie Yantis.

最后，除了Church,Rosser,Curry等的重要基础工作以及其他人在lambda演算上的工作外，这些年其他语言的发展也影响了Haskell，一并感谢。虽然很难直接说出许多好想法的来源，但下面的语言特别影响了Haskell，它们是: lisp（以及它的现代变体common lisp, scheme)，Landin的ISWIM, APL, Backus的FP, ML和Standard ML， Hope和Hope+, Clean, ID, Lofer, Sisal, 以及Turner的系列语言包括最后的miranda. 如果没有这些先驱语言，也就没有Haskell.

语言

简介

Haskell是通用的纯函数式语言，集成了当前在程序设计语言上的许多创新。Haskell提供高阶函数、非即时语义、静态多型类型系统、用户定义代数类型、模式匹配、列表组合、模块系统、单子化I/O函数、丰富的原始库包含列表、数组、任意精度及固定精度整数、浮点数。Haskell是多年函数式程序语言最高设计水平的代表成果。

本报告定义Haskell程序的语法以及程序的非形式操作语义。

我们不关心Haskell程序的具体运行方式以及与Haskell实现相关的的问题。比如程序的解释、编译、变换，也包括编程环境相关的问题、无定义程序(即形式求值到⊥程序)的错误返回信息等。

程序结构

本节，我们论述Haskell的抽象语法与语义结构，以及结构与报告其它部分的关系。

1. 在最上层，Haskell是模块的集合。模块在模块节论述。模块提供命名空间，是大程序中软件重用的主要方法。
2. 模块的上层包含声明的集合。声明有多种，在声明和绑定节论述。声明定义诸如常规值、数据类型、类型信息及结合信息等。
3. 再下面一层定义表达式。表达式在表达式节论述。表达式表示一个值，并有一个静态类型。“小范围而言”，表达式是Haskell程序的核心。
4. 最下层是Haskell词法结构。词法结构在词法结构节论述。词法结构是Haskell程序在文本文件中的具体表示。

本报告根据Haskell文法结构自底向上论述。

上面没有提到的预定义类型和类节描述Haskell内建的数据类型和类型类。基本输入输出节讨论Haskell中的I/O设施(即，Haskell怎样与外部世界通信)。另外，还有几节讲述Prelude、具体文法、作文式编程、派生实例规范、被大多数编译器支持的编译器指示等。

Haskell程序样例用打印机字体表示：

 let x = 1  
     z = x+y  
 in  z+1

”孔“，在程序样片中表示任意大小的样例，用斜体表示，比如if e1 then e2 else e3。通常，斜体名字有助记含义，比如e表达式expressions, d声明declarations，t类型type等。

Haskell核

流行于许多函数式编程中的便利语法也被Haskell采用。在本报告中，这些语法糖被转换为更简单的结构。如果反复应用这些转换，程序最终可认为是Haskell的一个小子集所编写，这个小子集我们称为Haskell核。

虽然Haskell核没有被形式定义，但它实际上是增加一些修饰的lambda演算变体，有直接的指称语义。在我们介绍语法结构时，我们也给出语法结构到Haskell核的转换。这种模块化的设计方便我们推理Haskell程序，也为语言的实现者提供了有用的参考。

值和类型

表达式求值到值，有静态类型。Haskell中，值和类型并不混合。然而，类型系统允许各种用户定义的数据类型，不仅允许参数化多型(使用传统的Hindley-Milner类型结构)，也允许临时多型，或者称为重载(使用类型类)。

Haskell中，错误和⊥("底")语义等价。技术上，这两者看起来就像非终止，因此语言没有检测或处理错误的机制。而语言的实现通常都会对错误提供一些有用信息，具体请见错误节。

名字空间

Haskell中，名字有6种:变量与构造符表示值；类型变量、类型构造符与类型类是类型系统中的实体；模块名属于模块系统。在命名时有两个约束：

变量名和类型变量名以小写字母或者下划线开头，其它四种名字以大写字母开头。

在同一作用域内，标示符不能用来做类型构造符或者类型类。

这些也仅仅只是约束：举个例子，在同一作用域内，Int可以同时作为模块名、类名与构造符。

词法结构

本章，我们讨论Haskell的下层词法结构。在第一次阅读本报告时，这里面绝大部分细节可以先忽略。

记法约定

在显示语法时，有下面的记法约定：

• [pattern] 可选
• {pattern} 0次或多次重复
• (pattern) 分组
• pat₁ |pat₂ 选择
• pat_<pat′> 从pat而不是pat'生成
• fibonacci 终结符(文字)使用打印机字体

本节中的语法都是讨论词法语法。所以，空白符都显式表示，在并列的符号之间不隐藏空白符。本节大量使用类BNF的文法，产生式的形式如下：

nonterm → alt₁ | alt₂ | … | alt_n

虽然从上下文通常可以判断出符号的意思，但必须要注意区分元逻辑文法符号，比如|，[…]和终结符(打印机字体)|和[...]的不同。

Haskell使用Unicode字符。但是，源程序现在仍倾向于使用早先版本Haskell的ASCII字符集。

Haskell语法的Unicode字符集属性取决于Unicode委员会的定义。因此，一旦有新的Unicode发布，Haskell编译器总是假定使用新版本。

词法程序结构

program → { lexeme | whitespace }
lexeme → qvarid | qconid | qvarsym | qconsym | literal | special | reservedop | reservedid
literal → integer | float | char | string
special → ( | ) | , | ; | [ | ] | ` | { | }

whitespace → whitestuff {whitestuff}
whitestuff → whitechar | comment | ncomment
whitechar → newline | vertab | space | tab | uniWhite
newline → return linefeed | return | linefeed | formfeed
return → a carriage return
linefeed → a line feed
vertab → a vertical tab
formfeed → a form feed
space → a space
tab → a horizontal tab
uniWhite → any Unicode character defined as whitespace

comment → dashes [ any_<symbol> {any} ] newline
dashes → -- {-}
opencom → {-
closecom → -}
ncomment → opencom ANY seq {ncomment ANY seq} closecom
ANY seq → {ANY}_{<{ANY} ( opencom | closecom ) {ANY}''>}
ANY → graphic | whitechar
any → graphic | space | tab

graphic → small | large | symbol | digit | special | " | '

small → ascSmall | uniSmall | _
ascSmall → a | b | … | z
uniSmall → any Unicode lowercase letter

large → ascLarge | uniLarge
ascLarge → A | B | … | Z
uniLarge → any uppercase or titlecase Unicode letter
symbol → ascSymbol | uniSymbol_{<special | _ | " | '>}

ascSymbol → ! | # | $ | % | & | ⋆ | + | . | / | < | = | > | ? | @ | \ | ^ | | | - | ~ | :
uniSymbol → any Unicode symbol or punctuation
digit → ascDigit | uniDigit

ascDigit → 0 | 1 | … | 9
uniDigit → any Unicode decimal digit
octit → 0 | 1 | … | 7

hexit → digit | A | … | F | a | … | f

词法分析总是按照"最大满足"规则: 每次做词法分析，总是按照最长的词法规则产生词汇(lexeme类)。因此，虽然case是保留字，但cases却不是。同样地，虽然=是保留字，但==以及~=却不是。

任意空格符也可看作是词汇的分隔符。

不在ANY类的字符在Haskell程序中是非法字符，会报词法错误。

注释

注释是合法的空格符。

常规注释从两个或者多个连续横线开始，一直到本行结束。注释横线前后的连续部分不能组成合法的词。举个例子，"-->"或者"|--"不是注释的开始，因为他们都是合法词汇。而"--foo"却开始一个新的注释。

嵌入注释从"{-"开始，到"-}"结束。没有合法词汇从"{-"开始，因此,"{-"总是开始注释。举个例子，"{---"开始一个嵌入注释，并不理会后面的横线。

嵌入注释本身不做词法分析。第一个未匹配的字符串"-}"结束嵌入注释。嵌入注释可以嵌入任意多个层次。在嵌入注释里面出现"{-"将开启一个新的嵌入注释，以"-}"结束。在一个嵌入注释内部，每个"{-"由一个对应的"-}"匹配。、

在一个常规注释内，字符序列"{-"及"-}"没有特殊含义。同样，在一个嵌入注释内，横线序列也没有特殊含义。

嵌入注释也用作编译器指示，在编译器指示节介绍。

如果使用嵌入注释将某些代码注释掉，那么代码中的字符串或者行注释部分出现"{-"或"-}"将会打断嵌入注释。

标识符和运算符

varid → (small {small | large | digit | ' })_<reservedid>
conid → large {small | large | digit | ' }
reservedid → case | class | data | default | deriving | do | else

| foreign | if | import | in | infix | infixl

| infixr | instance | let | module | newtype | of

| then | type | where | _

一个标识符包含首字母及随后的0个或多个字母、数字、下划线及单引号。从词法分析的角度，标识符分为两类：小写字母开头(变量标识符)以及大写字母开头(构造符标识符)。标识符大小写敏感：name, naMe以及Name是三个不同的标识符(前两个是变量标识符，最后一个是构造符标识符)。

下划线，"_"，被处理为小写字母，可以替代小写字母出现。而"_"本身则是保留标示符，用作模式中的通配符。如果编译器为未使用标识符提供告警，那么下划线为首字符的标识符通常建议不告警。这样，如果某个参数foo未使用，程序员可以使用"_foo"做参数。

varsym → ( symbol_<:> {symbol} )_{<reservedop | dashes>}
consym → ( : {symbol})_<reservedop>
reservedop → .. | : | :: | = | \ | | | <- | -> | @ | ~ | =>

如上所示，操作符由一个或多个符号字符组成。同样，从词法分析角度，被区分为两类(名字空间)：

• 冒号开始的操作符是构造符
• 其它符号开始的操作符是常规标识符

需要注意的是冒号本身被保留，唯一用作列表的构造符；这样，它可以和其它的列表语法形式，比如"[]“及"[a,b]"统一。

除了求反是特殊的前缀形式，其它操作符都是中缀形式。此外，中缀操作符也可以用在一个分切中，以产生偏应用操作符(见分切)。所有的中缀操作符都是预定义符号，可以回弹。

本报告的其余部分，使用6类不同的名字：
varid (变量)
conid (构造符)
tyvar → varid (类型变量)
tycon → conid (类型构造符)
tycls → conid (类型类)
modid → {conid .} conid (模块)

变量及类型变量用小写字母开头的标识符表示，其它类型名字用大写字母开始的标识符表示。另外，变量和构造符有中缀形式，而其它四类名字没有。模块名由点分割的conid序列组成。名字空间在名字空间节讨论。

在特定环境下，可以在名字前添加模块名来限定名字。这种方法对变量、构造符、类型构造符及类型类名适用，对类型变量或模块名无效。限定名在模块节详细讨论。

qvarid → [modid .] varid
qconid → [modid .] conid
qtycon → [modid .] tycon
qtycls → [modid .] tycls
qvarsym → [modid .] varsym
qconsym → [modid .] consym

由于模块名也是有效词汇，限定及名字之间不允许有空格。一些词法分析的结果可以见下表：

名字	词法分析结果
f.g	f . g (三符号)
F.g	F.g (限定'g')
f..	f .. (两符号)
F..	F.. (限定 ‘.’)
F.	F . (两符号)

限定不改变名字的语法处理; 比如，Prelude.+ 是中缀操作符，和Prelude中定义的"+"(嵌套声明)有相同的缀形式。

数符

decimal → digit{digit}
octal → octit{octit}
hexadecimal → hexit{hexit}
integer → decimal

| 0ooctal | 0Ooctal

| 0xhexadecimal | 0Xhexadecimal

float → decimal.decimal [exponent]

| decimal exponent

exponent → (e | E) [+ | -] decimal

Haskell有两种不同的数符: 整数符和浮点数符。整数符可以用十进制(缺省)、八进制(Oo或OO前缀)或者十六进制(Ox或OX)表示。浮点数符总是用十进制表示。浮点数符在点号前后都必须包含数字，以保证和其它带点的字符区别开来。负数符在操作符应用节讨论。数符的类型在数节讨论。

字符和串符

char → ' (graphic_{<' | \>} | space | escape_<\&>) '
string → " {graphic_{<" | \>} | space | escape | gap} "
escape → \ ( charesc | ascii | decimal | o octal | x hexadecimal )
charesc → a | b | f | n | r | t | v | \ | " | ' | &
ascii → ^cntrl | NUL | SOH | STX | ETX | EOT | ENQ | ACK

| BEL | BS | HT | LF | VT | FF | CR | SO | SI | DLE

| DC1 | DC2 | DC3 | DC4 | NAK | SYN | ETB | CAN

| EM | SUB | ESC | FS | GS | RS | US | SP | DEL

cntrl → ascLarge | @ | [ | \ | ] | ^ | _
gap → \ whitechar {whitechar} \

字符在两个单引号之间，比如'a'。串符在两个双引号之间，比如"Hello"。

字符和串符中可以使用退出码(escape)来表示特殊字。注意，单引号'可以在出现在串中，但必须使用退出码；同样地，双引号"也可以出现在字符中，也必须使用退出码。\后面跟字符表示退出码。上面词法规则中，charesc类包含了可移植的特殊字符，比如“报警"(\a)，"退格"(\b), "换页"(\f)，"新行"(\n)，"回车"(\r)，"水平制表"(\t)以及"垂直制表"(\v)。

Haskell提供Unicode字符集的退出码，包括像\^X这样的控制符。数字退出码，比如\137，表示该字符的数字表示是137；Haskell也允许八进制和十六进制的数字退出码。

根据“最大匹配”原则，\后面的数字退出码总是包含最多的连续数字，且长度任意。同样地，\后面的ASCII退出码也满足这条规则。比如,"\SOH"词法分析结果是长度为1的串符。退出码\&表示"空字符"，这样，我们可以构造类似"\137\&9"或"\SO\&H"这样的串符(串的长度都为2)。"\&"等价于""，而字符'\&'却是不允许的。字符之间的等价性在标准Haskell类型节定义。

两个反斜杠之间只有一个或多个空白符，称为"间隔“。串内如果有间隔，则间隔被忽略。这样，我们可以写出超过一行的字符串：在行的末尾插入反斜杠，在下一行的开头插入斜杠。比如：

"Here is a backslant \\ as well as \137, \  
    \a numeric escape character, and \^X, a control character."

串符实际上字符列表的简写(见列表节)。

排版

Haskell允许某些文法省略大括号和分号，取而代之，使用排版来传递相同信息。这样，我们可以同时使用排版和不排版两种编程风格，即使在同一程序内部，这两种风格也可以混用。由于程序排版不是必选项，haskell程序可直接由其它程序生成。

排版的haskell程序，使用排版格式的地方完全可以通过添加大括号和分号的办法实现等价的Haskell程序。这个等价的Haskell程序即不排版程序。

大致上，大括号和分号可用下面的方法添加：如果关键字where、let、do、of后面的左括号被省略，则表示开始一个排版("越位")列表。这时，下一个词汇(不管是不是在新行)的缩进被记录下来(词汇前面的空白符可能也包含注释)，插入被省略的左括号。在处理后续行时，如果后续行包含更多的缩进，表示继续前面行的语法项(不插入)；如果后续行包含相同的缩进，表示开始一个新的语法项，插入一个分号；如果后续行缩进变少，则表示当前排版列表结束(插入右括号)。如果where、let、do、of后面紧跟的非括号词汇，其缩进比当前缩进级别相等或者更小，这时，Haskell并不开始新的排版列表，而是插入括号对"{}"，仍然在当前缩进上进行排版处理(即，插入一个分号或者右括号)。如果包含当前排版列表的文法类结束，也将插入右括号;即，如果某处出现词汇错误，而将此错误词汇替换为右括号时正确，则在此处添加右括号。排版规则只对自己插入的左括号配对；显式的左括号必须有显式的右括号配对。如果给出显式左括号，则括号内不对括号外的结构排版，即便某行的缩进在之前某个插入的隐式左括号的左边。

版式节对排版规则给出更精确的定义。

给出排版规则后，一个新行可能结束多个排版列表。同样地，规则使得：

f x = let a = 1; b = 2  
          g y = exp2  
       in exp1

a, b 和 g 从属于一个排版列表。

一个实例，下面是一个排版程序(有些人为修饰):

module AStack( Stack, push, pop, top, size ) where  
data Stack a = Empty  
             | MkStack a (Stack a)  
 
push :: a -> Stack a -> Stack a  
push x s = MkStack x s  
 
size :: Stack a -> Int  
size s = length (stkToLst s)  where  
           stkToLst  Empty         = []  
           stkToLst (MkStack x s)  = x:xs where xs = stkToLst s  
 
pop :: Stack a -> (a, Stack a)  
pop (MkStack x s)  
  = (x, case s of r -> i r where i x = x) -- (pop Empty) is an error  
 
top :: Stack a -> a  
top (MkStack x s) = x                     -- (top Empty) is an error

程序应用排版规则后的结果如下：

module AStack( Stack, push, pop, top, size ) where  
{data Stack a = Empty  
             | MkStack a (Stack a)  
 
;push :: a -> Stack a -> Stack a  
;push x s = MkStack x s  
 
;size :: Stack a -> Int  
;size s = length (stkToLst s)  where  
           {stkToLst  Empty         = []  
           ;stkToLst (MkStack x s)  = x:xs where {xs = stkToLst s  
 
}};pop :: Stack a -> (a, Stack a)  
;pop (MkStack x s)  
  = (x, case s of {r -> i r where {i x = x}}) -- (pop Empty) is an error  
 
;top :: Stack a -> a  
;top (MkStack x s) = x                        -- (top Empty) is an error  
}

特别要注意的是：

• 以}};pop开始的行，终结前面行的排版应用了3次排版规则，对应3层嵌套where语句。
• 在case表达式和元组之间where语句后又添加了一个右括号，因为系统检测到元组的结束，意味着语法case项也要结束。
• 添加最后一个右括号是因为，最后一列是对end-of-file符号的0级缩进。

表达式

本章，我们讨论Haskell表达式的语法以及非形式语义，我们也适时给出表达式到Haskell核的转化。除了let表达式，所有的转化都保持程序的动态及静态语义。转化中用到的自由变量或者构造符都是来自于Prelude的实体。比如，在列表组合转换中用到的"concatMap"指的就是Prelude中定义的concatMap, 无论符号"concatMap"是否出现在列表组合作用域或是它所绑定的作用域(如果concatMap在列表组合的作用域)。

exp → infixexp :: [context =>] type (表达式类型签名)

| infixexp

infixexp → lexp qop infixexp (中缀操作符应用)

| - infixexp (前缀求反)

| lexp

lexp → \ apat₁ … apat_n -> exp (lambda抽象, n ≥ 1)

| let decls in exp (let表达式)

| if exp [;] then exp [;] else exp (条件式)

| case exp of { alts } (case表达式)

| do { stmts } (do表达式)

| fexp

fexp → [fexp] aexp (函数应用) aexp → qvar (变量)

| gcon (通用构造符)

| literal

| ( exp ) (括号表达式)

| ( exp₁ , … , exp_k ) (元祖, k ≥ 2)

| [ exp₁ , … , exp_k ] (列表, k ≥ 1)

| [ exp₁[, exp₂] ... [exp₃] ] (算术序列)

| [ exp | qual₁ , … , qual_n ] (列表组合, n ≥ 1)

| ( infixexp qop ) (左分切)

| ( qop_<-> infixexp ) (右分切)

| qcon { fbind₁ , … , fbind_n } (标记构造, n ≥ 0)

| aexp_<qcon>{ fbind₁ , … , fbind_n } (标记更新, n ≥ 1)

表达式，包括中缀表达式，用操作符结合信息来分辨(嵌套声明节)。连续的无括号操作符，如果优先级相等，必须指定是左结合还是右结合，否则会产生语法错误。假定无括号表达式"x gop^(a,i) y qop^(b,j) z"(qop^(a,i)表示操作符缀为a，优先级是i)，且i=j，这时必须在"x qop^(a,i) y"或者"y qop^(b,j) z"两侧添加括号，除非a=b=l或a=b=r。

结合解析节给出了包括中缀表达式在内的表达式结合判定算法。

求反是唯一的前缀表达式；它和Prelude中(嵌套声明)的中缀操作符-有相同的优先级。

如果考虑lambda抽象、let表达式和条件式的延伸，则通常会出现歧义文法。歧义文法的判定，由下面的元规则确定：这些结构总是尽可能的右延。

下面是一些样例解析：

表达式	解析
f x + g y	(f x) + (g y)
- f x + y	(- (f x)) + y
let { ... } in x + y	z + (let { ... } in (x + y))
f x y ::Int	(f x y)::Int
\ x -> a+b :: Int	\ x -> ((a+b) :: Int)

为了便于阐述，本节余下部分假定包含中缀操作符在内的表达式，根据操作符的结合信息有唯一的解析。

错误

Haskell中，表达式求值过程中的错误，用⊥(底)表示。Haskell不区分⊥和程序非终止。Haskell是一个非即时语言，所有的Haskell类型都包含⊥。即，任何类型的值都可能绑定到某个计算，计算启动后返回一个错误。求值过程中出现错误，会立即终止程序，不能被用户捕获。Prelude提供两个函数，可以直接产生错误：

error     :: String -> a  
undefined :: a

调用error终止当前程序执行，并返回合适错误信息给操作系统。同时，会以系统相关的方式显式错误串。调用undefined时，编译器产生错误信息。

Haskell表达式的转化使用error和undefined显式表达可能发生执行期错误的位置。发生错误时的程序行为由具体实现决定。表达式转化传递给error函数的消息仅仅只是建议；实际上，由具体实现来打印错误发生时的大概信息。

变量，构造符，操作符和终结符

aexp → qvar (变量)

| gcon (一般构造符)

| literal

gcon → ()

| []

| (,{,})

| qcon

var → varid | ( varsym ) (变量)
qvar → qvarid | ( qvarsym ) (限定变量)
con → conid | ( consym ) (构造符)
qcon → qconid | ( gconsym ) (限定构造符)
varop → varsym | ` varid ` (变量操作符)
qvarop → qvarsym | ` qvarid ` (限定变量操作符)
conop → consym | ` conid ` (构造符操作符)
qconop → gconsym | ` qconid ` (限定构造符操作符)
op → varop | conop (操作符)
qop → qvarop | qconop (限定操作符)
gconsym → : | qconsym

Haskell通过特殊语法支持中缀表示。操作符可以看做是使用中缀表示的函数(操作符应用)，也可以通过分切(分切)实现偏应用。

一个操作符可以是一个符号，比如+或$$，也可以是一个方言标记(反引号)的常规符号，比如`op`. 举个例子，前缀应用op x y，也可以写成中缀应用x `op` y。如果没有`op`没有结合定义，那么它缺省有最高的优先级并左结合(见声明与绑定节)。、

同样，符号表示的操作符也可以转换为常规符号，方法是添加括号。比如，(+) x y和x + y等价。foldr (*) 1 xs 和foldr (\x y -> x * y) 1 xs等价。

命名一些内置类型的构造符时使用了一些特殊语法，比如产生式gcon和literal。这些将在标准Haskell类型节阐述。

一个整数符表示函数fromInteger应用于类型为Integer的对应值。类似地，一个浮点数符表示fromRational应用一个类型为Rational的值(即，比率数(有理数))。

转化：整数符i被转化为fromInteger i，这里fromInteger是Num类的一个方法(见数节)。 浮点数符f等价于fromRational (n Ratio.% d)，这里fromRational是Fractional类的方法，Ratio.% 由两个整数构造一个有理数，在Ratio库中定义。整数n和d选择方法是n/d = f.

Curry应用及Lambda抽象

fexp → [fexp] aexp (函数应用)
lexp → \ apat₁ … apat_n -> exp (lambda抽象, n ≥ 1)

函数应用记为e₁ e₂。函数应用是左结合，因此(f x) y中的括号可以省略。除函数外，e₁也可以是数据构造符，因此，数据构造符的偏应用也是允许的。

Lambda抽象记为，\ p₁ ... p_n -> e, 其中，p_i是模式。形如\x:xs -> x的表达式语法上非法; 合法写法是\ (x:xs) -> x。

模式集合必须是线性的-集合中的变量至多出现一次。

转化：下面的转化等价: \ p1 … pn -> e = \ x1 … xn -> case (x1, …, xn) of (p1, …, pn) -> e 其中，xi是新标识符。

如果由这里的转换以及模式匹配节给出的case表达式以及模式匹配的语义不能匹配某个模式，则其结果是⊥。

操作符应用

infixexp → lexp qop infixexp

| - infixexp (前缀求反)

| lexp

qop → qvarop | qconop (限定操作符)
e₁ qop e₂是二元操作符qop应用于表达式e₁及e₂的中缀形式。 表达式-e形式特殊，是Haskell中唯一的前缀操作符，是negate (e)的语法表示。二元操作符"-"不一定指 Prelude中定义的"-"操作符，它有可能被模块系统重新定义。而，单元操作符"-"总是指Prelude中定义的求反函数。本地定义"-"操作符和单元求反之间没有联系。

前缀求反和中缀操作符-有相同的优先级(见嵌套声明节表)。表达式e₁ - e₂被解析为二元操作符-的中缀应用，因此，如果要得到另外一种解析，我们必须写成e₁ (-e₂)。类似地，(-)是(\ x y -> x - y)的语法，和其它中缀操作符一样，它不表示(\ x -> -x)，我们必须使用求反来获得(\ x-> -x)。

转化：下面式子等价: e1 = (op) e1 e2 -e = negate (e)

分切

aexp → ( infixexp qop ) (左分切)

| ( qop_<-> infixexp ) (右分切)

分切被记为( op e)或(e op)，这里，op是二元操作符，e是表达式。分切是二元操作符实现偏应用的便利语法。

语法优先级规则应用于分切如下所述：当且仅当(x op (e))和(x op e)语法解析相同时，(op e)合法。同理，(e op)也有此规则。举个例子，(*a+b)语法非法，但(+a*b)及(*(a+b))却合法。由于(+)左结合，(a+b+)语法正确，但(+a+b)错误。后者可以合法记为(+(a+b))。另外一个例子，由表达式节let/lambda元规则，表达式：

  (let n = 10 in n +)

非法。因为，表达式

  (let n = 10 in n + x)

语法解析为:

  (let n = 10 in (n + x))

而不是

  ((let n = 10 in n) + x)

由于语法中对-处理特殊，(- exp)不是分切，而是前缀求反应用。这在前面章节中有所论述。然而，Prelude定义了一个subtract函数，(subtract exp)等价于前面被禁掉的分切。同样地，表达式(+ (- exp))也能达到相同的目的。

转化：下面式子等价: (op e) = \ x -> x op e (e op) = \ x -> e op x 其中，op是二元操作符，e是表达式，x是不在e中自由出现的变量。

条件式

lexp → if exp [;] then exp [;] else exp

条件式形如if e₁ then e₂ else e₃。当e₁值为True时，返回e₂的值，当e₁值为False时返回e₃，其它情况下，返回⊥

转化：下面式子等价: if e1 then e2 else e3 = case e1 of { True -> e2 ; False -> e3 } 其中，True和False是Prelude中定义的、类型为Bool的非空构造符。e1的类型必须为Bool; e2和e3类型必须相同，且都是整个条件式的类型。

术语(中英文对照)

  structure: 结构
  lexical: 词法的
  expression: 表达式
  declaration: 声明
  binding: 绑定
  module: 模块
  type:  类型
  class: 类
  input: 输入
  output: 输出
  Foreign Function Interface: 外部函数接口
  syntax: 语法
  derived: 派生
  Instance: 实例
  compiler: 编译器
  pragmas: 指示
  specification： 规范
  namespace:  名字空间
  kernel:  核
  convention: 约定
  literal: 终结符 文字
  layout:  版式 排版 
  constructor： 构造符
  Application:  应用
  abstraction: 抽象
  operator: 操作符 
  section: 分切(expression section)
  conditional: 条件式
  list: 列表
  tuple: 元组
  unit expression: 元表达式
  parenthesized expression: 括号表达式
  sequence: 序列
  comprehension: 组合
  field: 域
  label: 标记
  pattern: 模式
  matching: 匹配
  type signature: 类型签名 
  overview： 概述
  datatype: 数据类型
  alert: 报警
  backspace: 退格
  form feed: 换页
  new line: 新行
  carriage return: 回车
  horizontal tab: 水平制表
  vertical tab: 垂直制表
  escape code: 退出码
  backslant: 反斜杠
  gap: 间隔   
  overload: 重载
  import: 导入
  export: 导出
  closure: 闭包
  strict evaluation: 即时求值
  monad: 单子
  exception: 异常
  marshal: 列集
  fixity: 缀 结合 (infix[中缀], leftfix[左结合], rightfix[右结合])
  resolution: 解析
  inline: 内联
  specialization: 特例化
  extension: 扩展
  functor: 函子
  Immutable: 不可变对象
  non-strict: 非即时
  rectangular form: 矩阵式
  polar form: 极坐标式
  conjugate: 共轭
  zip: 配对
  unzip: 拆对
  finalise: 固化
  handle: 句柄 
  throw: 抛出
  catch: 捕获
  variant: 变体
  workshop: 工作组会议
  calculus: 演算
  polymorphic: 多型
  syntactic sugar: 语法糖
  denotational semantics: 指称语义
  ad-hoc: 临时
  scope: 作用域
  literate programming: 作文式编程
  wild card: 通配符 
  identifier: 标识符 
  negation: 求反
  partially appied: 偏应用 
  rebound: 回弹 
  qualified: 限定
  brace: 大括号
  open brace: 左括号
  close brace: 右括号
  lexeme: 词汇
  production: 产生式
  extent: 延伸( extent of let expression: let 表达式的延伸)
  error: 错误
  non-termination: 非终止
  guard: 守护