Monoid类型类
Applicative类型类

Foldable类型类
Traversable类型类

Lens 和引用

## 理论提升

Equational reasoning
Program derivation
Category theory
The Curry-Howard isomorphism
fix 和递归

Introduction
Step by Step Examples
Graph reduction
Laziness
Strictness
Algorithm complexity
Data structures
Parallelism

## 程序库参考

The Hierarchical Libraries
Lists:Arrays:Maybe:Maps
IO:Random Numbers

# 起步

 注解 給 UNIX 用戶： 如果你是想编译源码的人：这对于 GHC 来说是一个坏主意, 特别是如果你是第一次安装。GHC 本身几乎全部使用 Haskell 编写，所以试着手工从源码引导它的编译是非常麻烦的。除此之外，编译会消耗大量时间并且消耗大量磁盘空间。如果你坚持从源码编译 GHC，参见GHC主页上的“编译和移植GHC”. 簡而言之，我們強烈建議安裝 Haskell platform 而非從源碼編譯。

## 第一步

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

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


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


Prelude> :quit
Leaving GHCi.


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

 可打印版本 Haskell基础 起步  >> 变量和函数  >> 列表和元组  >> 更进一步  >> 类型基础  >> 简单的输入输出  >> 类型声明 编辑此章节 Haskell 库参考 >> 普通实务 >> 特殊任务 编辑书目结构

# 变量和函数

## 变量

ghci> 3.1416 * 5^2
78.53999999999999


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

Prelude>


Prelude> 3.14 * 5^2
78.5


Prelude> 3.14159265358979323846264338327950 * (5 ^ 2)
78.53981633974483


Prelude> 2 * 3.14159265358979323846264338327950 * 5
31.41592653589793


Prelude> 3.14159265358979323846264338327950 * (25 ^ 2)
1963.4954084936207


Prelude> let pi = 3.14159265358979323846264338327950

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

Prelude> pi
3.141592653589793


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


## 类型

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


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


 注解 事实上在这个难题背后有一点点微妙。它涉及一个叫作单一同态限定（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）来禁用它，但是这带来了一些低效率的风险。除此之外，多数情况下它就像明确指定类型一样容易。

## 变量中的变量

Prelude> let area = pi * 5^2


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


Prelude> let r = 2.0
Prelude> area2
1963.4954084936207


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


## 函数

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


Prelude> area 5
78.53981633974483
Prelude> area 25
1963.4954084936207


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


### 多重参数

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


## 函数中的函数

Prelude> let areaRect l w = l * w
Prelude> let areaSquare s = areaRect s s
Prelude> areaSquare 5
25


## 总结

2. 变量不可以改变。
3. 函数可以帮助你编写可重复利用的代码。
4. 函数可以接受一个以上的参数。

## 注释

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

 可打印版本 习题解答 Haskell基础 起步  >> 变量和函数  >> 列表和元组  >> 更进一步  >> 类型基础  >> 简单的输入输出  >> 类型声明 编辑此章节 Haskell 库参考 >> 普通实务 >> 特殊任务 编辑书目结构

# 列表和元组

## 列表

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

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

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


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"]


### 创建列表

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


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]


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


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）数据到一个列表上

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 = 

### 列表组成的列表

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


1. [1,2,3,[]]
2. [1,[2,3],4]
3. [[1,2,3],[]]
1. []:[[1,2,3],[4,5,6]]
2. []:[]
3. []:[]:[]
4. [1]:[]:[]
4. 下面的列表为什么不正确？如果你还不能回答不要太烦恼。
1. [[1,2],3,[4,5]]

## 元组

### 另一种多值记法

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


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

### 从元组中取出数据

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


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

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


### 元组组成的元组（以及其它组合）

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


• 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. 列表和元组可以任意方式嵌套：列表组成的列表，元组组成的列表，等等

## 提示

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

 可打印版本 习题解答 Haskell基础 起步  >> 变量和函数  >> 列表和元组  >> 更进一步  >> 类型基础  >> 简单的输入输出  >> 类型声明 编辑此章节 Haskell 库参考 >> 普通实务 >> 特殊任务 编辑书目结构

# 更进一步

area r = pi * r^2


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

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


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


*Main> area 5
78.53981633974483


### 没有let

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


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


### 不能定义同一个量两次

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 

## 关于函数的更多特性

### 条件表达式

#### if / then / else

Haskell支持标准的条件表达式。我们可以定义一个参数小于${\displaystyle 0}$时返回${\displaystyle -1}$、参数等于${\displaystyle 0}$时返回${\displaystyle 0}$、参数大于${\displaystyle 0}$时返回${\displaystyle 1}$的函数。事实上，这个函数已经存在（被称为符号（signum）函数），但是让我们定义一个我们自己的，把它叫做mySignum

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


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


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

#### case

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

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 x =
case x of { 0 -> 1 ;
1 -> 5 ; 2 -> 2
; _ -> -1 }


### 为不同参数定义一个函数

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


### 函数合成

square x = x^2


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


 注解 在数学里我们用表达式 ${\displaystyle f\circ g}$ 表达 "f following g." 在Haskell , 代码f . g 也表达为 "f following g." 其中${\displaystyle f\circ g}$ 等同于 ${\displaystyle (f\circ g)(x)=f(g(x))}$。

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

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


### let绑定

${\displaystyle x={\frac {-b\pm {\sqrt {b^{2}-4ac}}}{2a}}}$

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


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


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 库参考 >> 普通实务 >> 特殊任务 编辑书目结构

# 类型基础

## 介绍

2 + 3

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

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

## 使用交互式的:type命令

### 字符和字符串

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


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


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

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

"Hello World" :: String


### 布尔值

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


### 数值类型

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


## 函数类型

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.

### 例子：not

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)是否"不"存在于电子数据表中。如下：

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 :: Bool -> Bool



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

### 例子：unlines和unwords

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)

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.

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).

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.

### 例子：chr和ord

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


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?

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.

There are very deep reasons for this, which we'll cover in the chapter on 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:

-->

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]:

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...

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:

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.

### 例子：fst和snd

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:

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:

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:

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:

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.

-- 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:

(==)  :: 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:

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.

### 类型防止错误发生

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:

"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:

"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.
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 库参考 >> 普通实务 >> 特殊任务 编辑书目结构

# 简单的输入输出

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


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

## 动作(Actions)

putStrLn :: String -> IO ()


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

getLine :: IO String


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

 注解 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:

main = do
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:

main = do
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):

main = do
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:

main = do
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.

### 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
guess <- getLine
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
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) {
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
guess <- getLine
case compare (read guess) num of
EQ -> do putStrLn "You win!"
return ()

-- we don't expect to get here if 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.

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

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?

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, <-.

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:

import Data.Char (toUpper)

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

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:

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?

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 has three basic ways to declare a new type:

• 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 来创建你自己的类型

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.

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:

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


He married Jane Smith on 4th March 1987:

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 库参考 >> 普通实务 >> 特殊任务 编辑书目结构

# 递归

## 数值递归

### 阶乘函数

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


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


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

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


• 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)

• factorial 5是几?
• factorial 1000呢?如果你有个计算器，先用它算一算，然后看看和电脑中的一样吗？
• 要是 factorial (-1)会如何？为何如此？
2. 双阶乘意为：从1（或2）隔一个数字乘一个，一直乘到n。比如，8的双阶乘是 8 × 6 × 4 × 2 = 384, 7的双阶乘是 7 × 5 × 3 × 1 = 105. 定义一个双阶乘函数doublefactorial.

### 一次小小的跑题

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


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


### 其他递归函数

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


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 函数。

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


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')]

## 不要太爱递归

factorial n = product [1..n]


## 注释

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

# 控制结构

## if 表达式

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


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 库参考 >> 普通实务 >> 特殊任务 编辑书目结构

# 类与类型

## 定义

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

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


instance MonadPlus [] where
mzero = []
mplus = (++)

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个结果,
-- 因此我们丢弃掉第二个.


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 的成功的计算.

## 例子: 并行解析

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


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


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加).

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


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


## 实用函数

### msum

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


### guard

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


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


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


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).  可打印版本 习题解答 Monads 编辑此章节 Haskell 库参考 >> 普通实务 >> 特殊任务 编辑书目结构 # Monad transformers  可打印版本 (解答) Monads 编辑此章节 我们已经学习了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


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

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


## 一个简单的 monad transformer: MaybeT

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

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


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

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


-- 特化为 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


• 首先, 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_value >>= f = case maybe_value of
Nothing -> Nothing
Just value -> f value


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

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

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 = do lift $putStrLn "输入新密码:" value <- getValidPassphrase lift$ putStrLn "储存中..."


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 值构造函数了. 在 transformers 和 mtl 包中, 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, s 和 StateT s m 共同组成了一个 MonadState 的 instance". s 和 m 分别对应了 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` 函数的返回值.

# XML

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