Haskell/可打印版本

维基教科书,自由的教学读本
跳到导航 跳到搜索


Table Of Contents

Haskell基础

起步
变量和函数
列表和元组
更进一步
类型基础
简单的输入输出
类型声明
编辑此章节

初级Haskell

递归
模式匹配
深入列表
控制结构
列表处理
深入函数
高阶函数
编辑此章节

Haskell进阶

模块
缩进
更多数据类型
类的声明
类与类型
保持状态记录
编辑此章节

Monads

理解 Monad
高级 Monad
Monad 进阶
MonadPlus
Monadic parser combinators
Monad transformers
Monad 实务
编辑此章节

高级Haskell

Monoid类型类
Applicative类型类
箭头
理解箭头
Foldable类型类
Traversable类型类
延续过渡风格(CPS)
可变对象
拉链
适用函子
独异点
Lens 和引用
并行
编辑此章节

类型的乐趣

多形性基础
存在性类型
高级类型类
幻影类型
通用代数数据类型
数据类型代数学
编辑此章节

理论提升

指称语义
Equational reasoning
Program derivation
Category theory
The Curry-Howard isomorphism
fix 和递归
编辑此章节

Haskell性能

Introduction
Step by Step Examples
Graph reduction
Laziness
Strictness
Algorithm complexity
Data structures
Parallelism
编辑此章节

程序库参考

The Hierarchical Libraries
Lists:Arrays:Maybe:Maps
IO:Random Numbers
编辑此章节

普通实务

构建一个独立的应用
除错
测试
打包你的程序
使用外部程序接口
编辑此章节

专门任务

图形用户界面
数据库
网络编程
使用XML
使用正则表达式
编辑此章节

Haskell基础


起步

本章节展示了如何安装软件,以便让你用 Haskell 编写程序。

可打印版本
Haskell基础

起步
变量和函数
列表和元组
更进一步
类型基础
简单的输入输出
类型声明

安装Haskell

Haskell 是一种编程语言,表达人类如何让计算机工作。类似写菜谱,人来写而计算机负责烹调。

要运行 Haskell 编写的程序,首先,你需要一个 Haskell 编译器。编译器是一种电脑程序,将 Haskell 代码变成机器码,而電腦能理解机器码。照上頭的比喻來說的話,編譯器就是把麵糊(程式碼)轉化為餅乾(可執行檔)的烤爐,而在經過烘烤後,要得知原來的食譜是困難的。

下载并安装 Haskell platform,它包含 Glasgow Haskell Compiler(缩写:GHC)与其他所需组件。

如果你只是想試試 Haskell,或者不願意完整地安裝編譯器,你可能會喜歡 Hugs,Haskell的輕量級可攜式直譯器,或 TryHaskell,一個線上直譯器。值得注意的是本課程假定你使用的是 GHC。

注解

給 UNIX 用戶:

如果你是想编译源码的人:这对于 GHC 来说是一个坏主意, 特别是如果你是第一次安装。GHC 本身几乎全部使用 Haskell 编写,所以试着手工从源码引导它的编译是非常麻烦的。除此之外,编译会消耗大量时间并且消耗大量磁盘空间。如果你坚持从源码编译 GHC,参见GHC主页上的“编译和移植GHC”.

簡而言之,我們強烈建議安裝 Haskell platform 而非從源碼編譯。

第一步

在 Haskell Platform 安装完毕后,现在可以开始写第一份 Haskell 代码了。 需要使用一个叫做GHCi(i代表交互式,interactive)。根据不同的操作系统,进行以下操作

  • Windows:『开始』菜单,然后『运行』,输入 cmd 并回车,输入 ghci 后再次回车
  • MacOS:打开在『应用程序/实用工具』中的『终端』,在新打开的窗口中输入 ghci 并按回车
  • Linux:打开一个终端(或模拟器)然后运行 ghci 程序

你会看到类似于下面的界面:

GHCi, version 8.6.5: http://www.haskell.org/ghc/  :? for help
Prelude>

首先看到的是 GHCi 的版本号。然后提示你正在载入基本包,可以通过 :?help 命令查找帮助。最后的 Prelude> 就是提示符了。你可以在这之后输入命令,GHCi 会立刻把计算出来的结果显示出来。

现在可以开始写第一份 Haskell 代码了,让我们先来试一试一些基本的算术功能:

Prelude> 2 + 2
4
Prelude> 5 + 4 * 3
17
Prelude> 2 ^ 5
32

这些运算符和其它编程语言中是大致相同的:+ 是加法,* 是乘法,^ 是乘方。由第二個例子,我們能看出 Haskell 遵守一般的運算子優先順位。

现在我们已经知道如何把 Haskell 当作计算器使用,Haskell 语言中的关键点在于,它总是像计算器,当我们不仅仅计算数字,而是与其他像字符、列表、函数、树甚至其他程序等对象来使用时便显得更加强大(如果你现在还不熟悉,用不着担心)。

如果你想关闭解释器 GHCi,可以使用 :quit (或者 :q):

Prelude> :quit
Leaving GHCi.

GHCi 是一个非常强大的开发平台。随着课程的进行,我们会学到如何在 GHCi 中载入源文件,并计算其中不同的部分。

下一章节,我们会介绍 Haskell 基本概念。然后会写我们第一个函数。



可打印版本
Haskell基础

起步  >> 变量和函数  >> 列表和元组  >> 更进一步  >> 类型基础  >> 简单的输入输出  >> 类型声明


Haskell

Haskell基础 >> 初级Haskell >> Haskell进阶 >> Monads
高级Haskell >> 类型的乐趣 >> 理论提升 >> Haskell性能


库参考 >> 普通实务 >> 特殊任务


变量和函数

(本章的所有例子都可以写进Haskell源代码文件并利用GHC或Hugs加载进行求值运算。请注意不要输入开头的提示符,如果代码前面有提示符,可以在GHCi等环境中输入;如果没有,则写进文件再运行。)

变量

我们已经了解如何把GHCi当作计算器来使用,当然只是极其简短的例子。对于更长的计算以及Haskell程序而言,需要对運算的中間结果进行追踪。

中間结果可以存入变量,通过名字来访问。一个变量包含一个,當使用變數時,變數內的值會被代入。举个例子,请考虑以下情况

ghci> 3.1416 * 5^2
78.53999999999999

在前一章节中,我们知道了如何做像加法和减法这样的算术运算。提问:半径是5厘米的圆的面积是多少?别担心,你并不是错看了几何课本。这个圆的面积是,其中是半径(5厘米),简单地说就是。那么,让我们在GHCi中试一下吧:

   ___         ___ _
  / _ \ /\  /\/ __(_)
 / /_\// /_/ / /  | |      GHC Interactive, version 6.4.1, for Haskell 98.
/ /_\\/ __  / /___| |      http://www.haskell.org/ghc/
\____/\/ /_/\____/|_|      Type :? for help.

Loading package base-1.0 ... linking ... done.
Prelude>

我们要把pi(3.14)乘以半径的平方,那就这样

Prelude> 3.14 * 5^2
78.5

太棒了!我们让这台奇妙而又伟大的计算机帮我们计算出了我们想要的结果。但我们不想pi仅仅保留2位小数。那么就让我们再试一次,这次pi变得有点长。

Prelude> 3.14159265358979323846264338327950 * (5 ^ 2)
78.53981633974483

很好,这次我们来计算一下圆的周长(提示:)。

Prelude> 2 * 3.14159265358979323846264338327950 * 5
31.41592653589793

那么半径是25的圆的面积呢?

Prelude> 3.14159265358979323846264338327950 * (25 ^ 2)
1963.4954084936207

我们迟早会厌倦把上述代码一遍又一遍的输入(或拷贝粘贴)的。如我们所言,编程的目的就是摆脱类似于把pi的前20位输入一亿遍这样愚蠢、乏味的重复劳动。我们要做的就是让解释器记住pi的值:

Prelude> let pi = 3.14159265358979323846264338327950
注解

如果这条命令没用的话,你可能使用的是hugs而不是GHCi,hugs的语法有一点不同。

这里你就告诉了Haskell:“让pi等于3.14159……”。这里引入了一个新的变量pi,它被定义为一个数字3.14159265358979323846264338327950。这样就变得非常方便了,我们只要再次输入pi就可以了:

Prelude> pi
3.141592653589793

别在意那些丢失的小数位,他们仅仅是不显示罢了。所有这些小数位都会在将来的计算中被使用到的。

有了变量,事情就变得轻松了。半径是5厘米的圆的面积是多少呢?半径是25厘米的呢?

Prelude> pi * 5^2
78.53981633974483
Prelude> pi * 25^2
1963.4954084936207
注解

我们这里所说的“变量”("variables"),在其它函数式编程的书籍中经常被叫做是“符号”("symbols")。那是因为在其它的语言中,也就是命令式语言中,变量被赋予了完全不同的使用方式:跟踪状态(keeping track of state)。在Haskell中的变量不是这样的:变量保存了一个值,然后再也不可以修改它了。

类型

按照上面的示例,你可能会想把半径保存在一个变量里。让我们看看会发生什么吧!

Prelude> let r = 25
Prelude> 2 * pi * r

<interactive>:1:9:
    Couldn't match `Double' against `Integer'
      Expected type: Double
      Inferred type: Integer
    In the second argument of `(*)', namely `r'
    In the definition of `it': it = (2 * pi) * r

怎么回事!这里,你遇到了程序设计上的一个概念:类型(types)。类型是许多程序设计语言都有的一个特性,它被设计用来在你自己发现之前,尽早的捕获程序设计上的错误。我们将在之后的类型基础详细讨论型别,现在让我们把它想像成插头和插座。例如,计算机背后的不同功能的插头被设计成不同的形状和大小,这样你就不必担心插错插头了。类型也有着类似的目的,但是在这个特殊的例子里,类型好像不怎么有用啊。

这里的诡异之处在于,像25这样的数字会被解释成Double(双精度浮点型)或Integer(整型),或者可能是其它类型。由于缺少必要的信息,Haskell“猜测”它的类型是Integer(它不能和一个Double型别的数字相乘)。为了解决这个问题,我们只需简单的强调一下,把它作为Double就可以了。

Prelude> let r = 25 :: Double
Prelude> 2 * pi * r
157.07963267948966

请注意,Haskell的这里“猜测”只会发生在当它缺乏足够的信息来推断出型别的时候。下面我们会看到,在大多数情况下,Haskell是能够根据上下文的信息来作出推断的。也就是说,是否把一个数字作为Integer,或是其它型别。

注解

事实上在这个难题背后有一点点微妙。它涉及一个叫作单一同态限定(monomorphism restriction)的语言特性。事实上现在你不需要知道这个,所以如果只想快一点你可以跳过这条提示。除了指定Double类型,你也可以给它一个多态(polymorphic)类型,像Num a => a,意思是"属于Num类的任意类型a"。示例代码如下,它们运行起来像先前的代码一样:

Prelude> let r = 25 :: Num a => a
Prelude> 2 * pi * r
157.07963267948966

Haskell可以从理论上系统地指定这样的多态类型,而不是做缺省的存在潜在错误的猜测,比如整数。但在现实世界,这可能导致数值被不必要地复制或重复计算。要避免这个潜在的陷阱,Haskell的设计者赞同更谨慎的“单一同态限定”。这意味着如果可以从上下文推断出来,或者你明确指定了一个,那么数值只能有一个多态类型。否则编译器会强制选择一个默认的单一同态(也就是非多态)类型。无论如何,这个特性是有争议的。甚至可以使用GHC参数(-fno-monomorphism-restriction)来禁用它,但是这带来了一些低效率的风险。除此之外,多数情况下它就像明确指定类型一样容易。


变量中的变量

变量不仅可以保存像3.14这样的数值,还可以保存任何Haskell表达式。那么,为了方便的表达半径是5的圆的面积,我们可以写如下代码:

Prelude> let area = pi * 5^2

多么有意思啊,我们在一个变量里面保存了一个复杂的Haskell程序块(一个包含变量的算术表达式)。

我们可以在变量里面保存任意的Haskell代码。那么,让我们继续吧!

Prelude> let r = 25.0
Prelude> let area2 = pi * r ^ 2
Prelude> area2
1963.4954084936207

到现在为止,一直都还不错。

Prelude> let r = 2.0
Prelude> area2
1963.4954084936207
变量不可以被修改

等一下,怎么不对?为什么我们改了半径,面积还是原来的结果?原因就是Haskell里的变量是不可以被修改的[1]。在你第二次定义r的时候,实际上,操作的是另一个r。这种事情在现实生活中也经常碰到。名字叫John的人有多少呢?很多人名字都会是John。当你向朋友们提起“John”的时候,你朋友会根据当时的情况知道到底是哪一个John。在程序设计上也有类似于“当时的情况”这样的概念:作用域。我们并不在这里解释作用域(至少现在不)。Haskell作用域的诡异之处在于可以定义两个不同的r,而总能取用正确的那个。遗憾的是,作用域并没有解决当前的问题。我们要的是定义一个通用的area函数,来告诉我们圆的面积。我们现在能做的,只能把它再定义一遍:

Prelude> let area3 = pi * r ^ 2
Prelude> area3
12.566370614359172

我们是程序员,程序员是讨厌重复劳动的。有更好的解决方法吗?

函数

我们为了完成一个通用的求面积功能,其实就是定义一个函数。就如同定义一个变量那样,在Haskell中定义一个函数十分的简单。不同之处在于等号的左边有一些额外的东西。例如,下面我们定义一个pi,接着就是面积函数area:

Prelude> let pi = 3.14159265358979323846264338327950
Prelude> let area r = pi * r ^ 2

要计算两个圆的面积,只要把不同的半径传入就可以了:

Prelude> area 5
78.53981633974483
Prelude> area 25
1963.4954084936207

函数的出现使得我们对代码的重用方面有了极大的飞跃。先等一下,让我们来剖析一下上面事物的本质。注意到area r = ...中的r了吗?这就是所谓的参数。参数用来表示一个函数的输入。当Haskell在执行这个函数的时候,参数的值是来自于外部的。在area这个例子中,当你调用area 5的时候,r5,而调用area 25的时候,r25.

练习

在Haskell中输入如下代码:(先不要在解释器中输入)

Prelude> let r = 0
Prelude> let area r = pi * r ^ 2
Prelude> area 5
  1. 你认为会发生什么?
  2. 实际发生了什么为什么(提示:记得以前我们提过的“作用域”吗?))

作用域和参数

警告:此章节包含上面练习的一些信息

我们希望你完成上面那个小小的练习(也可说是一个实验)。那么,下面的代码并不会让你出乎意料:

Prelude> let r = 0
Prelude> let area r = pi * r ^ 2
Prelude> area 5
78.53981633974483

你可能认为会得到一个0,但结果出乎你的预料。原因就上我们上面所说的,一个命名参数的值是你调用这个函数时传入的。那就是我们的老朋友,作用域。let r = 0中的r和我们定义的函数area中的r,并不是同一个r。在area中的r覆盖了其它的r。你可以认为Haskell选取了一个最近的一个r。如果你有很多朋友都叫John,那么和你在一起的那个John就是你在说话中提到的那个Jonh。类似的,r的值是什么取决于作用域。

多重参数

关于函数你也许应该知道另一项知识。那就是,函数可以接受一个以上的参数。例如,你想要计算一个矩形的面积。这很容易表达:

Prelude> let areaRect l w = l * w
Prelude> areaRect 5 10
50

又或者你想要计算一个直角三角形的面积

Prelude> let areaTriangle b h = (b * h) / 2
Prelude> areaTriangle 3 9
13.5

参数传入的方式很直接:只需要根据和定义时一样的顺序传入参数就可以了。因此,areaTriangle 3 9会给出底为3而高为9的三角形面积,而areaTriangle 9 3将给出底为9而高为3的三角形面积。

练习
写一个计算立方体体积的函数。立方体有长、宽、高。把它们乘起来就可以了。


函数中的函数

我们可以在其他函数的内部调用函数以进一步删减重复的数量。一个简单的例子将用于展示怎样利用这些创建一个计算正方形面积的函数。我们都知道正方形是矩形的一个特殊情况(面积仍然是宽乘以长);然而,我们知道它的宽和长是相同的,因此为什么我们需要键入两次呢?

Prelude> let areaRect l w = l * w
Prelude> let areaSquare s = areaRect s s
Prelude> areaSquare 5
25
练习
编写一个计算圆柱体体积的函数. 圆柱体的体积是圆形底的面积 (你已经在这章编写了这个函数, 所以重新利用它) 乘以高.

总结

  1. 变量保存着值。其实,他们可以保存任意的Haskell表达式。
  2. 变量不可以改变。
  3. 函数可以帮助你编写可重复利用的代码。
  4. 函数可以接受一个以上的参数。

注释

  1. 依据读者以前的编程经验:变量不可以改变?我只能得到常量?震惊!恐怖!不……相信我们,我们希望在这本书的剩下部分给你说明,不改变一个单一的变量对你大有帮助!事实上,这些不能改变的变量可以使生活更加方便,因为它可以使程序变得更加可以预测。



可打印版本
习题解答
Haskell基础

起步  >> 变量和函数  >> 列表和元组  >> 更进一步  >> 类型基础  >> 简单的输入输出  >> 类型声明


Haskell

Haskell基础 >> 初级Haskell >> Haskell进阶 >> Monads
高级Haskell >> 类型的乐趣 >> 理论提升 >> Haskell性能


库参考 >> 普通实务 >> 特殊任务


列表和元组

列表和元组是把多个值融为单个值的两种方法

列表

函数式编程程序员的下一个好友

上一章我们介绍了Haskell变量和函数的概念。 在Haskell程序中,函数是两个主要的构成块之一。另一个则是通用列表。那么干脆,我们切换到解释器里,并创建一些列表:

例子 - 在解释器中创建列表

Prelude> let numbers = [1,2,3,4]
Prelude> let truths  = [True, False, False]
Prelude> let strings = ["here", "are", "some", "strings"]

方括号指出列表的开始和结束,逗号操作符","分隔列表元素。另外,列表元素必须是同一类型。因此, [42, "life, universe and everything else"] 不是一个正确的列表,因为它包含了两种不同类型的元素,也就分别是整型和字符串型。而 [12, 80] 或者, ["beer", "sandwiches"] 都是合法的列表,因为他们都是单一类型的。

如果定义一个含有多个类型元素的列表,就会发生这样的错误:

Prelude> let mixed = [True, "bonjour"]

<interactive>:1:19:
    Couldn't match `Bool' against `[Char]'
      Expected type: Bool
      Inferred type: [Char]
    In the list element: "bonjour"
    In the definition of `mixed': mixed = [True, "bonjour"]

如果你对列表和类型感到困惑,不用担心。我们还没有太多地讨论到类型,我们相信在以后的章节你会明白。

创建列表

方括号与逗号并不是创建列表的唯一方式。使用(:)cons操作符,你可以逐步地把数据附加(consing[1])到一个列表上,从而创建另一个列表。

Example

例子: 把数据附加(Cons)到列表

Prelude> let numbers = [1,2,3,4]
Prelude> numbers
[1,2,3,4]
Prelude> 0:numbers
[0,1,2,3,4]


当你附加数据到列表(something:someList)时,你得到的是另一个列表。那么,毫无悬念,这种构建方式是可以复合的。

Example

例子: 附加(Cons)

Prelude> 1:0:numbers
[1,0,1,2,3,4]
Prelude> 2:1:0:numbers
[2,1,0,1,2,3,4]
Prelude> 5:4:3:2:1:0:numbers
[5,4,3,2,1,0,1,2,3,4]


事实上所有的列表都是在一个空的列表([])的基础上通过附加数据创建的。逗号与方括号的记法实际上是一种语法糖般的令人愉快的形式。 换句话说,[1,2,3,4,5]精确地等同于1:2:3:4:5:[]

你需要留意一类形如1:2的错误,你会得到如下错误。

Example

例子: Whoops!

Prelude> 1:2

<interactive>:1:2:
    No instance for (Num [a])
      arising from the literal `2' at <interactive>:1:2
    Probable fix: add an instance declaration for (Num [a])
    In the second argument of `(:)', namely `2'
    In the definition of `it': it = 1 : 2


再一个例子True:False,但仍然错误

Example

例子: 更简单但仍然错误

Prelude> True:False

<interactive>:1:5:
    Couldn't match `[Bool]' against `Bool'
      Expected type: [Bool]
      Inferred type: Bool
    In the second argument of `(:)', namely `False'
    In the definition of `it': it = True : False


可以看到(:)cons构建适用于something:someList这种形式,但当我们将其使用于something:somethingElse形式下时它就不适用了。可以看到(:)cons是如何依赖于列表的。 在这里我们开始接触到类型的概念。让我们来总结一下:

  • 列表中的元素必须有相同的类型
  • 只能附加(cons)数据到一个列表上

类型是不是很烦人?确实,但是我们可以从Haskell/类型基础可以看到它也可以为我们节约时间。当你以后使用Haskell编程时遇到了错误,你会习惯想到这很可能是一个类型错误。

练习
  1. 如下Haskell是否正确: 3:[True,False]?为什么?
  2. 写一个函数cons88添加到一个列表中。并进行如下测试:
    1. cons8 []
    2. cons8 [1,2,3]
    3. cons8 [True,False]
    4. let foo = cons8 [1,2,3]
    5. cons8 foo
  3. 写一个有两个参数的函数,一个参数为list,另一个为thing,把thing附加到list。你可以这样开始let myCons list thing =

列表组成的列表

列表可以包含任意数据,只要它们都属于同一种类型。那么,接下来思考这样一个问题:列表也是数据,所以,列表可以包含……是的的确,其它列表!在解释器上尝试以下语句:

Example

例子: 列表可以包含列表

Prelude> let listOfLists = [[1,2],[3,4],[5,6]] 
Prelude> listOfLists
[[1,2],[3,4],[5,6]]


有时列表组成的列表可能相当狡猾,因为一个列表所包含的单个数据并不和这个列表自身同属一种数据类型。让我们用几个练习来说明这个概念:

练习
  1. 下列哪些是正确的Haskell表达式,哪些不是?用cons记法重写。
    1. [1,2,3,[]]
    2. [1,[2,3],4]
    3. [[1,2,3],[]]
  2. 下列哪些是正确的Haskell表达式,哪些不是?用逗号和方括号记法重写。
    1. []:[[1,2,3],[4,5,6]]
    2. []:[]
    3. []:[]:[]
    4. [1]:[]:[]
  3. Haskell中可以创建包含由列表组成的列表的列表吗?为什么能或者为什么不能?
  4. 下面的列表为什么不正确?如果你还不能回答不要太烦恼。
    1. [[1,2],3,[4,5]]

列表组成的列表极其有用,因为它们允许你表达一些非常复杂的、结构化的数据(例如二维矩阵)。它们也是Haskell类型系统中众多真正的闪光点之一。人类程序员,或者至少这本Wikibook的作者,在使用列表组成的列表时,总是变得困惑;同时,有限制的类型经常帮助我们艰难地通过这些潜在的困难。

元组

另一种多值记法

元组是另一种把多个值储存到一个值的方式,但是它们与列表在某些方面有一些精巧的差异。若你事先知道你要储存多少个值为一组元组是十分有用的,其次元组对其中每一个值是分别进行类型限制的。举些例子,我们想用一个类型来表达平面坐标,现在我们知道要储存的值的个数为两个(xy),所以在这个例子中可以使用元组来储存平面坐标。或者,我们要写一个电话本程序,我们可以把某人的名字,电话号码以及地址储存到一个元组中。在第二个例子中,我们同样知道我们需要储存三个值为一组。尽管三个值的类型不尽相同,但元组对其中值的类型没有同一性的要求。

让我们看一下这些元组样本。

Example

例子: 一些元组

(True, 1)
("Hello world", False)
(4, 5, "Six", True, 'b')


第一个例子是一个有两个元素的元组,第一个元素是True第二个是1。第二个例子同样是一个有两个元素的元组,第一个是"Hello world"第二个是False。第三个例子比较复杂,这个元组有五个元素,第一个是数字4,第二个是数字5,第三个是"Six",第四个是True,最后一个是字母'b'。元组的组成就是用逗号吧各个元素分开,两端围上圆括号。

术语:若元组的长度为n则称其为n-tuple。特殊地如果元组的长度为2则称其为'pairs'(对),如果元组的长度为3则称其为'triples'。

元组跟列表有一点是相似的,就是它们都能储存多个值。但是,很重要的一点,不同长度的元组的类型是不一样的。虽然这里再次提及类型这个概念,一个你可能还不清楚的概念,但是可以看到列表跟元组对待自身长度的方式是不一样的。换一种说法,如果对一个由数字组成的列表添加一个新的数字,它依然是一个列表。但是如果你往一个长度为2的元组中添加一个元素,则你得到了一个完全不同的元组[2]

练习
  1. 写一个 3-tuple 第一个元素为 4, 第二个元素为 "hello" , 第三个元素为 True。
  2. 以下哪几个是元组 ?
    1. (4, 4)
    2. (4, "hello")
    3. (True, "Blah", "foo")
  3. 往一个列表堆叠(consing)新的元素: 你可以往一个数字列表添加数字,得到一个数字列表,但是元组是没有这种堆叠方法的。
    1. 你是怎样理解的?
    2. 讨论:如果有一个函数可以对元组进行堆叠,堆叠后得到的是什么?

元组有何用途?

当你想在某个函数中返回多个值的时候,元组很好使。在大多数语言中,返回多个值意味着那些值必须被封装成一种特殊的数据结构,而这种数据结构也许仅仅就在这个函数中使用一次(这种情况下显得有点浪费)。 在Haskell中,仅仅需要返回一个元组就够了。

Haskell记录常常达到同样的目的,但是你将不得不指定元素的名字。我们将在接下来的学习中与记录不期而遇。

你也可将元组视为一种原子数据结构。 这需要对类型有所了解,而到我们还没说到那。

从元组中取出数据

在本节中,我们的注意力将仅仅集中在包含2个元素的元组上。虽然这主要是为了简化,但2个元素的元组确实是被使用最多的一种元组。

好的,我们已经看到,简单地使用(x, y, z)语法,可以把数值放进元组。我们怎样再把它们取出来?例如,元组的一个典型用途是储存一个点的(x, y)坐标:想像你有一个棋盘,而你想要指定一个特定的方格。你可以通过给所有的行打上从1到8的标签来做到,列同理,然后说,(2, 5)代表第2行第5列。我们要定义一个能找出一个给定列中所有点的函数。方法之一是找到所有点的坐标,然后看行部分是否等于我们要找的行。一旦有了一个点的坐标(x, y),这个函数将需要提取x(行部分)。这里有两个函数可以做到,fstsnd,它们分别“投影”出一个对中的第一和第二个元素(用数学语言来说,从结构体中取出数据的函数叫做“投影”(Projection))。让我们来看一些例子:

Example

例子: 使用fstsnd

Prelude> fst (2, 5)
2
Prelude> fst (True, "boo")
True
Prelude> snd (5, "Hello")
"Hello"


以上函数的功能容易明白。但是要注意的是fstsnd只能使用到长度为2的元组中。[3]

练习
  1. 使用fstsnd的组合将4从(("Hello", 4), True)中取出。
  2. 思考列表 [(4, 'a'),(5,'b')] 与 列表 [(4, 1),(5, 2)] 之间的区别。

将元素从元组中取出的通用技巧是模式匹配(是的,由于这是一个函数式编程的出众特征,我们过些时候将深入讨论)。为避免使事情比原本的更复杂,让我们仅仅向你展示我怎么写一个和fst有同样功能、命名为first的函数:

Example

例子: first的定义

 Prelude> let first (x, y) = x
 Prelude> first (3, True) 
 3


这就是说如果输入(x, y)first (x, y)会返回x

元组组成的元组(以及其它组合)

我们可以像在列表中储存列表一样来操作元组。元组也是数据,所以你可以在元组中储存元组(嵌套在元组中直到任意复杂的级别)。同样,你也可以创建元组组成的列表,列表组成的元组,以下例子的每一行分别表达了一中不同的组合方法。

Example

例子: 嵌入元组和列表

((2,3), True)
((2,3), [2,3])
[(1,2), (3,4), (5,6)]


一些相关讨论——你更应该从中看到数据分组的重要思想

无论如何,这里还有一个难点需要当心。决定元组类型的不仅有它的大小,还有它其中所包含的元素的类型。例如,("Hello",32)(47,"World")是完全不同的两个类型。一个是(String,Int)类型的元组,然而另一个是(Int,String)。因此我们在构造包含元组的列表时,只能构建形如[("a",1),("b",9),("c",9)]这样的列表,而[("a",1),(2,"b"),(9,"c")]就是错误的。你能指出其中的区别吗?

练习
  1. 以下哪些是正确的Haskell表达式,为什么?
    • fst [1,2]
    • 1:(2,3)
    • (2,4):(2,3)
    • (2,4):[]
    • [(2,4),(5,5),('a','b')]
    • ([2,4],[2,2])

概要

在这一章我们已经介绍了两种新的记法,列表和元组。总结一下:

  1. 列表用方括号和逗号定义:[1,2,3].
    • 它们可以包含任意数据,只要这个列表的所有元素都属于相同类型
    • 也可以用cons操作符(:)来创建它们,但是你只能附加(cons)数据到列表
  2. 元组用圆括号和逗号定义:("Bob",32)
    • 它们可以包含任意数据,甚至不同类型的数据
    • 它们有一个固定的长度,或者至少它们的长度被它们的类型决定。就是说,两个不同长度的元组有不同的类型。
  3. 列表和元组可以任意方式嵌套:列表组成的列表,元组组成的列表,等等

我们希望在这一刻,你已经能熟练运用Haskell的基本构建(变量,函数,列表),因为我们现在会转移到一些更振奋人心的主题,类型和递归。 类型,虽然我们已经在这一章提及了三次,但是却没有明确说明它是什么。 在解释什么是类型前,我们还是先对GHC作一个介绍,使你能更好地使用GHC解释器。

提示

  1. 你应该反对因为你认为那甚至不是一个正确的单词。好的,它不是。在程序员中,一个由LISP开始的传统是把这种追加元素到列表头部的操作称为"consing"。因为这是一种构造列表的方式,所以这个动词在这里是"cons",也就是"constructor"(构造)的简写。
  2. 这至少涉及到类型,但是我们正试着避免使用这个词 :)
  3. 更专业的说,fstsnd有限制它们配对的类型。你将不能定义通用的以元组为参数的射影函数(projection function),因为它们将不得不接受不同大小的数据,从而使这个函数的类型多样化。



可打印版本
习题解答
Haskell基础

起步  >> 变量和函数  >> 列表和元组  >> 更进一步  >> 类型基础  >> 简单的输入输出  >> 类型声明


Haskell

Haskell基础 >> 初级Haskell >> Haskell进阶 >> Monads
高级Haskell >> 类型的乐趣 >> 理论提升 >> Haskell性能


库参考 >> 普通实务 >> 特殊任务


提示


更进一步

Haskell文件

到现在,我们已经多次使用了GHC解释器。它的确是一个有用的调试工具。但是接下来的课程如果我们直接输入所有表达式是麻烦的。所以现在我们开始写第一个Haskell源文件。

在你最喜爱的编辑器中打开一个文件Varfun.hs(hs是Haskell的简写)然后把下面的定义粘贴进去。Haskell使用缩进和空格来决定函数(及其它表达式)的开始和结束,所以确保没有前置的空格并且缩进是正确的,否则GHC将报错。

area r = pi * r^2

(为避免你的疑虑,pi事实上已经被Haskell定义,不需要在这里包含它了)。现在转到你保存文件的目录,打开ghci,然后使用 :load(或者简写为 :l):

Prelude> :load Varfun.hs
Compiling Main             ( Varfun.hs, interpreted )
Ok, modules loaded: Main.
*Main> 

如果ghci给出一个错误,"Could not find module 'Varfun.hs'"(“找不到模块'Varfun.hs'”),那么使用:cd来改变当前目录到包含Varfun.hs的目录:

Prelude> :cd c:\myDirectory
Prelude> :load Varfun.hs
Compiling Main             ( Varfun.hs, interpreted )
Ok, modules loaded: Main.
*Main> 

现在你可以执行文件中的函数:

*Main> area 5
78.53981633974483

如果你修改了文件,只需使用:reload(简写为 :r)来重新载入文件。

注解

GHC也可以用作编译器。就是说你可以用GHC来把你的Haskell文件转换为一个独立的可执行程序。详情见其文档。

你将注意到直接在ghci输入语句与从文件载入有一些不同。这些不同现在看来可能非常随意,但它们事实上是十分明智的范围的结果,其余的,我们保证将晚点解释。

没有let

初学者要注意,源文件里不要像这样写

let x = 3
let y = 2
let area r = pi * r ^ 2

而是要像这样写

x = 3
y = 2
area r = pi * r ^ 2

关键字let事实上在Haskell中用的很多,但这里不强求。在这一章讨论let绑定的用法后,我们将看得更远。

不能定义同一个量两次

先前,解释器高兴地允许我们像这样写

Prelude> let r = 5
Prelude> r
5
Prelude> let r = 2
Prelude> r
2

另一方面,在源文件里像这样写不对

--这不对
r = 5
r = 2

像我们先前提及的那样,变量不能改变,并且当你写一个源文件时甚至更关键。这里有一个漂亮的暗示。它意味着:

顺序不重要

你声明变量的顺序不重要。例如,下面的代码片段可以得到完全同样的结果:

 y = x * 2
 x = 3
 x = 3
 y = x * 2

这是Haskell和其它函数式编程语言的一个独特的特性。变量不可改变的事实意味着我们随意选择以任何顺序写代码(但是这也是我们不能声明一个量一次以上的原因--否则那将是模棱两可的的)。

练习
把你在上一章写的作业保存在一个Haskell文件中。在GHCi中载入这个文件并用一些参数测试里面的函数

关于函数的更多特性

当我们开始使用源文件工作而不只是在解释器中敲一些代码时,定义多个子函数会让工作变得简单。 让我们开始见识Haskell函数的威力吧。

条件表达式

if / then / else

Haskell支持标准的条件表达式。我们可以定义一个参数小于时返回、参数等于时返回、参数大于时返回的函数。事实上,这个函数已经存在(被称为符号(signum)函数),但是让我们定义一个我们自己的,把它叫做mySignum

mySignum x =
    if x < 0 then 
        -1
    else if x > 0 then 
        1
    else 
        0

我们可以这样像这样测试它:

Example

例子:

*Main> mySignum 5
1
*Main> mySignum 0
0
*Main> mySignum (5-10)
-1
*Main> mySignum (-1)
-1

注意最后一个测试“-1”两边的括弧是必需的;如果没有,系统将认为你正试图将值“mySignum”减去“1”,而这是错误的。

Haskell中的结构与大多数其它编程语言非常相似;无论如何,你必须同时有一个then一个else子句。在执行条件语句后如果它的值为True,接着会执行then部分;在执行条件语句后如果它的值为False,接着会执行else部分。

你可以把程序修改到文件里然后重新装载到GHCI中,除了可以用命令:l Varfun.hs 重新装载外,你还可以通过更快捷更简单的方法:reload:r 把当前已经载入的文件重新载入。

case

Haskell跟很多语言一样提供了 case 结构用于组合多个条件语句。(case其实有更强大的功能 -- 详情可以参考 模式匹配).


假设我们要定义一个这样的函数,如果它的参数为它会输出;如果它的参数为它会输出;如果它的参数为它会输出;如果它的参数为其它,它会输出。如果使用if 语句我们会得到一个可读性很差的函数。但我们可以用case语句写出如下形式可读性更强的函数:


f x =
    case x of
      0 -> 1
      1 -> 5
      2 -> 2
      _ -> (-1)

在这个程序中,我们定义了函数f它有一个参数x,它检查x的值。如果它的值符合条件那么f的值为,如果它的值符合条件那么f的值为,如此类推。如果x不符合之前任何列出的值那么f的值为"_"为“通配符”表示任何值都可以符合这个条件)


注意在这里缩进是非常重要的。Haskell 使用一个叫“layout"的布局系统对程序的代码进行维护(Python 语言也使用一个相似的系统)。这个布局系统允许我们可以不需要像C,Java语言那样加分号跟花括号来对代码段进行分割。



缩进

更多了解请到 缩进。 有人不喜欢使用使用缩进的布局方法,而使用分号跟花括号的方法。如果使用这种方法,以上的程序可以写成以下的形式:

f x = case x of
        { 0 -> 1 ; 1 -> 5 ; 2 -> 2 ; _ -> -1 }

当然, 如果你使用分号跟花括号的布局方法, 你可以更随意地编写你的代码。以下的方式是完全可以的。

f x =
    case x of { 0 -> 1 ;
      1 -> 5 ; 2 -> 2
   ; _ -> -1 }

但是用这种方法有时候代码可读性是很差的。(譬如在以上情况下)

为不同参数定义一个函数

函数也可以通过分段定义的方法进行定义,也就是说你可以为不同个参数定义同一个函数的不同版本。例如,以上的函数f可以写成一下方式

f 0 = 1
f 1 = 5
f 2 = 2
f _ = -1

就跟以上的case语句一样,函数的执行是与定义的顺序有关的。如果我们把最后的一行移到最前面,那么无论参数是什么,函数f的值都会是-1,无论是0 ,1 ,2 (大部分编译器会对这种参数定义重合发出警告)。如果我们不使用f _ = -1,当函数遇到 0 ,1 ,2 以外的参数时会抛出一个错误(大部分编译器也会会发出警告)。这种函数分段定义的方法是非常常用的,而且会经常在这个教程里面使用。以上的方法跟case语句实质上是等价的 —— 函数分段定义将被翻译成case语句

函数合成

复杂的函数可以通过简单的函数相互合成进行构建。函数合成就是把一个函数的结果作为另一个函数的参数。其实我们曾经在起步那一章见过,5*4+3就是两个函数合成。在这个例子中先执行,然后执行的结果作为 参数,最后得出结果。我们也可以把这种方法应用到squaref

square x = x^2
Example

例子:

*Main> square (f 1)
25
*Main> square (f 2)
4
*Main> f (square 1)
5
*Main> f (square 2)
-1

每一个函数的结果都是显而易见的。在例子的第一句中括号是非常必要的;不然,解释器认为你要尝试得到square f的值,但这显然没有意义。函数的这种合成方式普遍存在于其它编程语言中。在Haskell中有另外一种更数学化的表达方法:(.) 点函数。点函数源于数学中的()符号。


注解

在数学里我们用表达式 表达 "f following g." 在Haskell , 代码f . g 也表达为 "f following g."

其中 等同于


(.)函数(函数的合成函数),将两个函数合称为一个函数。例如,(square . f)表示一个有一个参数的函数,先把这个参数代入函数f,然后再把这个结果代入函数square得到最后结果。相反地,(f . square)表示一个有一个参数的函数,先把这个参数代入函数square,然后再把这个结果代入函数f得到最后结果。我们可以通过一下例子中的方法进行测试:

Example

例子:

*Main> (square . f) 1
25
*Main> (square . f) 2
4
*Main> (f . square) 1
5
*Main> (f . square) 2
-1

在这里,我们必须用括号把函数合成语句括起来;不然,如(square . f) 1Haskell的编译器会认为我们尝试把squaref 1的结果合成起来,但是这是没有意义的因为f 1甚至不是一个函数。

现在我们可以稍稍停下来看看在Prelude中已经定义的函数,这是十分明智的。因为很有可能把已经在Prelude中定义了的函数,自己却不经意再定义一遍(我已经不记得我这样做了多少遍了),这样浪费掉了很多时间。

let绑定

我们经常在函数中声明局部变量。 如果你记得中学数学课的内容,这里有一个例子, 一元二次方程可以用下列等式求解

我们将它转换为函数来得到:的两个值

roots a b c =
    ((-b + sqrt(b*b - 4*a*c)) / (2*a),
     (-b - sqrt(b*b - 4*a*c)) / (2*a))

请注意我们的定义中有一些冗余,不如数学定义优美。在函数的定义中我们重复了sqrt(b*b - 4*a*c)。 用Haskell的局部绑定(local binding)可以解决这个问题。也就是说我们可以在函数中定义只能在本函数中使用的值。 我们来创建sqrt(b*b-4*a*c)的局部绑定disc,并在函数中替换sqrt(b*b - 4*a*c)

我们使用了let/in来声明disc:

roots a b c =
    let disc = sqrt (b*b - 4*a*c)
    in  ((-b + disc) / (2*a),
         (-b - disc) / (2*a))

在let语句中可以同时声明多个值,只需注意让它们有相同的缩进就可以:

roots a b c =
    let disc = sqrt (b*b - 4*a*c)
        twice_a = 2*a
    in  ((-b + disc) / twice_a,
         (-b - disc) / twice_a)



可打印版本
习题解答
Haskell基础

起步  >> 变量和函数  >> 列表和元组  >> 更进一步  >> 类型基础  >> 简单的输入输出  >> 类型声明


Haskell

Haskell基础 >> 初级Haskell >> Haskell进阶 >> Monads
高级Haskell >> 类型的乐趣 >> 理论提升 >> Haskell性能


库参考 >> 普通实务 >> 特殊任务


类型基础

类型在编程中是一种分组相似值的方法。在Haskell中,类型系统是一种确保你的代码中存在更少错误的强有力的途径。

介绍

编程处理不同的条目。例如,考虑把两个数相加:

2 + 3

2和3是什么?很清楚,它们是数。但是这个添加在中间的加号是什么?当然不是一个数。那它又是什么?

类似地,考虑一个程序问你的名字,然后说“Hello”。你的名字和Hello这个词都不是数字。它们是什么?我们应该提及所有的句子和段落等等作为文本。事实上,编程时使用的一个稍微更秘密的词“String”,要更普通。

Haskell中,规则是所有的类型名必须以一个大写字母开始。今后我们应该坚持这个转变。

如果你之前曾经设置过一个数据库,你将可能遇到过类型。例如,说我们在一个数据库中有一个表来存储一个人的详细联系信息;一种个人电话本。它的内容应该像这样:

电话号码 地址
743756 北京新天地小区22#1B
655523 上海蓝玛仁小区99#3B

字段中包含着值。“李”是一个值,“上海蓝玛仁小区99#3B”是一个值,“655523”也是一个值。如此说来,类型是用以分辨数据的标准。上表中有何类型?一二行的名和姓属于文字,所以这二个值的类型是String(字符串)。第三行是一个以名来定的值,电话号码。此值的类型是Number(数字)。

初看之下,地址行的值也是String类型的。然而事实上地址相当复杂。地址中有许多约定俗成的意义在。比如说,地址最后的一部分,通常是房间号,如果不是,也可能是信箱号,但总之是一个人的最详细地址。简单点说,此处的意义不止Text(文本)本身那点可怜的意义。我们可以说地址属于Text;这没什么关系。然而声明它属于另一种类型,比如Address,会更科学。如果我们知道某些数据时Text,这通常于事无补。然而若知道它属于Address,我们立刻就可以对它有更多解读。

这道理我们可以用在电话号码行上。故,TelephoneNumber这种类型产生了。以后我们要是再看到一串数字,只要知道是TelephoneNumber的类型,就会明白这不止是一串数字,而意会更多的信息。

不把TelephoneNumber看做Number(数字)类型的另一个原因是数字可以进行数学运算。那一个TelephoneNumber和1相加又有什么意义呐?电话可不会帮你转接张三的弟弟张四。因此把电话号码做成一种更强的类型而不仅仅是一个数字是有足够的理由的。而且,电话号码中的每个数字都是很重要的,不能多也不能少,所以没有四舍五入的说法,在电话号码前面加0就更是匪夷所思了。另一个理由是可能需要指定区号的位置,添加国家码。这样,最好的办法就是抽象出一个单独的类型。

为什么类型有用

到现在,我们都好像只是在搞搞分类,几乎没有一点可以让现代计算机语言设计者吸收之处。别急,下一篇,我们会探究Haskell如何善用类型,使程序员获益。

使用交互式的:type命令

字符和字符串

在Haskell中,探寻类型如何发挥作用的最好方法是使用 GHCi 。运行之,来了解一下 :type 命令。

Example

例子: 在GHCi中对字符使用 :t 命令

Prelude> :type 'H'
'H' :: Char


提示: :type 命令可缩写为 :t

这就是我们的使用方式。在 GHCi中,它会对一个值给出其类型。此例中,我们给了一个字符 'H' ——一个包在单引号里的字母 H ,GHCi 显示了它,其后跟着"::" ,也就是“类型是”的意思。整句话的意思是: 'H' 的类型是 Char 。

如果想给出一个字符串,要用双引号括起来。

Example

例子: 在GHCi中对字符串使用 :t 命令

Prelude> :t "Hello World"
"Hello World" :: [Char]


这次,我们给出的是一个用双引号括起来的文本,GHCi的反应是: "Hello World" :: [Char] 。[Char] 意思是“字符构成的表”。注意区别 Char 和 [Char] ——带方括号的被用来构造文字列表。

练习
  1. 试用 :type 查询 "H" 的类型(注意双引号的使用),返回什么?为什么?.
  2. 试用 :type 查询 'Hello World' 的类型(注意单引号的使用),返回什么?为什么?.


在Haskell中字符串实质就是字符列表。在Haskell中可以用几种方法初始化字符串: 用双引号(ANSI 34)括起的连续的字符; 也可以像构建列表那样用":"将多个字符连接起来从而构成一个字符串,如 'H':'e':'l':'l':'o':[]; 还可以使用字符列表的形式来构建。

Haskell 有一个同义类的概念。就像英语里面的 'fast' 与 'quick', 两者意义相同,在Haskell中这种字面不同,但意义相同的两个类称为同义类(type synonyms)。就是说能使用 [Char]的地方一样能用 String来代替,如:

"Hello World" :: String

这样的表达也是正确的 。从这里开始我们将会更多的使用String,而不是[Char]来表示字符串。

布尔值

另一种在其他语言中很常见的类型是布尔型(Boolean),或简称Bool。这是一种十分有用的类型。这种类型有两个值:True 或 False(对或错)。例如一个程序向使用者询问一个名字并在一个文件中查找这个名字相关项目。这时候如果我们有一个函数 nameExists用来确认这个名字是否存在是十分方便的。如果名字存在,可以用True来表达,如果名字不存在可以将结果表达为False。要注意的是在Haskell中布尔值是头字母大写的(其中的原因在逐步深入后会变得清晰)

Example

例子: 在GHCI中探索 True 与 False的类型

Prelude> :t True
True :: Bool
Prelude> :t False
False :: Bool


这里就不用太多的解释了。 True 与 False 被归类为布尔型。

数值类型

如果你已经使用:t对所有你已经熟悉的值进行查询,可能你会发现对5进行查询会返回如下的复杂类型。


Prelude> :t 5
5 :: (Num t) => t


简单来说,有很多数型(整数,小数等)而5可以属于不同的数型。这个看起来比较复杂的类型与Haskell的类型类特性有关。我们将会在以后的章节详细解释这种复杂的类型表示。

函数类型

So far, the types we have talked about apply to values (strings, booleans, characters, etc), and we have explained how types not only help to categorize them, but also describe them. The next thing we'll look at is what makes the type system truly powerful: We can assign types not only to values, but to functions as well[1]. Let's look at some examples.

之前我们展示了类型是如何应用在值(字符串,布尔值,字符,等)上的,可以看出Haskell中的类型不只是简单用于分分类,而且可用以描述值的特性。接着我们介绍,使类型系统真正强大的特性 -- 类型不只能应用在值上,还能应用在函数上 [2]。让我们看几个例子.

例子:not

Example

例子: Negating booleans

not True  = False
not False = True


not is a standard Prelude function that simply negates Bools, in the sense that truth turns into falsity and vice versa. For example, given the above example we gave using Bools, nameExists, we could define a similar function that would test whether a name doesn't exist in the spreadsheet. It would likely look something like this:

not是一个标准的Prelude函数。功能就是把True变成False,False变成True。这里重新使用之前使用过的nameExists例子,重新定义一个相似的函数,但是这个函数是检验名字(not)是否"不"存在于电子数据表中。如下:

Example

例子: nameDoesntExist: using not

nameDoesntExist name = not (nameExists name)


To assign a type to not we look at two things: the type of values it takes as its input, and the type of values it returns. In our example, things are easy. not takes a Bool (the Bool to be negated), and returns a Bool (the negated Bool). Therefore, we write that:

要为not写一个类型标记我们关心两个方面:输入的值的类型,输出的值的类型。在我们的例子中,给not一个布尔型的值,然后返回一个布尔型的值。一次我们可以为not写出一下的类型标记:

Example

例子: not的类型标记

not :: Bool -> Bool
注意: not是类型标记的一部分。


You can read this as 'not is a function from things of type Bool to things of type Bool'.

我们可以这样来描述这个类型标记: not函数取一个布尔值作为输入,返回一个布尔值。

例子:unlinesunwords

A common programming task is to take a list of Strings, then join them all up into a single string, but insert a newline character between each one, so they all end up on different lines. For example, say you had the list ["Bacon", "Sausages", "Egg"], and wanted to convert it to something resembling a shopping list, the natural thing to do would be to join the list together into a single string, placing each item from the list onto a new line. This is precisely what unlines does. unwords is similar, but it uses a space instead of a newline as a separator. (mnemonic: un = unite)

程序设计中有一种任务很常见,这就是对一个字符串列表含有的每个元素添加换行符,再将它们连接成一个新的字符串。例如,对于列表 ["Bacon", "Sausages", "Egg"],我们希望把它合并为一个采购清单,对此,最直接的方法是,将列表中的每一项放入一个新行。这种方法就是unlinesunwords与它类似,区别在于后者用空格代替换行。(助记符: un = unite)

Example

例子: unlines and unwords

Prelude> unlines ["Bacon", "Sausages", "Egg"]
"Bacon\nSausages\nEgg\n"
Prelude> unwords ["Bacon", "Sausages", "Egg"]
"Bacon Sausages Egg"


Notice the weird output from unlines. This isn't particularly related to types, but it's worth noting anyway, so we're going to digress a little and explore why this is. Basically, any output from GHCi is first run through the show function, which converts it into a String. This makes sense, because GHCi shows you the result of your commands as text, so it has to be a String. However, what does show do if you give it something which is already a String? Although the obvious answer would be 'do nothing', the behaviour is actually slightly different: any 'special characters', like tabs, newlines and so on in the String are converted to their 'escaped forms', which means that rather than a newline actually making the stuff following it appear on the next line, it is shown as "\n". To avoid this, we can use the putStrLn function, which GHCi sees and doesn't run your output through show.

请注意unlines的输出格式。虽与本章内容无关,我们将稍微解释一下这种格式。GHCi的所有输出,都首先利用show函数,此函数将输出转化为一个字符串。这是因为GHCi将把你命令的结果作为文本输出。如果输出已经是字符串了,show函数将做什么?毫无疑问,它什么都不会做;但具体行为上,与“什么都不会做”略有不同:字符串中出现的特殊字符,如tab,换行等,将被转义为\t,\n等格式。为了避免这种情况,可以使用putStrLn函数,这样将不会像平常一样默认调用show函数

Example

例子: Using putStrLn in GHCi

Prelude> putStrLn (unlines ["Bacon", "Sausages", "Egg"])
Bacon
Sausages
Egg

Prelude> putStrLn (unwords ["Bacon", "Sausages", "Egg"])
Bacon Sausages Egg


The second result may look identical, but notice the lack of quotes. putStrLn outputs exactly what you give it (actually putStrLn appends a newline character to its input before printing it; the function putStr outputs exactly what you give it). Also, note that you can only pass it a String. Calls like putStrLn 5 will fail. You'd need to convert the number to a String first, that is, use show: putStrLn (show 5) (or use the equivalent function print: print 5).

第二个结果看起来似乎一致,但不要忘记它少了引号。putStrLn函数将严格输出你给它的东西(但实际上,putStrLn会给自己的输出自动加个换行符,putStr才会给出真正严格的输出)。同时,注意它将仅仅接受一个字符串作为参数。诸如putStrLn 5的函数调用将会失败,你必须将数字5转化为字符串才行,例如putStrLn (show 5) (或者print: print 5))

Getting back to the types. What would the types of unlines and unwords be? Well, again, let's look at both what they take as an argument, and what they return. As we've just seen, we've been feeding these functions a list, and each of the items in the list has been a String. Therefore, the type of the argument is [String]. They join all these Strings together into one long String, so the return type has to be String. Therefore, both of the functions have type [String] -> String. Note that we didn't mention the fact that the two functions use different separators. This is totally inconsequential when it comes to types — all that matters is that they return a String. The type of a String with some newlines is precisely the same as the type of a String with some spaces.

现在让我们回到类型上来。unlinesunwords 是什么类型?观察它们的输入和输出,注意到这两个函数都将接受一个字符串列表,所以,它们的输入参数类型为[String]。处理并连接列表后,它们都将输出一个较长的字符串。所以,这两个函数的类型是 [String] -> String。注意,我们并未提及这两个函数用于连接的字符的不同,因为这对类型来说是微不足道的,它们都将输出一个字符串,含有换行的字符串的类型和含有空格的字符串的类型是一致的。

例子:chrord

文字處理是計算機的一個問題. 當一切東西都到達最底層的時候, 計算機所知道的僅僅是1和0, 正如其在二進制下工作. 然而直接操作二進制並不方便, 人們開始讓計算機保存文字信息. 每個字符應該先轉換為數字, 然後再轉換為二進制來存儲. 因此, 文字, 或者說一串字符, 能夠被編碼為二進制. 一般來說, 我們只是關心字符如何用數字來表示, 因為再將數字轉為二進制將會非常容易.


轉換字元變成數字這件事是簡單的,只要將所有可能的字元寫下來,然後每個字元給一個數字。舉例來說,我們可能給予字元 'a' 對應到 1, 字元 'b' 對應到2, 依此類推。這件事有一個稱為ASCII標準已經幫我們做了,有128個標準常用的字元,數字都被編碼在 ASCII 的表格裡面。但是當我們每次需要用到一個字元時,都需要從表格中去把這些字元對應的數字找出來,或從數字中找出這些字元來,這真是一件無聊的事。所以,我們可以用兩個函式來幫我們解決這個問題,chr(發音是 'char') 以及 ord

Example

例子: Type signatures for chr and ord

chr :: Int  -> Char
ord :: Char -> Int


記得我們之前說過Haskell有多少數字類型么? 最簡單的是Int類型, 它表示一個整數, to give them their proper name. [3] 記得上面類型標識么? 回憶一下上面的not是怎麼工作的. 我們先是看到函數的參數類型, 然後是其返回類型. chr函數(返回對應數字編碼的字符)的類型標識表示其接受一個Int類型的參數, 並返回一個Char. 執行反操作的是ord函數(返回對應字符的數字編碼).

具體來說, 參考以下幾個調用chrord的例子, 你可以看到這些類型是如何工作得. 注意這兩個函數並不是內建函數, 而是在Data.Char模塊中的, 因此你需要使用:m (:module的縮寫)命令來加載之.

Example

例子: Function calls to chr and ord

Prelude> :m Data.Char
Prelude Data.Char> chr 97
'a'
Prelude Data.Char> chr 98
'b'
Prelude Data.Char> ord 'c'
99


多参数函数

So far, we've only worked with functions that take a single argument. This isn't very interesting! For example, the following is a perfectly valid Haskell function, but what would its type be?

到目前为止,我们只使用只有一个参数的函数。这太没趣了。例如,下面就是一个完全有效的Haskell函数,但是它是什么类型的呢?

Example

例子: A function in more than one argument

f x y = x + 5 + 2 * y


As we've said a few times, there's more than one type for numbers, but we're going to cheat here and pretend that x and y have to be Ints.

正如前面说的,数字可以表达为多种类型,只是我们在这里假装 x 和 y 必须是 Int 的。

There are very deep reasons for this, which we'll cover in the chapter on Currying.

这种做法有着深层次的原因。我们将在Currying一章中进行解读。

The general technique for forming the type of a function in more than one argument, then, is to just write down all the types of the arguments in a row, in order (so in this case x first then y), then write -> in between all of them. Finally, add the type of the result to the end of the row and stick a final -> in just before it. So in this case, we have:

对多参数函数来说最普遍的方式是把所有参数的类型都写在同一行,按字母排序(所以在这个例子中 x先于y),在它们中间插入->。最后,在行尾写上结果的类型并且在它前面加最后一个->。所以在这个例子中,我们有:

-->
  1. Write down the types of the arguments. We've already said that x and y have to be Ints, so it becomes:
    Int             Int
    ^^ x is an Int  ^^ y is an Int as well
    
  2. Fill in the gaps with ->:
    Int -> Int
  3. Add in the result type and a final ->. In our case, we're just doing some basic arithmetic so the result remains an Int.
    Int -> Int -> Int
                  ^^ We're returning an Int
        ^^ There's the extra -> that got added in 

现实例子:openWindow

A library is a collection of common code used by many programs.

As you'll learn in the Practical Haskell section of the course, one popular group of Haskell libraries are the GUI ones. These provide functions for dealing with all the parts of Windows or Linux you're familiar with: opening and closing application windows, moving the mouse around etc. One of the functions from one of these libraries is called openWindow, and you can use it to open a new window in your application. For example, say you're writing a word processor like Microsoft Word, and the user has clicked on the 'Options' button. You need to open a new window which contains all the options that they can change. Let's look at the type signature for this function [4]:

Example

例子: openWindow

openWindow :: WindowTitle -> WindowSize -> Window


Don't panic! Here are a few more types you haven't come across yet. But don't worry, they're quite simple. All three of the types there, WindowTitle, WindowSize and Window are defined by the GUI library that provides openWindow. As we saw when constructing the types above, because there are two arrows, the first two types are the types of the parameters, and the last is the type of the result. WindowTitle holds the title of the window (what appears in the blue bar (XP and before) or black translucent bar (Vista) - you didn't change the color, did you? - at the top), WindowSize how big the window should be. The function then returns a value of type Window which you can use to get information on and manipulate the window.

练习

Finding types for functions is a basic Haskell skill that you should become very familiar with. What are the types of the following functions?

  1. The negate function, which takes an Int and returns that Int with its sign swapped. For example, negate 4 = -4, and negate (-2) = 2
  2. The (&&) function, pronounced 'and', that takes two Bools and returns a third Bool which is True if both the arguments were, and False otherwise.
  3. The (||) function, pronounced 'or', that takes two Bools and returns a third Bool which is True if either of the arguments were, and False otherwise.

For any functions hereafter involving numbers, you can just assume the numbers are Ints.

  1. f x y = not x && y
  2. g x = (2*x - 1)^2
  3. h x y z = chr (x - 2)

多态性的类型

So far all we've looked at are functions and values with a single type. However, if you start playing around with :t in GHCi you'll quickly run into things that don't have types beginning with the familiar capital letter. For example, there's a function that finds the length of a list, called (rather predictably) length. Remember that [Foo] is a list of things of type Foo. However, we'd like length to work on lists of any type. I.e. we'd rather not have a lengthInts :: [Int] -> Int, as well as a lengthBools :: [Bool] -> Int, as well as a lengthStrings :: [String] -> Int, as well as a...

到目前為止,我們已經看過一些具有單一型態的函式和值。然而,如果你開始在GHCi中玩 :t,你將會碰到一些型態的第一個字母不是熟悉的大寫字母。舉例來說,有一個函式用來找出列表的長度,稱作 length. 記住,[Foo] 是一個存放型態Foo的事情的列表。然而我們希望length可以使用在存放任何型態的列表。而不是用計算存放整數的列表的長度用 lengthInts :: [Int] -> Int,計算存放布尔值的列表長度用 lengthBools :: [Bool] -> Int,計算存放字串列表的長度用 lengthStrings :: [String] -> Int, 等等。

That's too complicated. We want one single function that will find the length of any type of list. The way Haskell does this is using type variables. For example, the actual type of length is as follows:

這太複雜了,我們想要有一個單一的函式,可以計算出每一種存放所有型態列表的長度,所以, Haskell 使用型態變數來解決這個問題。例如:真實的型態長度如下:

Example

例子: Our first polymorphic type

length :: [a] -> Int


We'll look at the theory behind polymorphism in much more detail later in the course.

The "a" you see there in the square brackets is called a type variable. Type variables begin with a lowercase letter. Indeed, this is why types have to begin with an uppercase letter — so they can be distinguished from type variables. When Haskell sees a type variable, it allows any type to take its place. This is exactly what we want. In type theory (a branch of mathematics), this is called polymorphism: functions or values with only a single type (like all the ones we've looked at so far except length) are called monomorphic, and things that use type variables to admit more than one type are therefore polymorphic.

例子:fstsnd

As we saw, you can use the fst and snd functions to extract parts of pairs. By this time you should be in the habit of thinking "What type is that function?" about every function you come across. Let's examine fst and snd. First, a few sample calls to the functions:

Example

例子: Example calls to fst and snd

Prelude> fst (1, 2) 
1
Prelude> fst ("Hello", False)
"Hello"
Prelude> snd (("Hello", False), 4)
4


To begin with, let's point out the obvious: these two functions take a pair as their parameter and return one part of this pair. The important thing about pairs, and indeed tuples in general, is that they don't have to be homogeneous with respect to types; their different parts can be different types. Indeed, that is the case in the second and third examples above. If we were to say:

fst :: (a, a) -> a

That would force the first and second part of input pair to be the same type. That illustrates an important aspect to type variables: although they can be replaced with any type, they have to be replaced with the same type everywhere. So what's the correct type? Simply:

Example

例子: The types of fst and snd

fst :: (a, b) -> a
snd :: (a, b) -> b


Note that if you were just given the type signatures, you might guess that they return the first and second parts of a pair, respectively. In fact this is not necessarily true, they just have to return something with the same type of the first and second parts of the pair.

代码中的类型标记

Now we've explored the basic theory behind types and types in Haskell, let's look at how they appear in code. Most Haskell programmers will annotate every function they write with its associated type. That is, you might be writing a module that looks something like this:

Example

例子: Module without type signatures

module StringManip where

import Data.Char

uppercase = map toUpper
lowercase = map toLower
capitalise x = 
  let capWord []     = []
      capWord (x:xs) = toUpper x : xs
  in unwords (map capWord (words x))


This is a small library that provides some frequently used string manipulation functions. uppercase converts a string to uppercase, lowercase to lowercase, and capitalize capitalizes the first letter of every word. Providing a type for these functions makes it more obvious what they do. For example, most Haskellers would write the above module something like the following:

Example

例子: Module with type signatures

module StringManip where

import Data.Char

uppercase, lowercase :: String -> String
uppercase = map toUpper
lowercase = map toLower

capitalise :: String -> String
capitalise x = 
  let capWord []     = []
      capWord (x:xs) = toUpper x : xs
  in unwords (map capWord (words x))


Note that you can group type signatures together into a single type signature (like ours for uppercase and lowercase above) if the two functions share the same type.

类型推断

So far, we've explored types by using the :t command in GHCi. However, before you came across this chapter, you were still managing to write perfectly good Haskell code, and it has been accepted by the compiler. In other words, it's not necessary to add type signatures. However, if you don't add type signatures, that doesn't mean Haskell simply forgets about typing altogether! Indeed, when you didn't tell Haskell the types of your functions and variables, it worked them out. This is a process called type inference, whereby the compiler starts with the types of things it knows, then works out the types of the rest of the things. Type inference for Haskell is decidable, which means that the compiler can always work out the types, even if you never write them in [5]. Let's look at some examples to see how the compiler works out types.

到目前為止,我們已經可以透過命令 :t 來看型態。然而,在你結束這章前,你正學習寫一個完美的 Hasekell 程式碼,這程式碼已經可以被編譯器接受。 換句話說,你不需要加上型別簽章。如果你沒有加上型別簽章,這不代表 Hasekell 全部忽略型別這件事。相反地,當你沒有告訴 HaseKell 你的函式或變數型別,Hasekell 會想辦法生出來。這個流程叫做型別推論。藉著它所知道的事情的型別,推論出其他事情的型別。型別推論對 Haskell來說是可決定性的,代表著編譯器總是能夠推論出型別,甚至你從沒寫過他們。


Example

例子: Simple type inference

-- We're deliberately not providing a type signature for this function
-- 我们故意不提供这个函数的类型指纹.
isL c = c == 'l'


This function takes a character and sees if it is an 'l' character. The compiler derives the type for isL something like the following:

Example

例子: A typing derivation

(==)  :: a -> a -> Bool
'l'   :: Char
Replacing the second ''a'' in the signature for (==) with the type of 'l':
(==)  :: Char -> Char -> Bool
isL   :: Char -> Bool


The first line indicates that the type of the function (==), which tests for equality, is a -> a -> Bool [6]. (We include the function name in parentheses because it's an operator: its name consists only of non-alphanumeric characters. More on this later.) The compiler also knows that something in 'single quotes' has type Char, so clearly the literal 'l' has type Char. Next, the compiler starts replacing the type variables in the signature for (==) with the types it knows. Note that in one step, we went from a -> a -> Bool to Char -> Char -> Bool, because the type variable a was used in both the first and second argument, so they need to be the same. And so we arrive at a function that takes a single argument (whose type we don't know yet, but hold on!) and applies it as the first argument to (==). We have a particular instance of the polymorphic type of (==), that is, here, we're talking about (==) :: Char -> Char -> Bool because we know that we're comparing Chars. Therefore, as (==) :: Char -> Char -> Bool and we're feeding the parameter into the first argument to (==), we know that the parameter has the type of Char. Phew!

But wait, we're not finished yet! What's the return type of the function? Thankfully, this bit is a bit easier. We've fed two Chars into a function which (in this case) has type Char -> Char -> Bool, so we must have a Bool. Note that the return value from the call to (==) becomes the return value of our isL function.

So, let's put it all together. isL is a function which takes a single argument. We discovered that this argument must be of type Char. Finally, we derived that we return a Bool. So, we can confidently say that isL has the type:

Example

例子: isL with a type

isL :: Char -> Bool
isL c = c == 'l'


And, indeed, if you miss out the type signature, the Haskell compiler will discover this on its own, using exactly the same method we've just run through.

使用类型标记的原因

So if type signatures are optional, why bother with them at all? Here are a few reasons:

  • Documentation: the most prominent reason is that it makes your code easier to read. With most functions, the name of the function along with the type of the function is sufficient to guess at what the function does. (Of course, you should always comment your code anyway.)
  • Debugging: if you annotate a function with a type, then make a typo in the body of the function, the compiler will tell you at compile-time that your function is wrong. Leaving off the type signature could have the effect of allowing your function to compile, and the compiler would assign it an erroneous type. You wouldn't know until you ran your program that it was wrong. In fact, this is so important, let's explore it some more.

类型防止错误发生

假如你有以下几个函数:

Example

例子: Type inference at work

fiveOrSix :: Bool -> Int
fiveOrSix True  = 5
fiveOrSix False = 6

pairToInt :: (Bool, String) -> Int
pairToInt x = fiveOrSix (fst x)


Our function fiveOrSix takes a Bool. When pairToInt receives its arguments, it knows, because of the type signature we've annotated it with, that the first element of the pair is a Bool. So, we could extract this using fst and pass that into fiveOrSix, and this would work, because the type of the first element of the pair and the type of the argument to fiveOrSix are the same.

This is really central to typed languages. When passing expressions around you have to make sure the types match up like they did here. If they don't, you'll get type errors when you try to compile; your program won't typecheck. This is really how types help you to keep your programs bug-free. To take a very trivial example:

Example

例子: A non-typechecking program

"hello" + " world"


Having that line as part of your program will make it fail to compile, because you can't add two strings together! More likely, you wanted to use the string concatenation operator, which joins two strings together into a single one:

Example

例子: Our erroneous program, fixed

"hello" ++ " world"


An easy typo to make, but because you use Haskell, it was caught when you tried to compile. You didn't have to wait until you ran the program for the bug to become apparent.

This was only a simple example. However, the idea of types being a system to catch mistakes works on a much larger scale too. In general, when you make a change to your program, you'll change the type of one of the elements. If this change isn't something that you intended, then it will show up immediately. A lot of Haskell programmers remark that once they have fixed all the type errors in their programs, and their programs compile, that they tend to 'just work': function flawlessly first time, with only minor problems. Run-time errors, where your program goes wrong when you run it rather than when you compile it, are much rarer in Haskell than in other languages. This is a huge advantage of a strong type system like Haskell's.

练习

Infer the types of following functions:

  1. f x y = uppercase (x ++ y)
  2. g (x,y) = fiveOrSix (isL x) - ord y
  3. h x y = pairToInt (fst x,y) + snd x + length y

提示

  1. In fact, these are one and the same concept in Haskell.
  2. 事实上, 在Haskell中值跟函数是没有理论上的区别的.
  3. 其實Haskell擁有很多種整數類型! 不過不要擔心, 我們將會在恰當的時候告訴你.
  4. This has been somewhat simplified to fit our purposes. Don't worry, the essence of the function is there.
  5. Some of the newer type system extensions to GHC do break this, however, so you're better off just always putting down types anyway.
  6. This is a slight lie. That type signature would mean that you can compare two values of any type whatsoever, but this clearly isn't true: how can you see if two functions are equal? Haskell includes a kind of 'restricted polymorphism' that allows type variables to range over some, but not all types. Haskell implements this using type classes, which we'll learn about later. In this case, the correct type of (==) is Eq a => a -> a -> Bool.



可打印版本
习题解答
Haskell基础

起步  >> 变量和函数  >> 列表和元组  >> 更进一步  >> 类型基础  >> 简单的输入输出  >> 类型声明


Haskell

Haskell基础 >> 初级Haskell >> Haskell进阶 >> Monads
高级Haskell >> 类型的乐趣 >> 理论提升 >> Haskell性能


库参考 >> 普通实务 >> 特殊任务


简单的输入输出

迄今为止这本教材已经讨论了返回数值的函数,它们很不错。但是我们怎样才能写出"Hello world"?为了给你第一印象,这里有一个Haskell版的"Hello world"程序:

Example

例子: Hello! What is your name?

main = do
  putStrLn "Please enter your name: "
  name <- getLine
  putStrLn ("Hello, " ++ name ++ ", how are you?")


这个小程序至少说明了haskell没有忘记提供输入输出功能(IO)! 因为IO会产生副作用,函数式语言基本上都在这方面存在问题。对于相同的参数,函数总是应该返回相同的结果。但是像getLine这样的函数怎么可能每次都返回相同的结果呢?在给出答案前,让我们来仔细思考一下这个问题的难点。

任何IO库至少应该提供以下功能:

  • 在屏幕上打印字符串
  • 从键盘上读取字符串
  • 向文件写入数据
  • 从文件中读取数据

这里有两个问题。 我们先考虑前面的两个例子应该是什么类型. 第一个操作 (叫它“函数”似乎不合适) 应该取一个String类型的参数并返回一些东西,它应该返回什么呢?它应该返回一个()单元,因为打印字符串本身什么都不生成。第二个操作跟第一个类似,应该返回String类型的值,但它应该不需要参数。

我们希望这两个操作是函数,但是从定义上说它们不是函数。从键盘读取字符串的操作每次都返回不同的String类型值。如果putStrLn每次都返回(),依照引用透明性,我们可以把这个函数替换为f _ = ()。很明显这样做是不能得到相同结果的。

动作(Actions)

当Philip Wadler发现monads将会是一个解决IO计算的好方法时,这个问题有了突破性的进展。实际上,monads能够解决比上述简单操作更复杂的问题。我们可以用monads来解决一大类问题,比如并发、异常、IO、非确定性等等。而且,monads也不难在编译器的层面上处理(虽然这样,编译器经常会优化monadic操作)。在某种程度上monads经常被人们误解为是难以理解的。这些我们会稍后解释,目前我们只需要知道IO使用的monads,我们可以在不了解背后理论细节的情况下使用它(其实monads理论也不是非常复杂)。目前我们可以暂时忘记monads的存在了。

就像前面说过的, 我们不能把类似“在屏幕上打印字符串”或是“从文件中读数据”的操作作为函数, 因为它们不是函数(从纯数学的角度)。因此,我们给它另一个名字:“动作”。我们不仅给它一个特殊的名字,我们还给了它一个特殊的类型。 一个非常有用的动作是putStrLn,它在屏幕上打印字符串。这个行为的类型是:

putStrLn :: String -> IO ()

跟我们想的一样,putStrLn需要一个字符串参数。那它的返回类型IO ()是什么呢?这说明这个函数是一个IO动作(这就是IO的意义)。此外,当这个动作被“执行”(或是“运行”)时,结果的类型是()

注解

实际上这个类型说明putStrLn是一个“IO monad"中的动作, 但是目前我们会先忽略它。

你现在可能已经猜到了getLine的类型:

getLine :: IO String

这个类型说明getLine是一个IO动作,执行这个动作后会返回类型为String的结果.

眼前的事情是我们怎样运行一个动作?这个看起来是编译器该干的活。你不能直接运行一个动作,而是要通过main函数执行这个动作。main函数本身也是一个动作,运行编译后的程序就会直接执行这个动作。因此,编译器要求main函数是类型IO (),也就是一个什么都不返回的IO动作。(译者:然而这并不代表程序在这个运行期间不修改外部的世界如屏幕输出,文件修改等,而是这个动作在执行完后没有任何结果给予后继程序使用)

However, while you are not allowed to run actions yourself, you are allowed to combine actions. There are two ways to go about this. The one we will focus on in this chapter is the do notation, which provides a convenient means of putting actions together, and allows us to get useful things done in Haskell without having to understand what really happens. Lurking behind the do notation is the more explicit approach using the (>>=) operator, but we will not be ready to cover this until the chapter Understanding monads

虽然,你不能直接运行一个动作,但是你可以把同类型的动作组合 combine 起来。 有两种方法可以用,其中一种方法是使用do我们将会在这章详细介绍。隐藏在do背后的 是一个更显式的方法,显式使用(>>=),我们会在Understanding monads这章详细解释。

注解

Do notation is just syntactic sugar for (>>=). If you have experience with higher order functions, it might be worth starting with the latter approach and coming back here to see how do notation gets used. 实际上do(>>=)的语法糖。如果你有使用高阶函数的经验,可以直接阅读学习第二种方法然后回来这章学习如何使用do

Let's consider the following name program:

Example

例子: What is your name?

main = do
  putStrLn "Please enter your name: "
  name <- getLine
  putStrLn ("Hello, " ++ name ++ ", how are you?")


We can consider the do notation as a way to combine a sequence of actions. Moreover, the <- notation is a way to get the value out of an action. So, in this program, we're sequencing three actions: a putStrLn, a getLine and another putStrLn. The putStrLn action has type String -> IO (), so we provide it a String, so the fully applied action has type IO (). This is something that we are allowed to run as a program.

练习

Write a program which asks the user for the base and height of a triangle, calculates its area and prints it to the screen. The interaction should look something like:

The base?
3.3
The height?
5.4
The area of that triangle is 8.91
Hint: you can use the function read to convert user strings like "3.3" into numbers like 3.3 and function show to convert a number into string.

Left arrow clarifications

左箭头说明

The <- is optional

While we are allowed to get a value out of certain actions like getLine, we certainly are not obliged to do so. For example, we could very well have written something like this:

从特定的动作如 getLine 中取值是被容许的,但并非是必要的.我们可以这样写:

Example

例子: executing getLine directly

main = do
  putStrLn "Please enter your name: "
  getLine
  putStrLn ("Hello, how are you?")


Clearly, that isn't very useful: the whole point of prompting the user for his or her name was so that we could do something with the result. That being said, it is conceivable that one might wish to read a line and completely ignore the result. Omitting the <- will allow for that; the action will happen, but the data won't be stored anywhere.

显然, 这样写没有太多用处: 提示用户输入名字是为了能利用输入结果来做一些事情. 而上面的代码却可以理解为, 进行读取一行的操作, 忽略读取结果. 忽略 <- 就是这效果; 动作发生, 但结果未在任何地方保存.

In order to get the value out of the action, we write name <- getLine, which basically means "run getLine, and put the results in the variable called name."

The <- can be used with any action (except the last)

On the flip side, there are also very few restrictions which actions can have values obtained from them. Consider the following example, where we put the results of each action into a variable (except the last... more on that later):

Example

例子: putting all results into a variable

main = do
  x <- putStrLn "Please enter your name: "
  name <- getLine
  putStrLn ("Hello, " ++ name ++ ", how are you?")


The variable x gets the value out of its action, but that isn't very interesting because the action returns the unit value (). So while we could technically get the value out of any action, it isn't always worth it. But wait, what about that last action? Why can't we get a value out of that? Let's see what happens when we try:

Example

例子: getting the value out of the last action

main = do
  x <- putStrLn "Please enter your name: "
  name <- getLine
  y <- putStrLn ("Hello, " ++ name ++ ", how are you?")

Whoops!

YourName.hs:5:2:
    The last statement in a 'do' construct must be an expression


This is a much more interesting example, but it requires a somewhat deeper understanding of Haskell than we currently have. Suffice it to say, whenever you use <- to get the value of an action, Haskell is always expecting another action to follow it. So the very last action better not have any <-s.

這是一個很有趣的例子,相對於我們現在所認知的它需要一些對 Haskell 更深入的瞭解。只要用一句話就夠了,那就是無論你何時要使用 <- 去取得一個動作的值,Hasekell 總是期待後面還會有其它動作。所以,在最後一個動作最好不要有這個 <-

Controlling actions

Normal Haskell constructions like if/then/else and case/of can be used within the do notation, but you need to be somewhat careful. For instance, in a simple "guess the number" program, we have:

    doGuessing num = do
       putStrLn "Enter your guess:"
       guess <- getLine
       if (read guess) < num
         then do putStrLn "Too low!"
                 doGuessing num
         else if (read guess) > num
                then do putStrLn "Too high!"
                        doGuessing num
                else do putStrLn "You Win!"

If we think about how the if/then/else construction works, it essentially takes three arguments: the condition, the "then" branch, and the "else" branch. The condition needs to have type Bool, and the two branches can have any type, provided that they have the same type. The type of the entire if/then/else construction is then the type of the two branches.

In the outermost comparison, we have (read guess) < num as the condition. This clearly has the correct type. Let's just consider the "then" branch. The code here is:

              do putStrLn "Too low!"
                 doGuessing num

Here, we are sequencing two actions: putStrLn and doGuessing. The first has type IO (), which is fine. The second also has type IO (), which is fine. The type result of the entire computation is precisely the type of the final computation. Thus, the type of the "then" branch is also IO (). A similar argument shows that the type of the "else" branch is also IO (). This means the type of the entire if/then/else construction is IO (), which is just what we want.

注解

In this code, the last line is else do putStrLn "You Win!". This is somewhat overly verbose. In fact, else putStrLn "You Win!" would have been sufficient, since do is only necessary to sequence actions. Since we have only one action here, it is superfluous.

It is incorrect to think to yourself "Well, I already started a do block; I don't need another one," and hence write something like:

    do if (read guess) < num
         then putStrLn "Too low!"
              doGuessing num
         else ...

Here, since we didn't repeat the do, the compiler doesn't know that the putStrLn and doGuessing calls are supposed to be sequenced, and the compiler will think you're trying to call putStrLn with three arguments: the string, the function doGuessing and the integer num. It will certainly complain (though the error may be somewhat difficult to comprehend at this point).

We can write the same doGuessing function using a case statement. To do this, we first introduce the Prelude function compare, which takes two values of the same type (in the Ord class) and returns one of GT, LT, EQ, depending on whether the first is greater than, less than or equal to the second.

doGuessing num = do
  putStrLn "Enter your guess:"
  guess <- getLine
  case compare (read guess) num of
    LT -> do putStrLn "Too low!"
             doGuessing num
    GT -> do putStrLn "Too high!"
             doGuessing num
    EQ -> do putStrLn "You Win!"

Here, again, the dos after the ->s are necessary on the first two options, because we are sequencing actions.

If you're used to programming in an imperative language like C or Java, you might think that return will exit you from the current function. This is not so in Haskell. In Haskell, return simply takes a normal value (for instance, one of type Int) and makes it into an action that returns the given value (for the same example, the action would be of type IO Int). In particular, in an imperative language, you might write this function as:

void doGuessing(int num) {
  print "Enter your guess:";
  int guess = atoi(readLine());
  if (guess == num) {
    print "You win!";
    return ();
  }

  // we won't get here if guess == num
  if (guess < num) {
    print "Too low!";
    doGuessing(num);
  } else {
    print "Too high!";
    doGuessing(num);
  }
}

Here, because we have the return () in the first if match, we expect the code to exit there (and in most imperative languages, it does). However, the equivalent code in Haskell, which might look something like:

doGuessing num = do
  putStrLn "Enter your guess:"
  guess <- getLine
  case compare (read guess) num of
    EQ -> do putStrLn "You win!"
             return ()

  -- we don't expect to get here if guess == num
  if (read guess < num)
    then do print "Too low!";
            doGuessing num
    else do print "Too high!";
            doGuessing num

First of all, if you guess correctly, it will first print "You win!," but it won't exit, and it will check whether guess is less than num. Of course it is not, so the else branch is taken, and it will print "Too high!" and then ask you to guess again.

On the other hand, if you guess incorrectly, it will try to evaluate the case statement and get either LT or GT as the result of the compare. In either case, it won't have a pattern that matches, and the program will fail immediately with an exception.

练习

What does the following program print out?

main =
 do x <- getX
    putStrLn x

getX =
 do return "hello"
    return "aren't"
    return "these"
    return "returns"
    return "rather"
    return "pointless?"
Why?
练习

Write a program that asks the user for his or her name. If the name is one of Simon, John or Phil, tell the user that you think Haskell is a great programming language. If the name is Koen, tell them that you think debugging Haskell is fun (Koen Classen is one of the people who works on Haskell debugging); otherwise, tell the user that you don't know who he or she is.

Write two different versions of this program, one using if

statements, the other using a case statement.

Actions under the microscope

Actions may look easy up to now, but they are actually a common stumbling block for new Haskellers. If you have run into trouble working with actions, you might consider looking to see if one of your problems or questions matches the cases below. It might be worth skimming this section now, and coming back to it when you actually experience trouble.

Mind your action types

One temptation might be to simplify our program for getting a name and printing it back out. Here is one unsuccessful attempt:

Example

例子: Why doesn't this work?

main =
 do putStrLn "What is your name? "
    putStrLn ("Hello " ++ getLine)

Ouch!

YourName.hs:3:26:
    Couldn't match expected type `[Char]'
           against inferred type `IO String'


Let us boil the example above down to its simplest form. Would you expect this program to compile?

Example

例子: This still does not work

main =
 do putStrLn getLine


For the most part, this is the same (attempted) program, except that we've stripped off the superflous "What is your name" prompt as well as the polite "Hello". One trick to understanding this is to reason about it in terms of types. Let us compare:

putStrLn :: String -> IO ()
getLine  :: IO String

We can use the same mental machinery we learned in Type basics to figure how everything went wrong. Simply put, putStrLn is expecting a String as input. We do not have a String, but something tantalisingly close, an IO String. This represents an action that will give us a String when it's run. To obtain the String that putStrLn wants, we need to run the action, and we do that with the ever-handy left arrow, <-.

Example

例子: This time it works

main =
 do name <- getLine
    putStrLn name

Working our way back up to the fancy example:

main =
 do putStrLn "What is your name? "
    name <- getLine
    putStrLn ("Hello " ++ name)


Now the name is the String we are looking for and everything is rolling again.

Mind your expression types too

Fine, so we've made a big deal out of the idea that you can't use actions in situations that don't call for them. The converse of this is that you can't use non-actions in situations that DO expect actions. Say we want to greet the user, but this time we're so excited to meet them, we just have to SHOUT their name out:

Example

例子: Exciting but incorrect. Why?

import Data.Char (toUpper)

main =
 do name <- getLine
    loudName <- makeLoud name
    putStrLn ("Hello " ++ loudName ++ "!")
    putStrLn ("Oh boy! Am I excited to meet you, " ++ loudName)

-- Don't worry too much about this function; it just capitalises a String
makeLoud :: String -> String
makeLoud s = map toUpper s
This goes wrong...
    Couldn't match expected type `IO' against inferred type `[]'
      Expected type: IO t
      Inferred type: String
    In a 'do' expression: loudName <- makeLoud name


This is quite similar to the problem we ran into above: we've got a mismatch between something that is expecting an IO type, and something which is not. This time, the cause is our use of the left arrow <-; we're trying to left arrow a value of makeLoud name, which really isn't left arrow material. It's basically the same mismatch we saw in the previous section, except now we're trying to use regular old String (the loud name) as an IO String, which clearly are not the same thing. The latter is an action, something to be run, whereas the former is just an expression minding its own business. Note that we cannot simply use loudName = makeLoud name because a do sequences actions, and loudName = makeLoud name is not an action.

So how do we extricate ourselves from this mess? We have a number of options:

  • We could find a way to turn makeLoud into an action, to make it return IO String. But this is not desirable, because the whole point of functional programming is to cleanly separate our side-effecting stuff (actions) from the pure and simple stuff. For example, what if we wanted to use makeLoud from some other, non-IO, function? An IO makeLoud is certainly possible (how?), but missing the point entirely.
  • We could use return to promote the loud name into an action, writing something like loudName <- return (makeLoud name). This is slightly better, in that we are at least leaving the makeLoud itself function nice and IO-free, whilst using it in an IO-compatible fashion. But it's still moderately clunky, because by virtue of left arrow, we're implying that there's action to be had -- how exciting! -- only to let our reader down with a somewhat anticlimatic return
  • Or we could use a let binding...

It turns out that Haskell has a special extra-convenient syntax for let bindings in actions. It looks a little like this:

Example

例子: let bindings in do blocks.

main =
 do name <- getLine
    let loudName = makeLoud name
    putStrLn ("Hello " ++ loudName ++ "!")
    putStrLn ("Oh boy! Am I excited to meet you, " ++ loudName)


If you're paying attention, you might notice that the let binding above is missing an in. This is because let bindings in do blocks do not require the in keyword. You could very well use it, but then you'd have to make a mess of your do blocks. For what it's worth, the following two blocks of code are equivalent.

sweet unsweet
 do name <- getLine
    let loudName = makeLoud name
    putStrLn ("Hello " ++ loudName ++ "!")
    putStrLn ("Oh boy! Am I excited to meet you, " ++ loudName)
 do name <- getLine
    let loudName = makeLoud name
    in  do putStrLn ("Hello " ++ loudName ++ "!")
           putStrLn ("Oh boy! Am I excited to meet you, " ++ loudName)
练习
  1. Why does the unsweet version of the let binding require an extra do keyword?
  2. Do you always need the extra do?
  3. (extra credit) Curiously, let without in is exactly how we wrote things when we were playing with the interpreter in the beginning of this book. Why can you omit the in keyword in the interpreter, when you'd have to put it in when typing up a source file?




Learn more

At this point, you should have the skills you need to do some fancier input/output. Here are some IO-related options to consider.

  • You could continue the sequential track, by learning more about types and eventually monads
  • Alternately: you could start learning about building graphical user interfaces in the GUI chapter
  • For more IO-related functionality, you could also consider learning more about the System.IO library



可打印版本
习题解答
Haskell基础

起步  >> 变量和函数  >> 列表和元组  >> 更进一步  >> 类型基础  >> 简单的输入输出  >> 类型声明


Haskell

Haskell基础 >> 初级Haskell >> Haskell进阶 >> Monads
高级Haskell >> 类型的乐趣 >> 理论提升 >> Haskell性能


库参考 >> 普通实务 >> 特殊任务


类型声明



Haskell has three basic ways to declare a new type:

Haskell有三种基本的方式申明一个新类:

  • The data declaration for structures and enumerations.
  • The type declaration for type synonyms.
  • The newtype declaration, which is a cross between the other two.

In this chapter, we will focus on the most essential way, data, and to make life easier, type. You'll find out about newtype later on, but don't worry too much about it; it's there mainly for optimisation.

data for making your own types

使用 data 来创建你自己的类型

Here is a data structure for a simple list of anniversaries: 这里有两个最简单的纪念日列表数据结构 :

data Anniversary = Birthday String Int Int Int       -- name, year, month, day
                 | Wedding String String Int Int Int -- partner1name, partner2name, year, month, day

This declares a new data type Anniversary with two constructor functions called Birthday and Wedding. As usual with Haskell the case of the first letter is important: type names and constructor functions must always start with capital letters. Note also the vertical bar: this marks the point where one alternative ends and the next begins; you can think of it almost as an or - which you'll remember was || - except used in types.

这里定义了一个新的数据类型 Anniversary ,它有两个 constructor (构造)函数: BirthdayWedding. 通常情况下在Haskell里,单词的第一个字母大小写是很重要的: 类型名 和 构造函数必须以大写开头.注意这里的符号'|': 它代表着一个构造函数的结束和一个可选构造函数的开始。你可以把它记成'或' -- '||',用在指定类型的时候少一竖就可以了.

The declaration says that an Anniversary can be one of two things; a Birthday or a Wedding. A Birthday contains one string and three integers, and a Wedding contains two strings and three integers. The comments (after the "--") explain what the fields actually mean.

以上声明表达的是,一个纪念日可以是生日或者结婚日。生日包含一个字符串和三个整数,然后一个结婚纪念日包含两个字符串和三个整数。注释(在符号'--'后面的文字)解释了这些参数的意义。

Now we can create new anniversaries by calling the constructor functions. For example, suppose we have John Smith born on 3rd July 1968:

现在我们可以通过调用两个构造函数来创建新的纪念日。比如,John Smith 的生日是1968年7月3号:

johnSmith :: Anniversary
johnSmith = Birthday "John Smith" 1968 7 3

He married Jane Smith on 4th March 1987:

他在1987年3月4日娶了Jane Smith:

smithWedding :: Anniversary
smithWedding = Wedding "John Smith" "Jane Smith" 1987 3 4

These two objects can now be put in a list:

这两个对象可以放在一个列表里:

anniversaries :: [Anniversary]
anniversaries = [johnSmith, smithWedding]

(Obviously a real application would not hard-code its entries: this is just to show how constructor functions work).

Constructor functions can do all of the things ordinary functions can do. Anywhere you could use an ordinary function you can use a constructor function.

Anniversaries will need to be converted into strings for printing. This needs another function:

showAnniversary :: Anniversary -> String

showAnniversary (Birthday name year month day) =
   name ++ " born " ++ showDate year month day

showAnniversary (Wedding name1 name2 year month day) =
   name1 ++ " married " ++ name2 ++ " " ++ showDate year month day

This shows the one way that constructor functions are special: they can also be used to deconstruct objects. showAnniversary takes an argument of type Anniversary. If the argument is a Birthday then the first version gets used, and the variables name, month, date and year are bound to its contents. If the argument is a Wedding then the second version is used and the arguments are bound in the same way. The parenthesis indicate that the whole thing is one argument split into five or six parts, rather than five or six separate arguments.

Notice the relationship between the type and the constructors. All versions of showAnniversary convert an Anniversary to a String. One of them handles the Birthday case and the other handles the Wedding case.

It also needs an additional showDate routine:

showDate y m d = show y ++ "-" ++ show m ++ "-" ++ show d

Of course, it's a bit clumsy having the date passed around as three separate integers. What we really need is a new datatype:

data Date = Date Int Int Int   -- Year, Month, Day

Constructor functions are allowed to be the same name as the type, and if there is only one then it is good practice to make it so.

type for making type synonyms

It would also be nice to make it clear that the strings in the Anniversary type are names, but still be able to manipulate them like ordinary strings. The type declaration does this:

type Name = String

This says that a Name is a synonym for a String. Any function that takes a String will now take a Name as well, and vice versa. The right hand side of a type declaration can be a more complex type as well. For example String itself is defined in the standard libraries as

type String = [Char]

So now we can rewrite the Anniversary type like this:

data Anniversary = 
   Birthday Name Date
   | Wedding Name Name Date

which is a lot easier to read. We can also have a type for the list:

type AnniversaryBook = [Anniversary]

The rest of the code needs to be changed to match:

johnSmith :: Anniversary
johnSmith = Birthday "John Smith" (Date 1968 7 3)

smithWedding :: Anniversary
smithWedding = Wedding "John Smith" "Jane Smith" (Date 1987 3 4)

anniversaries :: AnniversaryBook
anniversaries = [johnSmith, smithWedding]


showAnniversary :: Anniversary -> String

showAnniversary (Birthday name date) =
   name ++ " born " ++ showDate date

showAnniversary (Wedding name1 name2 date) =
   name1 ++ " married " ++ name2 ++ showDate date


showDate :: Date -> String
showDate (Date y m d) = show y ++ "-" ++ show m ++ "-" ++ show d



可打印版本
习题解答
Haskell基础

起步  >> 变量和函数  >> 列表和元组  >> 更进一步  >> 类型基础  >> 简单的输入输出  >> 类型声明


Haskell

Haskell基础 >> 初级Haskell >> Haskell进阶 >> Monads
高级Haskell >> 类型的乐趣 >> 理论提升 >> Haskell性能


库参考 >> 普通实务 >> 特殊任务



初级Haskell


递归

可打印版本 (解答)
Elementary Haskell

Template:Haskell章节/Elementary Haskell

递归这个绝妙想法是Haskell(一般也是计算机科学)的中心:即,递归是在一个函数定义的内部用到自身。有此种定义的函数叫做递归。听起来好像会导致无限重复,但只要定义适当,就不会这样。

一般来说,一个递归函数的定义有两个部分。首先,至少要有一个底线,就是一个简单的线,越过此处,递归会停止(换言之,此时函数会直接返回值,而不会继续“递归般地”调用自身。底线保证了此函数必定结束。其次,是更一般的递归区,若参数在此范围内就会以某种形式调用自身。下面是例子。

数值递归

阶乘函数

数学上,尤其是组合数学,有一个相当常用的函数叫做阶乘(Factorial)。[1]阶乘函数的参数是一个自然数,它会返回1与此数之间所有数的乘积。比如,6的阶乘是 1 × 2 × 3 × 4 × 5 × 6 = 720 。这相当有趣,因为对我们来说,它可以用一种递归函数来表示。

首先,我们比较相邻两个数的阶乘。

Example

例子: 相邻数的阶乘

Factorial of 6 = 6 × 5 × 4 × 3 × 2 × 1
Factorial of 5 =     5 × 4 × 3 × 2 × 1


注意我们是如何对齐的。明显可以看出6的阶乘和5的阶乘有关系。6的阶乘就是6 × (5的阶乘)。让我们来看另一个例子。

Example

例子: Factorials of adjacent numbers

Factorial of 4 = 4 × 3 × 2 × 1
Factorial of 3 =     3 × 2 × 1
Factorial of 2 =         2 × 1
Factorial of 1 =             1


确实,我们可以看出任何数字的阶乘就是此数字乘以比此数小1的数的阶乘。除了一个例外:0的阶乘,我们不会把0和-1的阶乘相乘。事实上,我们只是认为0的阶乘是1(我们就是这样定义的,怎么着了,你不同意?[2])。所以,0是此处递归的底线,当我们遇到0的时候,我们会立刻说答案是1,不需递归。我们可以把阶乘函数的定义简述如下。

  • 0的阶乘是1
  • 任何数的阶乘都是此数乘以比此数小一的数的阶乘。

这个在Haskell中表示为:

Example

例子: 阶乘函数

factorial 0 = 1
factorial n = n * factorial (n-1)

这就定义了一个新的叫做factorial的函数。第一行表示0的阶乘是1,第二行表示任意别的数n的阶乘等于n乘以 n-1的阶乘。注意那个把n-1括起来的括弧:没有这个括弧代码就会被解析称为(factorial n) - 1;函数行为的优先级是很高的,会最先执行。 Template:Warning

到现在为止,你都会觉得有点微妙。实际上起作用吗?来看看到底执行了factorial 3到底会发生什么事情吧:

  • 3不是0,所以“递归”(再次执行factorial函数):看2的阶乘是几(也就是factorial 3
    • 2不是0,所以“递归”
      • 1不是0,递归
        • 0就是0,所以我们返回1
      • 我们将得到的1和本来的1相乘,得到 1 ,即(1 × 1),返回它
    • 我们将得到的1和本来的2相乘,得到2,即(2 × 1 × 1),返回它
  • 我们将得到的2和本来的3相乘,得到6,即6 (3 × 2 × 1 × 1)

我们可以看出乘法如何贯穿整个递归过程。

注意,我们最终的式子中1出现了两次,因为底线是0而不是1;不过这造不成什么错误,因为乘1还会是原来的数。如果我们想让 factorial 在1处停下也办得到,但0做底线符合常理,而且会很实用。

还有一点需要注意的:两个声明(一个是factorial 0的声明,一个是factorial n的声明)的顺序很重要。Haskell会先匹配第一个句子,来决定函数的定义。所以,如果我们把两句声明掉个,第一个n语句将会匹配任何数(包括0)。所以语句 factorial 0的执行过程是去匹配情况n,于是factorial 0 的结果将会是0 * factorial (-1),然后就会没完没了。无限循环不是我们想要的。一般来说:特殊情况应该置于前,一般情况置于后。

练习
  1. 将阶乘函数键入到一个源文件中,再载入到你的Haskell环境中
    • factorial 5是几?
    • factorial 1000呢?如果你有个计算器,先用它算一算,然后看看和电脑中的一样吗?
    • 要是 factorial (-1)会如何?为何如此?
  2. 双阶乘意为:从1(或2)隔一个数字乘一个,一直乘到n。比如,8的双阶乘是 8 × 6 × 4 × 2 = 384, 7的双阶乘是 7 × 5 × 3 × 1 = 105. 定义一个双阶乘函数doublefactorial.

一次小小的跑题

此段落欲为习惯命令式语言如c或Java的用户提供指导。

在命令式语言中,“循环”是很普遍的。在命令式语言中,阶乘函数的通常写法是用一个“for”循环,如下(用c语言):

Example

例子: 命令式语言中的阶乘函数

int factorial(int n) {
  int res = 1;
  for (i = 1; i <= n; i++)
    res *= i;
  return res;
}

这在Haskell中直接实现是不可能的,因为改变变量resi的值(以一种破坏性的方式)是不可以的。然而,我们依然可以将一个循环转换为同作用的递归形式。重点是让每个需要改变的循环变量变成一个递归函数的参数。比如,以下将上个循环“直译”为Haskell。

Example

例子: 用递归模拟循环

factorial n = factorialWorker 1 n 1 where
factorialWorker i n res | i <= n    = factorialWorker (i+1) n (res * i)
                        | otherwise = res

垂直号之后的表达式叫做“guards”(卫士),更详细的可以参考control structures。现在,我们应该可以通过与以上的c语言代码相比弄懂它是如何工作的。

很明显,在Haskell中,要实现阶乘函数,这不是一个简明、优雅的方式,但我们应该也知道,这种翻译也可以实现。

另一点需要提醒的是不必担心Haskell中递归性能会很低。一般来说,函数式语言的编译器都会对递归多所优化,包括一个重要的“尾递归优化”;记住:Haskell很懒,如果不必要,就不会发生。

其他递归函数

正如它本身所揭示的,factorial函数没有什么特殊之处;一大批数学函数都可以一种自然地方式递归定义。比如,乘法。你第一次接触乘法(回忆一下那是什么时候?:)),你认为那就是“重复加”而已。就是说, 5 × 4 和加四个5的结果是一样的。当然,加四个5和先加三个5再加一个5是一样的——也就是说, 5 × 4 = 5 × 3 + 5。这让我们自然想到了乘法的递归定义形式。

Example

例子: 递归地定义乘法

mult n 0 = 0                      -- 任何数乘 0 是 0
mult n 1 = n                      -- 任何数乘 1 是它本身
mult n m = (mult n (m - 1)) + n   -- 递归体:乘个数减1再加本身

回头看看,我们可以看到数字递归式如何写成一般递归形式的。数字递归的基线通常包括一个或更多特殊数字(通常是 0 或 1 ),对这些数字,我们可以立刻给出答案。递归体中,通过调用具有更小的参数的函数,相加返回值来产生结果。“更小的参数”通常比本处的参数更小,从而导致递归会“朝着更小的数走去”(就像factorial的例子一样)。当然,更小的参数也可以由其他方式产生。

练习
  1. 展开 5 × 4 ,方式参考 factorial 3的展开。
  2. 定义一个递归函数 power ,使得 power x y 计数 xy 次幂。
  3. 已有一个函数 plusOne x = x + 1. 不使用任何 (+)(加号), 定义一个 addition,使得 addition x yxy 相加。
  4. (难) 实现函数 log2, 意思是求以 2 为底的对数。 即, log2 会计算以 2 为底的适合参数的最大的幂。比如, log2 16 = 4log2 11 = 3log2 1 = 0 。(小建议:解题之前,再看一遍最后一段。)


基于表的递归

Haskell中“很多”函数都是递归函数,尤其是跟表有关的。[3]设想一个可以计算表长度的 length 函数。

Example

例子: length的递归定义

length :: [a] -> Int
length []     = 0
length (x:xs) = 1 + length xs


别被眼花缭乱的语法弄蒙了,我们会在 模式匹配 章节更深入的了解。现在,我们把代码翻译成人话,搞懂它如何发挥作用。第一行说明了 length的类型:它允许任何表进去,并且产生一个 Int,也就是整数。下一行表示一个空表的长度是 0 。当然,这也是基线(底线)。最后一行是递归区:如果一个表包括一个第一元素 x 和表的其余部分、另外一个表 xs ,那么表的长度是 xs 的长度加1。

那么一个 (++) 函数,这个函数可以实现两个表相连,该如何实现呢?(下面给出这个运算符的几个例子,因为我们还没见到过这个功能呢。)

{{HaskellExample|<递归的code>(++)函数|

Prelude> [1,2,3] ++ [4,5,6]
[1,2,3,4,5,6]
Prelude> "Hello " ++ "world" -- Strings are lists of Chars
"Hello world"

(++) :: [a] -> [a] -> [a]
[] ++ ys     = ys
(x:xs) ++ ys = x : xs ++ ys

length 复杂点是吧,然而掰开了讲也很简单。类型句表明 (++) 函数吸收两个表,再产生一个表。基线句表明一个空表和一个名为 ys 的表连接还是表 ys 自身。最后一句,递归区把第一个表断为头部(x)和尾部(xs),然后将第一个表的尾部和第二个表连接,最后将头部 x 订在前面。

这就是模式:在基于表的函数中,基线通常和空表相关,递归区通常会把表的尾部再传回函数自身以递归,这样表会越来越小。

练习

给出以下基于表的函数的递归定义。对每一题,想想基线是什么,而递归区又如何,又如何做到参数越来越小?

  1. replicat :: Int -> a -> [a],作用是接受一个数字和一个元素,返回有此数字个元素的表。比如: replicat 3 'a' = "aaa" 。(提示:考虑下0个元素的表是什么样子,个数 0 就是你的基线。
  2. (!!) :: [a] -> Int -> a在给出的 index(指针) 处返回元素。第一个元素是 index 0第二个是 1 ,以此类推。注意在此函数中,你得对数字和表同时“递归”。
  3. (有点难度) zip :: [a] -> [b] -> [(a, b)] ,拉链函数,将每个表中对应位置的元素连在一起,组成一个大表。比如 zip [1,2,3] "abc" = [(1, 'a'), (2, 'b'), (3, 'c')] 。如果某个表比较短,则立即停止即可。如 zip [1,2] "abc" = [(1, 'a'), (2, 'b')]

递归几乎是所有表函数和数字函数的实现方法。下一次你再遇到基于表的函数时,先看看空表时的情况,再看看不空时的情况,也就知道这个算法是不是递归的了。呵呵。

不要太爱递归

虽然我们对递归有个牢固的理解很重要,但这并不意味着在Haskell中我们要时时用递归编东西。事实上,有各种各样的用递归函数标准库,你只需要使用它们就可以了。比如,一种实现factorial(阶乘)函数的简单方式是这样的:

Example

例子: 用标准库实现 factorial 函数

factorial n = product [1..n]


简直跟作弊差不多,对吧? :) 这就是有经验的 Haskell 程序员会如何写程序,他们不会动辄祭起递归这个法宝。当然, product 函数的本质就是表递归[4],但当我们用这种方式写代码的时候,不用操心其实现方式了。

概要

递归是一种在函数定义内部调用自身的一种做法。它几乎都是由两种成分构成:基线和递归区。递归在处理表和数字时特别有用。



可打印版本
习题解答
Elementary Haskell

Template:Haskell章节/Elementary Haskell

Haskell

Haskell基础 >> 初级Haskell >> Haskell进阶 >> Monads
高级Haskell >> 类型的乐趣 >> 理论提升 >> Haskell性能


库参考 >> 普通实务 >> 特殊任务


注释

  1. 在数学上,n的阶乘用n!表示,但Haskell可没有这种语法,所以这里我们不会这样用。
  2. 事实上,定义0的阶乘是1绝非任意,而是因为0的阶乘代表了 empty product.
  3. 这并非巧合,没有变量,递归是实现控制结构的唯一方法。这听起来很像限制,但只要习惯了,它绝不会碍手碍脚。
  4. 事实上,这个函数叫做 foldl ,经常被用来实现递归。


模式匹配

Haskell/模式匹配

深入列表

Haskell/深入列表

控制结构

Haskell提供了几种方式来表达在不同的值间选择。本节描述了所有的方式并解释了他们的用途:

if 表达式

你已经见过这些表达式了。完整的语法是:

if <condition> then <true-value> else <false-value>

这里,条件是一个求值后得到一个布朗型的表达式。如果<条件>True的,那么<true-value>被返回,否则<false-value>被返回。注意Haskell中if是一个(被转化为一个值的)表达式──并非如通常的命令式语言那样是一个(被执行的)语句。这个事实的一个非常重要的后果则是Haskell中else是"必须的"。由于if是一个表达式,它必须求值得到一个结果,else保证了这一点。由于同一原因,通常的缩进同命令式语言有所不同。如果你需要把一个if表达式分为数行,那你应采用下面的缩进方式之一:

if <condition>
   then <true-value>
   else <false-value>

if <condition>
   then
      <true-value>
   else
      <false-value>

下面是一个简单的例子:

message42 :: Integer -> String
message42 n =
   if n == 42
      then "The Answer is forty two."
      else "The Answer is not forty two."

case表达式

One interesting way of thinking about case expressions is seeing them as a generalization of if expressions. We could even write a clone of if as a case:

alternativeIf :: Bool -> a -> a -> a
alternativeIf cond ifTrue ifFalse =
  case cond of
    True  -> ifTrue
    False -> ifFalse

First, this checks cond for a pattern match against True. If there is a match, the whole expression will evaluate to ifTrue, otherwise it will evaluate to ifFalse (since a Bool can only be True or False there is no need for a default case). case is more general than if because the pattern matching in which case selection is based allows it to work with expressions which evaluate to values of any type. [1] In fact, the left hand side of any case branch is just a pattern, so it can also be used for binding:

describeString :: String -> String
describeString str = 
  case str of
    (x:xs) -> "The first character is: " ++ [x] ++ "; the rest of the string is: " ++ xs
    ""     -> "This is an empty string."

This expression tells you whether str is an empty string or something else. Of course, you could just do this with an if-statement (with a condition of str == []), but using a case binds variables to the head and tail of our list, which is convenient in this instance.

Equations and Case Expressions

Remember you can use multiple equations as an alternative to case expressions. The describeString function above could be written like this:

describeString :: String -> String
describeString (x:xs) = "The first character is " ++ [x] ++ "; the rest of the string is " ++ xs
describeString ""     = "This is the empty string."

Named functions and case expressions at the top level are completely interchangeable. In fact the function definition form shown here is just syntactic sugar for a case expression.

One handy thing about case expressions, and indeed about Haskell control structures in general, is that since they evaluate to values they can go inside other expressions just like an ordinary expression would. For example, this case expression evaluates to a string which is then concatenated with two other strings, all inside a single expression:

data Colour = Black | White | RGB Int Int Int

describeColour :: Colour -> String
describeColour c = 
  "This colour is "
  ++ case c of
       Black           -> "black"
       White           -> "white"
       RGB 0 0 0       -> "black"
       RGB 255 255 255 -> "white"
       _               -> "freaky, man, sort of in between"
  ++ ", yeah?"

Writing this function in an equivalent way using the multiple equations style would need a named function inside something like a let block.

Guards

As shown, if we have a top-level case expression, we can just give multiple equations for the function instead, which is often neater. Is there an analogue for if expressions? It turns out there is. We use some additional syntax known as "guards". A guard is a boolean condition, like this:

describeLetter :: Char -> String
describeLetter c
   | c >= 'a' && c <= 'z' = "Lower case"
   | c >= 'A' && c <= 'Z' = "Upper case"
   | otherwise            = "Not a letter"

Note the lack of an = before the first |. Guards are evaluated in the order they appear. That is, if you have a set up similar to the following:

f (pattern1) | predicate1 = w
             | predicate2 = x
f (pattern2) | predicate3 = y
             | predicate4 = z

Then the input to f will be pattern-matched against pattern1. If it succeeds, then predicate1 will be evaluated. If this is true, then w is returned. If not, then predicate2 is evaluated. If this is true, then x is returned. Again, if not, then we jump out of this 'branch' of f and try to pattern match against pattern2, repeating the guards procedure with predicate3 and predicate4. Unlike the else in if statements, otherwise is not mandatory. Still, if no guards match an error will be produced at runtime, so it's always a good idea to provide the 'otherwise' guard, even if it is just to handle the "But this can't happen!" case (which normally does happen anyway...).

The otherwise you saw above is actually just a normal value defined in the Standard Prelude as:

otherwise :: Bool
otherwise = True

This works because of the sequential evaluation described a couple of paragraphs back: if none of the guards previous to your 'otherwise' one are true, then your otherwise will definitely be true and so whatever is on the right-hand side gets returned. It's just nice for readability's sake.

Notes

  1. Again, this is quite different from what happens in most imperative languages, in which switch/case statements are restricted to equality tests, often only on integral primitive types.



可打印版本
Haskell基础

起步  >> 变量和函数  >> 列表和元组  >> 更进一步  >> 类型基础  >> 简单的输入输出  >> 类型声明


Haskell

Haskell基础 >> 初级Haskell >> Haskell进阶 >> Monads
高级Haskell >> 类型的乐趣 >> 理论提升 >> Haskell性能


库参考 >> 普通实务 >> 特殊任务

列表处理

Haskell/列表处理

深入函数

Haskell/深入函数

高阶函数

Haskell/高阶函数


Haskell进阶


模块

Haskell/模块

缩进

Haskell/缩进

更多数据类型

Haskell/更多数据类型

类的声明

Haskell/类的声明

类与类型

Haskell/类与类型


Monads


理解monads

Haskell/理解monads

高级monads

Haskell/高级monads

MonadPlus

我们已经学习过, Maybe 和列表都表示了一个计算能够拥有的结果数量. 换句话说, 我们使用 Maybe 来表示计算或许会失败的情况 (即0种或1种结果), 我们使用列表来表示计算能够返回0个或任意多个结果的情况.

或许有时我们会需要将两个这些类型的计算所表示的所有结果合并起来. 比如说, 我们能够将两个列表 (++) 起来以"合并"两个列表所表示的计算结果.

定义

MonadPlus 类型类定义了两个函数. mzero 是表示没有结果的值; mplus 则是一个将两个计算合并的二元函数.

class Monad m => MonadPlus m where
  mzero :: m a
  mplus :: m a -> m a -> m a

以下是 Maybe 和列表的 instance:

instance MonadPlus [] where
  mzero = []
  mplus = (++)
 
instance MonadPlus Maybe where
  mzero                   = Nothing
  Nothing `mplus` Nothing = Nothing -- 0 个结果 + 0 个结果 = 0 个结果
  Just x  `mplus` Nothing = Just x  -- 1 个结果  + 0 个结果 = 1 个结果
  Nothing `mplus` Just x  = Just x  -- 0 个结果 + 1 个结果  = 1 个结果
  Just x  `mplus` Just y  = Just x  -- 1 个结果  + 1 个结果  = 2 个结果,
                                    -- 但是 Maybe 最多只能表示1个结果,
                                    -- 因此我们丢弃掉第二个.

另外, 在 Control.Monad.Error 模块中, (Either e) 也定义了 MonadPlus 的 instance:

instance (Error e) => MonadPlus (Either e) where
  mzero            = Left noMsg
  Left _  `mplus` n = n
  Right x `mplus` _ = Right x

Maybe 一样, (Either e) 表示了可能会失败的计算. 但和 Maybe 不一样的是, (Either e) 允许这个失败的计算包含一条信息 (通常是一个字符串). 一般来说, Left s 表示一个信息为 s 的失败的计算, Right x 则表示结果为 x 的成功的计算.

例子: 并行解析

传统的输入解析一般会使用一次"消耗"一个字符的一系列函数. 换句话说, 一个解析函数接收一个输入字符串, 从头部削去 (也就是所谓的"消耗") 一个满足特定条件的字符. 比如说, 一个消耗一个大写字符的函数. 但是如果这个头部的字符不满足这个特定的条件, 本次解析就失败了; 因此在这样的函数中使用 Maybe 或许是个好主意.

我们将使用 mplus并行运行两个解析器. 换句话说, 如果第一个解析器成功我们就返回它的结果, 否则如果第二个成功我们就返回第二个的结果. 若两个都失败了, 我们返回, Nothing.

下例中, 我们消耗一个特定的数字字符并返回它所代表的数字.

digit :: Int -> String -> Maybe Int
digit i s | i > 9 || i < 0 = Nothing
          | otherwise      = do
  let (c:_) = s
  if [c] == show i then Just i else Nothing

我们的 guard 保证了我们所检查的 Int只有一位. 然后, 我们检查字符串的首位是否匹配我们所想要的数字. 如果匹配的话, 我们返回一个包裹在 Just 中的数字. do 代码块保证了失败的任何模式匹配都将返回 Nothing.

我们使用 digitmplus 函数来解析一个由二进制位组成的字符串:

binChar :: String -> Maybe Int
binChar s = digit 0 s `mplus` digit 1 s

解析器库一般都以类似的方式使用 MonadPlus. 好奇的话, 你可以看看 Text.ParserCombinators.ReadP 中 (+++) 函数的实现, 或者 Text.ParserCombinators.Parsec.Prim 中的 (<|>).

MonadPlus 法则

MonadPlus 的 instance 必须满足一些法则, 就如同 Monad 的 instance 需要满足三条 Monad 法则一样. 不幸的是, 人们对 MonadPlus 法则并没有达成一致的意见. 最通常的意见是, mzeromplus 需要形成一个幺半群 (monoid). 换句话说:

-- mzero 是一个无具体意义的"中立"值
mzero `mplus` m  =  m
m `mplus` mzero  =  m
-- mplus 满足结合律
-- (但并不是所有的 instance 都满足这条定律, 因为这和一些无尽的值构造相悖)
m `mplus` (n `mplus` o)  =  (m `mplus` n) `mplus` o

"形成一个幺半群" 并没有什么特别之处: 在上例中, "中立值" 和 "结合律" 可以比作整数加法的交换律和整数0. 事实上, 这也是为什么这两个函数叫做 mzero (m零) 和 mplus (m加).

Control.Monad 的 Haddock 文档 额外规定了以下法则:

mzero >>= f  =  mzero
m >> mzero   =  mzero

HaskellWiki 则给出了具有争议的另一条:

(m `mplus` n) >>= k  =  (m >>= k) `mplus` (n >>= k)

甚至还有更多的法则. 有时例如 IO 的 Monad 也会有 MonadPlus 的 instance. 参见 All About Monads 以及 Haskell Wiki.

实用函数

除了基础的 mplusmzero, 还有两个应用了 MonadPlus 的通用函数:

msum

处理 MonadPlus 的常见操作: 将一个列表中的 MonadPlus 值, 例如 [Maybe a][[a]], 用 mplus 进行 fold. msum 函数正是为此而生:

msum :: MonadPlus m => [m a] -> m a
msum = foldr mplus mzero

某种意义上, msum 是只能用在列表上的函数 concat 的推广. 事实上, 当应用在列表上时这两个函数完全相同. 对于 Maybe, msum 返回其中的第一个 Just x,若其不存在则返回 Nothing.

guard

我们注意到, 列表 monad 和列表解析之间的惊人相似, 但我们或许不是很清楚列表解析中的过滤是如何实现的. guard 就是实现的方式.

我们来看看这个计算所有勾股数 (也就是能形成直角三角形三边长的三个数) 的列表解析. 首先我们检查暴力的方法. 我们用一个布尔条件来过滤那些非勾股数的组合:

pythags = [ (x, y, z) | z <- [1..], x <- [1..z], y <- [x..z], x^2 + y^2 == z^2 ]

将如上的列表解析写成列表 monad 的形式:

pythags = do
  z <- [1..]
  x <- [1..z]
  y <- [x..z]
  guard (x^2 + y^2 == z^2)
  return (x, y, z)

guard 函数的定义:

guard :: MonadPlus m => Bool -> m ()
guard True  = return ()
guard _ = mzero

具体地, 当它获得一个 False 作为参数时, guard 会将整个 do 代码块的运算结果化为 mzero. 因为由于 MonadPlus 法则第一条, mzero 位于 (>>=) 左侧的运算将总是得回 mzero. do 代码块实际上是一系列用 (>>=) 串联起来的表达式的语法糖, 因此在任何位置出现的 mzero 都将使它的最终结果变为 mzero.

我们将扩展上面的 pythags 函数以展示 guard 在列表 monad 中的应用. 首先, 这是将 guard 特化到列表 monad 后的实现:

guard :: Bool -> [()]
guard True  = [()]
guard _ = []

简单地说, guard 堵住了 一条运算路径. 在 pythags 中, 我们希望能够堵住所有 x^2 + y^2 == z^2False 的路径 (或者说, x, yz 的组合). 让我们在展开 do 代码块后的代码:

pythags =
  [1..] >>= \z ->
  [1..z] >>= \x ->
  [x..z] >>= \y ->
  guard (x^2 + y^2 == z^2) >>= \_ ->
  return (x, y, z)

(>>=)return 替换成它们在列表 monad 中的特化 (并使用 let 绑定来增加可读性), 我们得到如下等价代码:

pythags =
 let ret x y z = [(x, y, z)]
     gd  z x y = concatMap (\_ -> ret x y z) (guard $ x^2 + y^2 == z^2)
     doY z x   = concatMap (gd  z x) [x..z]
     doX z     = concatMap (doY z  ) [1..z]
     doZ       = concatMap (doX    ) [1..]
 in doZ

我们注意到当它的参数为 False 时, guard 返回一个空列表. 而无论我们使用什么函数, 对一个空列表 map 总是返回一个空列表. 因此在 gd 的 let 绑定中对于 guard 的调用中返回的空列表将使 gd 返回一个空列表, 因此 ret 也是一个空列表.

为了更好地理解, 我们可以将列表 monad 中的计算想象成一棵树. 用我们的算法, 我们需要从顶部开始为每一个 x 的选取创建一个分支, 然后再在这些分支地下为所有 y 的选择创建分支, z 也是同样. 因此这棵"计算树"会长这样:

   start
   |____________________________________________ ...
   |                     |                    |
x  1                     2                    3
   |_______________ ...  |_______________ ... |_______________ ...
   |      |      |       |      |      |      |      |      |
y  1      2      3       2      3      4      3      4      5
   |___...|___...|___... |___...|___...|___...|___...|___...|___...
   | | |  | | |  | | |   | | |  | | |  | | |  | | |  | | |  | | |
z  1 2 3  2 3 4  3 4 5   2 3 4  3 4 5  4 5 6  3 4 5  4 5 6  5 6 7


每一个 x, y 和 z 的组合都代表了树中的一条路径. 当所有计算完成以后, 每一个分支被从下至上合并起来. 任何不满足条件的路径此时被转化成空列表, 因此对合并过程没有影响.

练习
  1. 证明 Maybe 和列表确实满足 MonadPlus 法则.
  2. 我们能够修改上面的解析器, 使其接收任意字符:
     -- | 消耗输入中的一个指定字符, 返回一个二元组,
          其中包含了这个字符以及余下的字符串. 我们用
          一个 do 代码块使得任意位置失败的模式匹配
          都将返回 Maybe 的"失败状态" (也就是 Nothing)
     char :: Char -> String -> Maybe (Char, String)
     char c s = do
       let (c':s') = s
       if c == c' then Just (c, s') else Nothing
    
    此时我们能够实现一个 hexChar 函数, 其接收任何合法的十六进制数字符 (0-9 或 a-f). 试着实现这个函数 (提示: map digit [0..9] :: [String -> Maybe Int]).

和 Monoid 的关系

当我们讨论 MonadPlus 法则时, 我们提到了数学上的幺半群 (Monoid). 事实上 Haskell 中存在着一个 Monoid 类型类, 详细教程请参见Haskell趣学指南中的章节:

class Monoid m where 
  mempty  :: m
  mappend :: m -> m -> m

列表是一个简单的 monoid:

instance Monoid [a] where
  mempty  = []
  mappend = (++)

看起来是不是很熟悉呢? 尽管和 MonadPlus 有些相似, 它们有一点关键而微妙的区别. 注意在 instance 声明中我们使用了 [a] 而不是 []. Monoid 并不一定是其他类型的"容器", 或者说不一定是多态的. 比如说, 整数加法构成了一个 Monoid, 其中"中立值" (mempty) 为0.

确实, MonadPlus 的 instance 看起来和 Monoid 类似, 因为两者都有"零"和"加"的概念. 事实上, 我们能够让 MonadPlus 成为 Monoid 的子类 (如果值得这番功夫的话):

 instance MonadPlus m => Monoid (m a) where
   mempty  = mzero
   mappend = mplus
注解

由于 instance 声明中自由变量 a 的存在, 上述代码在 Haskell 98 中并不合法. 除非你开启 GHC 的 语言扩展 FlexibleInstances:

  • 如果你使用的是 GHCi, 使用参数 -XFlexibleInstances 启动它或者在交互提示符下输入 :set -XFlexibleInstances.
  • 如果你编译后再运行程序的话, 在源文件第一行加上 {-# LANGUAGE FlexibleInstances #-}.

我们重申一下, MonoidMonadPlus 工作与不同的"层次". 正如之前所说, Monoid 并不一定是其他类型的"容器", 或者说不一定是多态的. 更加正式地, Monoid 的 kind 为 *, 但 MonadPlus 的 instance 的 kind 为 * -> *. (后者本身也是 Monad).

Template:Haskell/NotesSection



可打印版本
习题解答
Monads

理解 Monad  >> 高级 Monad  >> Monad 进阶  >> MonadPlus  >> Monadic parser combinators  >> Monad transformers  >> Monad 实务


Haskell

Haskell基础 >> 初级Haskell >> Haskell进阶 >> Monads
高级Haskell >> 类型的乐趣 >> 理论提升 >> Haskell性能


库参考 >> 普通实务 >> 特殊任务

Monad transformers

我们已经学习了Monad能够如何简便对于 IO, Maybe, 列表, 和 State 的处理. 每一个Monad都是如此的有用且用途广泛, 我们自然会寻求将几个Monad的特性组合起来的方法. 比如, 也许我们可以定义一个既能处理I/O操作, 又能使用 Maybe 提供的异常处理的函数. 虽然这可以用形如 IO (Maybe a) 的函数实现, 但是在这种方式下我们将被迫在 IO 的 do 代码块中手工模式匹配提取值, 而避免写出这种繁琐而无谓的代码却恰恰是 Maybe Monad存在的原因.

于是我们发明了 monad transformers: 它们能够将几种Monad的特性融合起来, 同时不失去使用Monad的灵活性.

密码验证

我们先来看一看这个几乎每一个IT从业人员都会遇到的实际问题: 让用户设置足够强的密码. 一种方案是: 强迫用户输入大于一定长度, 且满足各种恼人要求的密码 (例如包含大写字母, 数字, 字符, 等等).

这是一个用于从用户处获取密码的Haskell函数:

getPassphrase :: IO (Maybe String)
getPassphrase = do s <- getLine
                   if isValid s then return $ Just s
                                else return Nothing

-- 我们可以要求密码满足任何我们想要的条件
isValid :: String -> Bool
isValid s = length s >= 8
            && any isAlpha s
            && any isNumber s
            && any isPunctuation s

首先, getPassphrase 是一个 IO Monad, 因为它需要从用户处获得输入. 我们还使用了 Maybe, 因为若密码没有通过 isValid 的建议, 我们决定返回 Nothing. 需要注意的是, 我们在这里并没有使用到 Maybe 作为Monad的特性: do 代码块的类型是 IO monad, 我们只是恰巧 return 了一个 Maybe 类型的值罢了.

Monad transformers 不仅仅使 getPassphrase 的实现变简单了, 而且还能够简化几乎所有运用了多个monad的代码. 这是不使用Monad transformers的程序:

askPassphrase :: IO ()
askPassphrase = do putStrLn "输入新密码:"
                   maybe_value <- getPassphrase
                   if isJust maybe_value
                     then do putStrLn "储存中..." -- 假装存在数据库操作
                     else putStrLn "密码无效"

这段代码单独使用了一行来获得 maybe_value, 然后又手工对它进行验证.

如果使用 monad transformers, 我们将可以把获得输入和验证这两个步骤合二为一 — 我们将不再需要模式匹配或者等价的 isJust. 在我们的简单例子中, 或许 monad transformers 只作出了微小的改进, 但是当问题规模进一步扩大时, 它们将发挥巨大的作用.

一个简单的 monad transformer: MaybeT

为了简化 getPassphrase 以及所有使用到它的函数, 我们定义一个赋予 IO monad 一些 Maybe monad 特性的 monad transformer; 我们将其命名为 MaybeT. 一般来说, monad transformers 的名字都会以 "T" 结尾, 而之前的部分 (例如, 在本例中是"Maybe") 表示它所提供的特性.

MaybeT 是一个包装 (wrap) 了 m (Maybe a) 的类型, 其中 m 可以是任何Monad (在本例中即为 IO):

newtype MaybeT m a = MaybeT { runMaybeT :: m (Maybe a) }

这里的 datatype 声明定义了 MaybeT, 一个被 m 参数化的类型构造子 (type constructor), 以及一个值构造函数 (value constructor), 同样被命名为 MaybeT, 以及一个作用为简便的内部值访问的函数 runMaybeT.

Monad transformers 的关键在于 他们本身也是monads; 因此我们需要写出 MaybeT mMonad 类型类实例:

instance Monad m => Monad (MaybeT m) where
    return  = MaybeT . return . Just

首先, 我们先用 Just 将值装入最内层的 Maybe 中, 然后用 return 将前述 Maybe 装入 m monad里, 最后再用 MaybeT 将整个值包装起来.


我们也可以这样实现 (虽然是不是增加了可读性仍然有待商榷) return = MaybeT . return . return.

如同在所有monad中一样, (>>=) 也是 transformer 的核心.

-- 特化为 MaybeT m 的 (>>=) 函数类型签名 
(>>=) :: MaybeT m a -> (a -> MaybeT m b) -> MaybeT m b

x >>= f = MaybeT $ do maybe_value <- runMaybeT x
                      case maybe_value of
                           Nothing    -> return Nothing
                           Just value -> runMaybeT $ f value

我们从 do 代码块的第一行开始解释:

  • 首先, runMaybeTx 中取出 m (Maybe a). 我们由此可知整个 do 代码块的类型为 monad m.
  • 第一行稍后, <- 从上述值中取出了 Maybe a.
  • case 语句对 maybe_value 进行检测:
    • 若其为 Nothing, 我们将 Nothing 返回至 m 当中;
    • 若其为 Just, 我们将函数 f 应用到其中的 value 上. 因为 f 的返回值类型为 MaybeT m b, 我们需要再次使用 runMaybeT 来将其返回值提取回 m monad 中.
  • 最后, do 代码块的类型为 m (Maybe b); 因此我们用 MaybeT 值构造函数将它包装进 MaybeT 中.

这咋看来获取有些复杂; 但是若剔除大量的包装和解包装, 我们的代码和 Maybe monad 的实现其实很像:

-- Maybe monad 的 (>>=)
maybe_value >>= f = case maybe_value of
                        Nothing -> Nothing
                        Just value -> f value

我们在 do 代码块中仍然能够使用 runMaybeT, 为何要在前者上应用 MaybeT 值构造函数呢? 这是因为我们的 do 代码块必须是 m monad, 而不是 MaybeT m monad, 因为后者此时还没有定义 (>>=). (回想一下 do 语法糖是如何工作的)

注解

return 的实现中层层相叠的函数也许可以为我们提供一个(或许)有助于理解的比喻: 将复合的 monad 想象为一个 三明治; 虽然这个比喻似乎在暗示实际上有三个 monad 在起作用, 但是实际上只有两个: 内层的以及"融合了的" monad. 置于基层的 monad (本例中即Maybe) 中并没有用到 (>>=) 或者 return, 它只是作为 transformer 实现的一部分罢了. 如果你觉得这个比喻很有道理, 将 transformer 和 底层 monad 想象成三明治的两片包裹着内层 monad 的面包. [1]

理论上, 这就是我们所需的全部了; 但是, 为 MaybeT 实现几个其他类型类的 instance 又何妨呢?

instance Monad m => MonadPlus (MaybeT m) where
    mzero     = MaybeT $ return Nothing
    mplus x y = MaybeT $ do maybe_value <- runMaybeT x
                            case maybe_value of
                                 Nothing    -> runMaybeT y
                                 Just _     -> return maybe_value

instance MonadTrans MaybeT where
    lift = MaybeT . (liftM Just)

MonadTrans monad 实现了 lift 函数, 由此我们可以在 MaybeT m monad 的 do 代码块中使用m monad 的值. 至于 MonadPlus, 因为 Maybe 有着这个类型类的 instance, MaybeT 也应该有着对应的 instance.

应用在密码验证的例子中

现在, 前例的密码管理可以被改写为:

getValidPassphrase :: MaybeT IO String
getValidPassphrase = do s <- lift getLine
                        guard (isValid s) -- MonadPlus 类型类使我们能够使用 guard.
                        return s

askPassphrase :: MaybeT IO ()
askPassphrase = do lift $ putStrLn "输入新密码:"
                   value <- getValidPassphrase
                   lift $ putStrLn "储存中..."

这段代码简洁多了, 特别是 askPassphrase 函数. 最重要的是, 有着 (>>=) 为我们代劳, 我们不再需要手动检查结果是 NothingJust 中的哪一个了.

我们使用了 lift 函数以在 MaybeT IO monad 中使用 getLineputStrLn; 因为 MaybeT IO 有着 MonadPlus 类型类的 instance, guard 可以为我们检查代码的合法性. 在密码不合法时其将返回 mzero (即 IO Nothing).

碰巧, 有了 MonadPlus, 我们可以优雅地不停要求用户输入一个合法的密码:

askPassword :: MaybeT IO ()
askPassword = do lift $ putStrLn "输入新密码:"
                 value <- msum $ repeat getValidPassphrase
                 lift $ putStrLn "储存中..."

泛滥的 transformer

transformers 包提供了许多包含常见 monad 的 transformer 版本的模块 (例如 Template:Haskell lib 模块提供了 MaybeT). 它们和对应的非 transformer 版本 monad 是兼容的; 换句话说, 除去一些和另一个 monad 交互所用到的包装和解包装 , 它们的实现基本上是一致的. 从今往后, 我们称 transformer monad 所基于的非 transformer 版本的 monad 为 基层 monad (例如 MaybeT 中的 Maybe); 以及称应用在 transformer 上的 monad 为 内层 monad (例如 MaybeT IO 中的 IO).

我们随便举一个例子, ReaderT Env IO String. 这是一个能够从某个外部环境读取 Env 类型的值 (并且和 Reader, 也就是基 monad, 使用方法相同) 并且能够进行一些I/O, 最后返回一个 String 类型的值的 monad. 由于这个 transformer 的 (>>=)return 语义和基 monad 相同, 一个 ReaderT Env IO String 类型的 do 语句块从外部看来和另一个 Reader 类型的 do 语句块并无二致, 除了我们需要用 lift 来使用 IO monad.

类型戏法

我们已经了解到, MaybeT 的类型构造子实际上是一个对内层 monad 中的 Maybe 值的包装. 因此, 用于取出内部值的函数 runMaybeT 返回给我们一个类型为 m (Maybe a) 的值 - 也就是一个由内层 monad 包装着的基 monad 值. 类似的, 对于分别基于列表和 Either 构建的 ListTExceptT transformer:

runListT :: ListT m a -> m [a]

and

runExceptT :: ExceptT e m a -> m (Either e a)

然而并不是所有的 transformer 都和它们的基 monad 有着类似的关系. 不同于上面两例所给出的基 monad, Writer, Reader, State, 以及 Cont monad 既没有多个值构造子, 也没有接收多个参数的值构造函数. 因此, 它们提供了形如 run... 的函数以作为解包装函数, 而它们的 transformer 则提供形如 run...T 的函数. 下表给出了这些 monad 的 run...run...T 函数的类型, 而这些类型事实上就是包装在基 monad 和对应的 transformer 中的那些. [2]

基 Monad Transformer 原始类型
(被基 monad 包装的类型)
复合类型
(被 transformer 包装的类型)
Writer WriterT (a, w) m (a, w)
Reader ReaderT r -> a r -> m a
State StateT s -> (a, s) s -> m (a, s)
Cont ContT (a -> r) -> r (a -> m r) -> m r

我们可以注意到, 基 monad 并没有出现在复合的类型中. 这些 monad 并没有一个像 Maybe 或列表那样的有意义的构造函数, 因此我们选择不在 transformer monad 中保留基 monad. 值得注意的是, 在后三个例子中我们包装的值是函数. 拿 StateT 作例子, 将原有的表示状态转换的 s -> (a, s) 函数变为 s -> m (a, s) 的形式; 然而我们只将函数的返回值 (而不是整个函数) 包装进内层 monad 中. ReaderT 也与此差不多. ContT 却与它们不同: 由于 Cont (表示延续的 monad) 的性质, 被包装的函数和作这个函数参数的函数返回值必须相同, 因此 transformer 将两个值都包装入内层 monad 中. 遗憾的是, 并没有一种能将普通的 monad 转换成 transformer 版本的万灵药; 每一种 transformer 的实现都和基 monad 的行为有关.

Lifting

我们将仔细研究 lift 函数: 它是应用 monad transformers 的关键. 首先, 我们需要对它的名字 "lift" 做一些澄清. 在理解_Monad中, 我们已经学习过一个名字类似的函数 liftM. 我们了解到, 它实际上是 monad 版本的 fmap:

liftM :: Monad m => (a -> b) -> m a -> m b

liftM 将一个类型为 (a -> b) 的函数应用到一个 m monad 内的值上. 我们也可以将它视为只有一个参数:

liftM :: Monad m => (a -> b) -> (m a -> m b)

liftM 将一个普通的函数转换为在 m monad 上运作的函数. 我们用"提升(lifting)"表示将一样东西带至另一样东西中 — 在前例中, 我们将一个函数提升到了 m monad 中.

有了 liftM, 我们不需要用 do 代码块或类似的技巧就能够把寻常的函数应用在 monad 上了:

do notation liftM
do x <- monadicValue
   return (f x)
liftM f monadicValue

类似的, lift 函数在 transformer 上起到了一个相似的作用. 它将内层 monad 中的计算带至复合的 monad (即 transformer monad) 中. 这使得我们能够轻易地在复合 monad 中插入一个内层 monad 的运算.

liftMonadTrans 类型类的唯一一个函数, 参见 Template:Haskell lib. 所有的 transformer 都有 MonadTrans 的 instance, 因此我们能够在任何一个 transformer 上使用 lift.

class MonadTrans t where
    lift :: (Monad m) => m a -> t m a

lift 存在一个 IO 的变种, 名叫 liftIO; 这是 MonadIO 类型类的唯一一个函数, 参见 Template:Haskell lib.

class (Monad m) => MonadIO m where
   liftIO :: IO a -> m a

当多个 transformer 被组合在一起时, liftIO 能够带来一些便利. 在这种情况下, IO 永远是最内层的 monad (因为不存在 IOT transformer), 因此一般来说我们需要多次使用 lift 以将 IO 中的值从底层提升至复合 monad 中. 定义了 liftIO instance 的类型被设计成能够使用 liftIOIO 从任意深的内层一次性提升到 transformer monad 中.

实现 lift

lift 并不是很复杂. 以 MaybeT transformer 为例:

instance MonadTrans MaybeT where
    lift m = MaybeT (liftM Just m)

我们从接收到一个内层 monad 中的值的参数开始. 我们使用 liftM (或者 fmap, 因为所有Monad都首先是Functor) 和 Just 值构造函数来将基 monad 插入内层 monad 中, 以从 m a 转化为 m (Maybe a)). 最后, 我们使用 MaybeT 值构造函数将三明治包裹起来. 值得注意的是, 此例中 liftM 工作于内层 monad 中, 如同我们之前看到的 MaybeT(>>=) 实现中的 do 代码块一样.

练习
  1. 为什么 lift 必须为每一个 monad transformer 单独定义, 但 liftM 却可以只实现一次呢?
  2. Identity 是一个定义于 Data.Functor.Identity 中实际意义不大的 functor:
    newtype Identity a = Identity { runIdentity :: a }
    它有着如下的 Monad instance:
    instance Monad Identity where
        return a = Identity a
        m >>= k  = k (runIdentity m)
    
    实现一个 monad transformer IdentityT, 这个 transformer 和 Identity 类似, 但是将值包裹在 m a 而不是 a 类型的值中. 请你至少写出它的 MonadMonadTrans instances.

实现 transformers

State transformer

作为一个额外的例子, 我们将试着实现 StateT. 请确认自己了解 State 再继续. [3]

正如同 State monad 有着 newtype State s a = State { runState :: (s -> (a,s)) } 的定义一样, StateT transformer 的定义为:

newtype StateT s m a = StateT { runStateT :: (s -> m (a,s)) }

StateT s m 有着如下的 Monad instance, 旁边用基 monad 作为对比:

State StateT
newtype State s a =
  State { runState :: (s -> (a,s)) }

instance Monad (State s) where
  return a        = State $ \s -> (a,s)
  (State x) >>= f = State $ \s ->
    let (v,s') = x s
    in runState (f v) s'
newtype StateT s m a =
  StateT { runStateT :: (s -> m (a,s)) }

instance (Monad m) => Monad (StateT s m) where
  return a         = StateT $ \s -> return (a,s)
  (StateT x) >>= f = StateT $ \s -> do
    (v,s') <- x s          -- 取得新的值和状态
    runStateT (f v) s'     -- 将它们传递给 f

我们的 return 实现使用了内层 monad 的 return 函数. (>>=) 则使用一个 do 代码块来在内层 monad 中进行计算.

注解

现在我们能够解释, 为什么在 State monad 中存在手工定义的 state 却没有与类型一同定义的 State 值构造函数了. 在 transformersmtl 包中, State s 被定义为 StateT s Identity 的类型别名, 其中 Identity 是在本章练习中出现的没有特别效果的 monad. 这个定义和我们迄今为止所见的使用 newtype 的定义是等价的.

为了将 StateT s m monad 同 State monad 一般使用, 我们自然需要核心的 getput 函数. 这里我们将使用 mtl 的代码风格. mtl 不仅仅提供了 monad transformers 的定义, 还提供了定义了常见 monad 的关键操作的类型类. 例如, Template:Haskell lib 包所提供的 MonadState 类型类, 定义了 getput 函数:

instance (Monad m) => MonadState s (StateT s m) where
  get   = StateT $ \s -> return (s,s)
  put s = StateT $ \_ -> return ((),s)
注解

instance (Monad m) => MonadState s (StateT s m) 的意思是: "对于任何类型 s 以及任何是 Monad instance 的类型 m, sStateT s m 共同组成了一个 MonadState 的 instance". sm 分别对应了 state monad 和内层 monad. 类型参数 s 是 instance 声明的一个独立部分, 因此函数能够访问到 s: 举个例子, put 的类型为 s -> StateT s m ().

存在为其他 transformer 包装着的 state monad 所定义的 MonadState instance, 例如 MonadState s m => MonadState s (MaybeT m). 这些 instance 使得我们不再需要写出 lift 来使用 get and put, 因为复合 monad 的 MonadState instance 为我们代劳了.

我们还可以为复合 monad 实现内层 monad 所拥有的一些类型类 instance. 例如, 所有包装了 StateT (其拥有 MonadPlus instance) 的复合 monad 也同样能够拥有 MonadPlus 的 instance:

instance (MonadPlus m) => MonadPlus (StateT s m) where
  mzero = StateT $ \_ -> mzero
  (StateT x1) `mplus` (StateT x2) = StateT $ \s -> (x1 s) `mplus` (x2 s)

mzeromplus 的实现符合我们的直觉; 它们将实际的操作下推给内层 monad 来完成.

最后, monad transformer 必须有 MonadTrans 的 instance, 不然我们无法使用 lift:

instance MonadTrans (StateT s) where
  lift c = StateT $ \s -> c >>= (\x -> return (x,s))

lift 函数返回一个包装在 StateT 中的函数, 其接受一个表示状态的值 s 作为参数, 返回一个函数, 这个函数接受一个内层 monad 中的值, 并将它通过 (>>=) 传递给一个将其和状态打包成一个在内层 monad 中的二元组的函数. 举个例子, 当我们在 StateT transformer 中使用列表时, 一个返回列表的函数 (即一个在列表 monad 中的计算) 在被提升为 StateT s []后, 将变成一个返回 StateT (s -> [(a,s)]) 的函数. 换句话说, 这个函数用初始状态产生了多个 (值, 新状态) 的二元组. 我们将 StateT 中的计算 "fork" 了, 为被提升的函数返回的列表中的每一个值创建了一个计算分支. 当然了, 将 StateT 和不同的 monad 组合将产生不同效果的 lift 函数.

练习
  1. 使用 getput 来实现 state :: MonadState s m => (s -> (a, s)) -> m a.
  2. MaybeT (State s)StateT s Maybe 等价吗? (提示: 比较两个 run...T 函数的返回值.

致谢

本章摘取了 All About Monads, 已取得作者 Jeff Newbern 的授权.

Template:Haskell/NotesSection



可打印版本
习题解答
Monads

理解 Monad  >> 高级 Monad  >> Monad 进阶  >> MonadPlus  >> Monadic parser combinators  >> Monad transformers  >> Monad 实务


Haskell

Haskell基础 >> 初级Haskell >> Haskell进阶 >> Monads
高级Haskell >> 类型的乐趣 >> 理论提升 >> Haskell性能


库参考 >> 普通实务 >> 特殊任务

monads实务

Haskell/monads实务


高级Haskell


Arrows

Haskell/Arrows

Understanding arrows

Haskell/Understanding arrows

Continuation passing style

Haskell/Continuation passing style

Mutable objects

Haskell/Mutable objects

Zippers

Haskell/Zippers


类型的乐趣


Existentially quantified types

Haskell/Existentially quantified types

Polymorphism

Haskell/Polymorphism

Advanced type classes

Haskell/Advanced type classes

Phantom types

Haskell/Phantom types

GADT

Haskell/GADT


理论提升


Denotational semantics

Haskell/Denotational semantics

Equational reasoning

Haskell/Equational reasoning

Program derivation

Haskell/Program derivation

Category theory

Haskell/Category theory


Haskell性能


Graph reduction

Haskell/Graph reduction

Laziness

Haskell/Laziness

Strictness

Haskell/Strictness

Algorithm complexity

Haskell/Algorithm complexity

Concurrency

Haskell/Concurrency

Choosing data structures

Haskell/Choosing data structures


程序库参考


Hierarchical libraries

Haskell/Hierarchical libraries

Hierarchical libraries/Lists

Haskell/Hierarchical libraries/Lists

Hierarchical libraries/Randoms

Haskell/Hierarchical libraries/Randoms


普通实务


Applications

Haskell/Applications

Debugging/

Haskell/Debugging/

Testing

Haskell/Testing

Packaging

Haskell/Packaging


专门任务


GUI

Haskell/GUI

Database

Haskell/Database

Web programming

Haskell/Web programming

XML

Haskell/XML

  1. 译者并没有看懂这个比喻, 请批判性地阅读. 看得懂的人希望能够帮忙确认或修改.
  2. 严格意义上, 这个解释只在大于 2.0.0.0 版本的 mtl 包中成立.
  3. 译注: 此处作者引用了 理解_Monad 中的内容, 然而译时此章节并没有翻译完成.