另一个 Haskell 教程/语言基础

Haskell

另一个 Haskell 教程
前言
介绍
入门
语言基础 (解答)
类型基础 (解答)
IO (解答)
模块 (解答)
高级语言 (解答)
高级类型 (解答)
单子 (解答)
高级 IO
递归
复杂度
此框：查看 • 讨论 • 编辑

在本章中，我们将介绍 Haskell 的基本概念。除了使您熟悉交互式环境并向您展示如何编译基本程序之外，我们还介绍了 Haskell 的基本语法，如果您习惯使用 C 和 Java 等语言，这可能非常陌生。

但是，在讨论语言的具体细节之前，我们需要确定 Haskell 的一些通用特性。最重要的是，Haskell 是一种**惰性**语言，这意味着除非在使用计算结果时被迫进行计算，否则不会进行任何计算。

例如，这意味着您可以定义无限大的数据结构，只要您永远不使用整个结构即可。例如，使用类似命令式的伪代码，我们可以创建一个无限链接列表，每个位置都包含数字 $1$ ，方法如下

List makeList()
{
  List current = new List();
  current.value = 1;
  current.next = makeList();
  return current;
}

通过查看此代码，我们可以了解它试图做什么：它创建一个新列表，将其值设置为 $1$ ，然后递归调用自身以创建列表的其余部分。当然，如果您实际编写了此代码并调用它，程序将永远不会终止，因为makeList将无限地调用自身。

这是因为我们假设这种类似命令式的语言是严格的，与惰性相反。严格语言通常被称为“按值调用”，而惰性语言则被称为“按名调用”。在上面的伪代码中，当我们“运行”makeList在第五行，我们尝试从中获取一个值。这会导致无限循环。

Haskell 中的等效代码是

makeList = 1 : makeList

此程序表示：我们正在定义一个名为makeList的东西（这是等号左侧的内容）。在右侧，我们给出了makeList的定义。在 Haskell 中，冒号运算符用于创建列表（我们很快就会详细讨论）。此右侧表示makeList的值是元素1附加到makeList的值的开头。

但是，由于 Haskell 是惰性的（或“按名调用”），因此我们实际上不会尝试在此时评估makeList是什么：我们只是记住，如果将来我们确实需要makeList的第二个元素，我们只需要查看makeList即可。

现在，如果您尝试将makeList写入文件、将其打印到屏幕或计算其元素的总和，则操作将不会终止，因为它必须评估无限长的列表。但是，如果您只使用列表的有限部分（例如前 $10$ 个元素），则列表无限长的这一事实无关紧要。如果您只使用前 $10$ 个元素，则只会计算前 $10$ 个元素。这就是惰性。

其次，Haskell 区分大小写。许多语言都区分大小写，但 Haskell 实际上使用大小写来赋予含义。Haskell 区分值（例如，数字： $1,2,3,...$ ）；字符串：“abc”，“hello”，...；字符：'a'，'b'，' '，...；甚至函数（例如，对值求平方或开平方根的函数）；以及类型（值所属的类别）。

就其本身而言，这并不罕见。大多数语言都有一些类型系统。不寻常的是 Haskell要求赋予函数和值的名称以小写字母开头，而赋予类型的名称则以大写字母开头。寓意是：如果您的程序在其他方面正确但无法编译，请确保您没有将函数命名为Foo或其他以大写字母开头的名称。

作为一种函数式语言，Haskell 避免了副作用。副作用本质上是在执行函数的过程中发生的与该函数产生的输出无关的事情。

例如，在 C 或 Java 等语言中，您可以从函数内部修改“全局”变量。这是一种副作用，因为全局变量的修改与函数产生的输出无关。此外，修改现实世界中的状态被认为是一种副作用：将内容打印到屏幕、读取文件等都是产生副作用的操作。

没有副作用的函数称为纯函数。判断函数是否为纯函数的一个简单测试是问自己一个简单的问题：“此函数的结果是否仅取决于它接收的参数，并且返回结果是它唯一执行的操作？”

所有这一切都意味着，如果您习惯于使用命令式语言（如 C 或 Java）编写代码，那么您将不得不开始以不同的方式思考。最重要的是，如果您有一个值x，您一定不要将x视为寄存器、内存位置或任何其他类似的东西。x只是一个名称，就像“Hal”是我的名字一样。您不能随意决定将不同的人存储在我的名字中，就像您不能随意决定将不同的值存储在x中一样。这意味着以下 C 代码可能看起来像的代码在 Haskell 中是无效的（并且没有对应项）

   int x = 5;
   x = x + 1;

类似这样的调用x = x + 1被称为破坏性更新，因为我们正在销毁之前存储在x中的任何内容，并用新值替换它。Haskell 中不存在破坏性更新。

通过不允许破坏性更新（或任何其他此类具有副作用的操作），Haskell 代码非常易于理解。也就是说，当我们定义一个函数f，并在程序开始时用一个特定的参数a调用该函数，然后在程序结束时，再次用相同的参数a调用f时，我们知道我们将得到相同的结果。这是因为我们知道a不可能发生改变，并且因为我们知道f只依赖于a（例如，它没有递增全局计数器）。此属性称为引用透明性，基本上表示如果两个函数f和g对相同参数产生相同的值，则我们可以用g替换f（反之亦然）。

注意

没有关于引用透明性的统一精确定义。上面给出的定义是我最喜欢的。它们都具有相同的含义；差异在于它们的形式化方式。

算术

让我们从简单的算术开始探索 Haskell。启动您最喜欢的交互式 Shell（Hugs 或 GHCi；有关安装说明，请参阅章节入门）。Shell 将输出几行关于自身及其正在执行的操作的信息，然后应该以光标位于读取以下内容的行上结束

示例

Prelude>

从这里，您可以开始评估表达式。表达式基本上是具有值的事物。例如，数字 $5$ 是一个表达式（其值为 $5$ ）。值可以从其他值构建；例如， $5+6$ 是一个表达式（其值为 $11$ ）。实际上，Haskell 支持大多数简单的算术运算，包括加法 (+)、减法 (-)、乘法 (*)、除法 (/)、幂运算 (^) 和平方根 (sqrt)。您可以通过要求交互式 Shell 评估表达式并为您提供其值来进行实验。这样，Haskell Shell 可以用作功能强大的计算器。尝试以下一些操作

示例

Prelude> 5*4+3
23
Prelude> 5^5-2
3123
Prelude> sqrt 2
1.4142135623730951
Prelude> 5*(4+3)
35

我们可以看到，除了标准的算术运算外，Haskell 还允许通过括号进行分组，因此5*4+3和5*(4+3)的值之间存在差异。这是因为第一个表达式的“隐含”分组是(5*4)+3，这是由于运算符优先级。

另请注意，函数参数周围不需要括号。例如，我们只是写了sqrt 2，而不是像大多数其他语言那样写sqrt(2)。您可以用括号来写，但在 Haskell 中，由于函数应用非常常见，因此不需要括号。

现在尝试输入2^5000。它有效吗？

注意

如果您熟悉其他语言的编程，您可能会发现sqrt 2会返回一个带小数点的数字（即浮点数），即使函数的参数似乎是整数。这种数字类型的可互换性是由于 Haskell 的类型类系统造成的，我们将在关于类的部分中详细讨论。

练习
我们已经看到乘法比加法具有更高的绑定优先级。你能想到一种方法来确定函数应用的绑定优先级是高于还是低于乘法吗？

对、三元组及更多

除了单个值之外，我们还应该处理多个值。例如，我们可能希望通过其 $x$ / $y$ 坐标来引用位置，这将是一对整数。创建一对整数很简单：您将它们括在括号中并用逗号分隔。尝试以下操作

示例

Prelude> (5,3)
(5,3)

这里，我们有一对整数， $5$ 和 $3$ 。在 Haskell 中，对的第一元素不必与第二元素具有相同的类型：也就是说，对允许是异构的。例如，您可以将一个整数与一个字符串配对。这与列表形成对比，列表必须由所有相同类型的元素组成（我们将在关于列表的部分中进一步讨论列表）。

有两个预定义函数允许您提取对的第一和第二元素。它们分别是fst和snd。您可以查看它们的工作方式如下

示例

Prelude> fst (5, "hello")
5
Prelude> snd (5, "hello")
"hello"

除了对之外，您还可以定义三元组、四元组等。要分别定义三元组和四元组，我们写

示例

Prelude> (1,2,3)
(1,2,3)
Prelude> (1,2,3,4)
(1,2,3,4)

等等。一般来说，对、三元组等等被称为元组，可以存储固定数量的异构数据。

注意

函数fst和snd不能用于长度超过一对的任何事物；如果您尝试将它们用于更大的元组，您将收到一条消息，指出存在类型错误。此错误消息的含义将在章节类型基础中解释。

练习
结合使用`fst`和`snd`来提取字符`'a'` 从元组`((1,'a'),"foo")`中。

列表

元组的主要限制是它们仅保存固定数量的元素：对保存两个，三元组保存三个，依此类推。可以保存任意数量元素的数据结构是列表。列表的组装方式与元组非常相似，只是它们使用方括号而不是圆括号。我们可以定义一个列表，例如

示例

Prelude> [1,2]
[1,2]
Prelude> [1,2,3]
[1,2,3]

列表不需要有任何元素。空列表只是[]。

与元组不同，我们可以使用冒号运算符非常轻松地将元素添加到列表的开头。冒号称为“cons”运算符；添加元素的过程称为“consing”。其词源在于我们正在从一个元素和一个旧列表中construct（构建）一个新列表。我们可以在以下示例中看到 cons 运算符的实际应用

示例

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

我们实际上可以使用 cons 运算符（冒号）和空列表来构建任何列表

示例

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

实际上，[5,1,2,3,4] 语法是使用显式 cons 运算符和空列表的表达式的“语法糖”。如果我们使用[5,1,2,3,4]表示法编写内容，编译器会将其简单地转换为使用(:)和[]的表达式。

注意

一般来说，“语法糖”是一个严格来说不必要的语言特性，它被添加到使语法更漂亮。

列表和元组之间的另一个区别是，虽然元组是异构的，但列表必须是同构的。这意味着您不能拥有一个同时包含整数和字符串的列表。如果您尝试这样做，将报告类型错误。

当然，列表不必只包含整数或字符串；它们还可以包含元组甚至其他列表。类似地，元组可以包含列表和其他元组。尝试以下一些操作

示例

Prelude> [(1,1),(2,4),(3,9),(4,16)]
[(1,1),(2,4),(3,9),(4,16)]
Prelude> ([1,2,3,4],[5,6,7])
([1,2,3,4],[5,6,7])

有两个基本的列表函数：head和tail。head函数返回（非空）列表的第一个元素，tail函数返回（非空）列表除第一个元素之外的所有元素。

要获取列表的长度，您可以使用length函数

示例

Prelude> length [1,2,3,4,10]
5
Prelude> head [1,2,3,4,10]
1
Prelude> length (tail [1,2,3,4,10])
4

字符串

在 Haskell 中，一个 String 仅仅是一个 Char 列表。因此，我们可以创建字符串 "Hello" 如下：

示例

Prelude> 'H':'e':'l':'l':'o':[]
"Hello"

列表（当然，还有字符串）可以使用 ++ 运算符进行连接

示例

Prelude> "Hello " ++ "World"
"Hello World"

此外，非字符串值可以使用 show 函数转换为字符串，字符串可以使用 read 函数转换为非字符串值。当然，如果你尝试读取格式错误的值，将会报告错误（注意，这是一个运行时错误，而不是编译时错误）

示例

Prelude> "Five squared is " ++ show (5*5)
"Five squared is 25"
Prelude> read "5" + 3
8
Prelude> read "Hello" + 3
Program error: Prelude.read: no parse

在上面，确切的错误消息取决于实现。但是，解释器推断出你试图将 3 加到某个东西上。这意味着当我们执行 read "Hello" 时，我们期望返回一个数字。然而，"Hello" 无法解析为数字，因此报告了错误。

简单的列表函数

Haskell 程序中的大部分计算都是通过处理列表来完成的。有三个主要的列表处理函数：map、filter 和 foldr（还有 foldl）。

map 函数接受一个值列表和一个应该应用于每个值的函数作为参数。它返回此应用的结果。例如，有一个内置函数 Data.Char.toUpper，它以一个 Char 作为输入，并产生一个 Char，它是原始参数的大写版本。因此，要将整个字符串（它只是一个字符列表）转换为大写，我们可以将 toUpper 函数映射到整个列表上

示例

Prelude> map Data.Char.toUpper "Hello World"
"HELLO WORLD"

当你映射到一个列表时，列表的长度永远不会改变——只有列表中的各个值会改变。

要从列表中删除元素，可以使用 filter 函数。此函数允许你根据元素的值（而不是其上下文）从列表中删除某些元素。例如，函数 Data.Char.isLower 会告诉你给定字符是否是小写。我们可以使用它过滤掉所有非小写字符

示例

Prelude> filter Data.Char.isLower "Hello World"
"elloorld"

foldr 函数需要稍微多一些时间来理解。foldr 接受三个参数：一个函数、一个初始值和一个列表。理解 foldr 的最佳方式是，它用函数参数替换列表构造运算符 (:) 的出现，并用初始值替换空列表构造函数 ([])。因此，如果我们有一个列表

  3 : 8 : 12 : 5 : []

并且我们对其应用 foldr (+) 0，我们得到

  3 + 8 + 12 + 5 + 0

它对列表求和。我们可以测试一下

示例

Prelude> foldr (+) 0 [3,8,12,5]
28

我们可以执行相同类型的操作来计算列表中所有元素的乘积

示例

Prelude> foldr (*) 1 [4,8,5]
160

我们之前说过，折叠就像用特定函数替换 (:) 并用初始元素替换 ([])。这就引发了一个问题，即当函数不是结合律时会发生什么（函数 ( $\cdot$ ) 是结合律，如果 $a\cdot (b\cdot c)=(a\cdot b)\cdot c$ )。当我们写 $4\cdot 8\cdot 5\cdot 1$ 时，我们需要指定在哪里放置括号。也就是说，我们的意思是 $((4\cdot 8)\cdot 5)\cdot 1$ 还是 $4\cdot (8\cdot (5\cdot 1))$ ？foldr 假设函数是右结合的（即，正确的括号是后者）。因此，当我们将其用于非结合函数（如减法）时，我们可以看到效果

示例

Prelude> foldr (-) 1 [4,8,5]
0

这个的精确推导看起来像这样

     foldr (-) 1 [4,8,5]
==>  4 - (foldr (-) 1 [8,5])
==>  4 - (8 - foldr (-) 1 [5])
==>  4 - (8 - (5 - foldr (-) 1 []))
==>  4 - (8 - (5 - 1))
==>  4 - (8 - 4)
==>  4 - 4
==>  0

foldl 函数朝另一个方向前进，并有效地产生相反的括号。foldl 在应用时看起来相同，因此我们也可以使用 foldl 进行求和

示例

Prelude> foldl (+) 0 [3,8,12,5]
28

但是，当使用非结合函数减法时，我们得到不同的结果

示例

Prelude> foldl (-) 1 [4,8,5]
-16

这是因为 foldl 使用相反的括号。它实现这一点的方式本质上是遍历整个列表，取最后一个元素并通过提供的函数将其与初始值组合。然后它取列表中的倒数第二个元素并将其与这个新值组合。它这样做，直到列表中没有更多元素。

此处的推导以相反的方式进行

     foldl (-) 1 [4,8,5]
==>  foldl (-) (1 - 4) [8,5]
==>  foldl (-) ((1 - 4) - 8) [5]
==>  foldl (-) (((1 - 4) - 8) - 5) []
==>  ((1 - 4) - 8) - 5
==>  ((-3) - 8) - 5
==>  (-11) - 5
==>  -16

请注意，一旦 foldl 消失，括号与 foldr 完全相反。

注意

由于我们将在关于列表的章节中讨论的原因，foldl 通常比 foldr 更有效率。但是，foldr 可以作用于无限列表，而 foldl 则不能。这是因为在 foldl 做任何事情之前，它必须到达列表的末尾。另一方面，foldr 立即开始产生输出。例如，foldr (:) [] [1,2,3,4,5] 只是返回相同的列表。即使列表是无限的，它也会产生输出。使用 foldl 的类似函数将无法产生任何输出。

如果对折叠函数的讨论仍然有些模糊，没关系。我们将在关于列表的章节中进一步讨论它们。

练习
使用 `map` 将字符串转换为布尔值列表，新列表中的每个元素表示原始元素是否为小写字符。也就是说，它应该接收字符串 "aBCde" 并返回 `[True,False,False,True,True]`。

练习
使用本节中提到的函数（你需要两个），计算字符串中小写字母的数量。对于例如，在 "aBCde" 上，它应该返回 3。

练习
我们已经看到如何使用折叠函数计算总和和乘积。鉴于函数 `max` 返回两个数字中的最大值，请编写一个使用折叠的函数，该函数将返回列表中的最大值（如果列表为空则返回零）。因此，当应用于 `[5,10,2,8,1]` 时，它将返回 10。假设列表中的值始终 $\geq 0$ 。向自己解释一下它是如何工作的。

练习
编写一个函数，它接受至少包含两个元素的成对列表，并返回列表中第二个元素的第一部分。因此，当提供 `[(5,'b'),(1,'c'),(6,'a')]` 时，它将返回 1.

源代码文件

作为程序员，我们不希望仅仅评估像这样的简单表达式——我们希望坐下来，在我们选择的编辑器中编写代码，保存它，然后使用它。

我们在之前的章节Ghc和Nhc中已经了解了如何编写一个“Hello World”程序以及如何编译它。在这里，我们将展示如何在交互式环境中使用源代码文件中定义的函数。为此，创建一个名为Test.hs的文件，并输入以下代码

module Test
    where

x = 5
y = (6, "Hello")
z = x * fst y

这是一个用Haskell编写的非常简单的“程序”。它定义了一个名为“Test”的模块（通常模块名称应该与文件名匹配；有关这方面的更多信息，请参阅关于模块的部分）。在这个模块中，有三个定义：x、y和z。编写并保存此文件后，在您保存它的目录中，通过执行以下任一操作，在您喜欢的解释器中加载它：

示例

% hugs Test.hs
% ghci Test.hs

这将分别启动Hugs或GHCi，并加载文件。或者，如果您已经加载了其中一个，您可以使用“:load”命令（或简写为“:l”）加载模块，例如：

示例

Prelude> :l Test.hs
...
Test>

在第一行和最后一行之间，解释器将打印各种数据来解释它正在做什么。如果出现任何错误，您可能在文件中输入错误；仔细检查，然后重试。

您会注意到，以前显示“Prelude”的地方现在显示“Test”。这意味着Test是当前模块。“Prelude”模块（通常简称为“Prelude”）始终加载，并包含标准定义（例如，列表的（:）运算符，或（+）或（*）、fst、snd等等）。

现在我们已经加载了Test，我们可以使用其中定义的内容。例如：

示例

Test> x
5
Test> y
(6,"Hello")
Test> z
30

完美，正如我们预期的那样！

关于如何将程序编译成独立的可执行文件，还有一个最后的问题。为了使程序成为可执行文件，它必须具有模块名称“Main”，并且必须包含一个名为main的函数。因此，如果您进入Test.hs并将其重命名为“Main”（将读取module Test的行更改为module Main），我们只需要添加一个main函数。试试这个：

main = putStrLn "Hello World"

现在，保存文件并编译它（请参阅关于入门的部分，了解如何在您的编译器中执行此操作）。例如，在GHC中，您会说：

示例

% ghc --make Test.hs -o test

注意

对于Windows，它将是“-o test.exe”

这将创建一个名为“test”（或在Windows上为“test.exe”）的文件，然后您可以运行它。

示例

% ./test
Hello World

注意

或者，在Windows上：

示例

C:\> test.exe
Hello World

函数

现在我们已经了解了如何在文件中编写代码，我们可以开始编写函数了。正如您可能预期的那样，函数是Haskell的核心，因为它是一种函数式语言。这意味着程序的求值仅仅是函数的求值。

我们可以编写一个简单的函数来计算一个数的平方，并将其输入到我们的Test.hs文件中。我们可以这样定义它：

square x = x * x

在这个函数定义中，我们说我们正在定义一个名为square的函数，它接受一个参数（也称为形参），我们称之为x。然后我们说square x的值等于x * x。

Haskell也支持标准的条件表达式。例如，我们可以定义一个函数，如果其参数小于 $0$ ，则返回 $-1$ ；如果其参数是 $0$ ，则返回 $0$ ；如果其参数大于 $0$ ，则返回 $1$ （这称为符号函数）。

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

您可以像这样进行实验：

示例

Test> signum 5
1
Test> signum 0
0
Test> signum (5-10)
-1
Test> signum (-1)
-1

请注意，最后一个示例中“-1”周围的括号是必需的；如果缺少，系统会认为您试图从值“signum”中减去值“1”，这是类型错误的。

Haskell中的if/then/else结构与大多数其他编程语言非常相似；但是，您必须同时具有then 和else子句。它评估条件（在本例中为 $x<0$ ），如果此条件求值为True，则它会评估then子句；如果条件求值为False，则它会评估else子句）。

您可以通过编辑文件并将其重新加载到解释器中来测试此程序。如果Test已经是当前模块，则无需再次输入:l Test.hs，您只需输入:reload或:r即可重新加载当前文件。这通常快得多。

Haskell与许多其他语言一样，也支持case结构。当您希望针对多个值进行检查时，可以使用这些结构（case表达式实际上比这强大得多——有关所有详细信息，请参阅关于模式匹配的部分）。

假设我们想要定义一个函数，当它的参数为 $0$ 时，它的值为 $1$ ；当它的参数为 $1$ 时，它的值为 $5$ ；当它的参数为 $2$ 时，它的值为 $2$ ；在所有其他情况下，它的值为 $-1$ 。使用if语句来编写这个函数会很长而且难以阅读；所以我们使用case语句来编写它，如下所示（我们将此函数称为 f）

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

在这个程序中，我们定义 f 来接收一个参数 x，然后检查 x 的值。如果它匹配 $0$ ，则 f 的值为 $1$ 。如果它匹配 $1$ ，则 f 的值为 $5$ 。如果它匹配 $2$ ，则 f 的值为 $2$ ；如果到那时它还没有匹配任何内容，则 f 的值为 $-1$ （下划线可以被认为是“通配符”——它将匹配任何内容）。

这里的缩进很重要。Haskell 使用一个称为“布局”的系统来构建其代码（Python 编程语言使用类似的系统）。布局系统允许您编写代码，而无需其他语言（如 C 和 Java）所需的显式分号和括号。

布局的一般规则是在以下关键字之后插入一个左括号：where, let, do和of，并且记住下一条命令出现的列位置。从那时起，在缩进相同数量的每一新行之前插入一个分号。如果后续行缩进较少，则插入一个右括号。这听起来可能很复杂，但如果您遵循在每个关键字后缩进的一般规则，您将永远不必记住它（有关布局的更完整讨论，请参阅关于布局的部分）。

有些人更喜欢不使用布局并显式地编写括号和分号。这是完全可以接受的。在这种风格中，上述函数可能看起来像这样

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

这里，顺序很重要。如果我们将最后一行放在第一行，它将匹配每个参数，而 f 将返回 -1，而不管其参数是什么（不过，大多数编译器会警告您这一点，并说明一些关于重叠模式的内容）。如果我们没有包含最后一行，如果对 f 应用 0、1 或 2 以外的任何内容，它将产生错误（大多数编译器也会警告您这一点，并说明一些关于不完整模式的内容）。这种分段定义的风格非常流行，并且在本教程中会经常使用。这两个 f 的定义实际上是等价的——这个分段版本被翻译成 case 表达式。

更复杂的函数可以通过函数组合从更简单的函数构建。函数组合只是获取一个函数应用的结果并将其用作另一个函数的参数。我们早在算术中（关于算术的部分）就看到了这一点，当时我们写了 5*4+3。在这里，我们正在评估 $5*4$ ，然后将 $+3$ 应用于结果。我们可以对我们的 square 和 f 函数做同样的事情

示例

Test> square (f 1)
25
Test> square (f 2)
4
Test> f (square 1)
5
Test> f (square 2)
-1

这些函数应用的结果都相当简单明了。内部函数周围的括号是必要的；否则，在第一行中，解释器会认为您试图获取“square f”的值，而这毫无意义。像这样的函数应用在大多数编程语言中都相当标准。还有一种更偏向数学的方式来表达函数组合，使用（.）（只是一个句点）函数。这个（.）函数应该类似于数学中的（ $\circ$ )运算符。

注意

在数学中，我们写 $f\circ g$ 表示“f跟随g”，在Haskell中，我们写f . g也表示“f跟随g”。

$f\circ g$ 的含义很简单，就是 $(f\circ g)(x)=f(g(x))$ 。也就是说，将值 $x$ 应用于函数 $f\circ g$ 与将其应用于 $g$ ，获取结果，然后将其应用于 $f$ 是一样的。

（.）函数（称为函数组合函数）接受两个函数并将它们组合成一个。例如，如果我们写(square . f)，这意味着它创建一个新函数，该函数接受一个参数，将f应用于该参数，然后将square应用于结果。相反，(f . square)意味着它创建一个新函数，该函数接受一个参数，将square应用于该参数，然后将f应用于结果。我们可以像以前一样通过测试来观察这一点。

示例

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

这里，我们必须将函数组合括在括号中；否则，Haskell编译器会认为我们试图在第一行中将square与值f 1组合，这是没有意义的，因为f 1甚至不是一个函数。

可能明智的做法是花一点时间查看Prelude中定义的一些函数。毫无疑问，在某些时候，您会意外地重写一些已经存在的函数（我重写过很多次），但是如果我们能够将这种情况降到最低，将会节省大量时间。以下是一些简单的函数，其中一些我们已经见过。

`sqrt`	平方根函数
`id`	恒等函数：`id x = x`
`fst`	从一个对中提取第一个元素
`snd`	从一个对中提取第二个元素
`null`	告诉你一个列表是否为空
`head`	返回非空列表中的第一个元素
`tail`	返回非空列表中除了第一个元素之外的所有元素
`++`	连接两个列表
`==`	检查两个元素是否相等
`/=`	检查两个元素是否不相等

这里，我们展示了每个函数的使用示例。

示例

Prelude> sqrt 2
1.41421
Prelude> id "hello"
"hello"
Prelude> id 5
5
Prelude> fst (5,2)
5
Prelude> snd (5,2)
2
Prelude> null []
True
Prelude> null [1,2,3,4]
False
Prelude> head [1,2,3,4]
1
Prelude> tail [1,2,3,4]
[2,3,4]
Prelude> [1,2,3] ++ [4,5,6]
[1,2,3,4,5,6]
Prelude> [1,2,3] == [1,2,3]
True
Prelude> 'a' /= 'b'
True
Prelude> head []

Program error: {head []}

我们可以看到，将head应用于空列表会产生错误（确切的错误消息取决于您使用的是GHCi还是Hugs——显示的错误消息来自Hugs）。

Let 绑定

我们通常希望提供局部声明以供函数使用。例如，以下等式用于查找形式为 $ax^{2}+bx+c=0$ 的多项式的根（零点）： $x=(-b\pm {\sqrt {b^{2}-4ac}})/(2a)$ 。我们可以编写以下函数来计算 $x$ 的两个值。

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

不幸的是，我们在这里重复了表达式。为了解决这个问题，Haskell允许进行局部绑定。也就是说，我们可以在函数内部创建仅该函数可见的值。例如，我们可以为表达式sqrt(b*b-4*a*c)创建一个局部绑定，将其称为discr表示判别式，然后在sqrt(b*b - 4*a*c)出现的所有位置使用它。我们可以使用let/in声明

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

实际上，您可以在let内部提供多个声明。只需确保它们的缩进量相同，否则会出现布局问题。

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

中缀

中缀函数是由符号而不是字母组成的函数。例如，(+)、(*)、(++)都是中缀函数。您可以通过将它们括在括号中来在非中缀模式下使用它们。因此，以下两个表达式相同。

示例

Prelude> 5 + 10
15
Prelude> (+) 5 10
15

类似地，非中缀函数（如map）可以通过将它们括在反引号（美国键盘上波浪号键上的撇号）中来使其成为中缀函数。

示例

Prelude> map Data.Char.toUpper "Hello World"
"HELLO WORLD"
Prelude> Data.Char.toUpper `map` "Hello World"
"HELLO WORLD"

注释

Haskell 中有两种类型的注释：行注释和块注释。行注释以标记 -- 开头，一直延伸到行尾。块注释以 {- 开头，一直延伸到对应的 -}。块注释可以嵌套。

注意

Haskell 中的 -- 对应于//C++ 或 Java 中的，而 {- 和 -} 对应于/*和*/.

注释用于用英文解释你的程序，编译器和解释器完全忽略它们。例如

module Test2
    where

main =
  putStrLn "Hello World"  -- write a string
                          -- to the screen

{- f is a function which takes an integer and
produces integer.  {- this is an embedded
comment -} the original comment extends to the
matching end-comment token: -}
f x =
    case x of
      0 -> 1    -- 0 maps to 1
      1 -> 5    -- 1 maps to 5
      2 -> 2    -- 2 maps to 2
      _ -> -1   -- everything else maps to -1

此示例程序演示了行注释和（嵌入式）块注释的使用。

递归

在像 C 和 Java 这样的命令式语言中，最基本的控制结构是循环（如 for 循环）。但是，for 循环在 Haskell 中没有多大意义，因为它们需要破坏性更新（索引变量不断更新）。相反，Haskell 使用递归。

如果一个函数调用自身，则该函数是递归的（有关详细信息，请参阅关于递归的附录）。C 和 Java 中也存在递归函数，但使用频率低于函数式语言。原型递归函数是阶乘函数。在命令式语言中，您可能会这样编写：

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

虽然此代码片段将成功计算正整数的阶乘，但它以某种方式忽略了阶乘的基本定义，通常表示为

$n!={\begin{cases}1&n=1\\n*(n-1)!&{\mbox{otherwise}}\\\end{cases}}$

这个定义本身就是一个递归定义：即 $n!$ 的值取决于 $(n-1)!$ 的值。如果你把 $!$ 视为一个函数，那么它就是在调用自身。我们可以将此定义几乎逐字翻译成 Haskell 代码

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

这可能是你见过的最简单的递归函数，但它是正确的。

注意

当然，可以编写一个命令式递归版本

int factorial(int n) {
  if (n == 1)
    return 1;
  else
    return n * factorial(n-1);
}

但这可能比 C 中的循环版本慢得多。

递归可能是一件难以掌握的事情。它与数学中的归纳概念完全类似（有关更正式的处理，请参阅递归章节）。但是，通常可以将一个问题视为具有一个或多个基本情况和一个或多个递归情况。在factorial的情况下，有一个基本情况（当 $n=1$ ）和一个递归情况（当 $n>1$ ）。对于设计你自己的递归算法，尝试区分这两种情况通常很有用。

现在转向幂运算的任务，假设我们有两个正整数 $a$ 和 $b$ ，并且我们想要计算 $a^{b}$ 。此问题只有一个基本情况：即当 $b$ 为 $1$ 时。递归情况是当 $b>1$ 时。我们可以写成一般形式

$a^{b}={\begin{cases}a&b=1\\a*a^{b-1}&{\mbox{otherwise}}\\\end{cases}}$

同样，这可以直接翻译成 Haskell 代码

exponent a 1 = a
exponent a b = a * exponent a (b-1)

就像我们可以定义整数上的递归函数一样，我们也可以定义列表上的递归函数。在这种情况下，基本情况通常是空列表[]，递归情况是 cons 列表（即，一个值连接到另一个列表上）。

考虑计算列表长度的任务。我们再次可以将其分解为两种情况：要么我们有一个空列表，要么我们有一个非空列表。显然，空列表的长度为零。此外，如果我们有一个 cons 列表，则此列表的长度只是其尾部的长度加一。因此，我们可以将长度函数定义为

my_length [] = 0
my_length (x:xs) = 1 + my_length xs

注意

每当我们为标准 Haskell 函数提供替代定义时，我们都会在它们前面加上my_前缀，以避免编译器混淆。

类似地，我们可以考虑filter函数。同样，基本情况是空列表，递归情况是有头列表。但是，这次，我们会根据某个特定谓词是否成立来选择是否保留元素。我们可以将filter函数定义为

my_filter p [] = []
my_filter p (x:xs) =
  if p x
    then x : my_filter p xs
    else my_filter p xs

在此代码中，当遇到空列表时，我们只需返回一个空列表。这是因为filter不能添加元素；它只能删除元素。

当遇到形如(x:xs)的列表时，我们需要决定是否保留值x。为此，我们使用一个if语句和谓词p。如果p x为真，则我们返回一个以x开头，后跟过滤列表尾部的结果的列表。如果p x为假，则我们排除x并返回过滤列表尾部的结果。

我们还可以使用显式递归来定义map和两个fold函数。有关map的定义，请参阅练习；有关fold的定义，请参阅章节语言高级。

练习

斐波那契数列定义为

$F_{n}={\begin{cases}1&n=1{\mbox{ or }}n=2\\F_{n-2}+F_{n-1}&{\mbox{otherwise}}\\\end{cases}}$

编写一个递归函数fib，它接受一个正整数n作为参数，并计算

F_{n}

。

练习
定义一个递归函数`mult`，它接受两个正整数`a`和`b`，并返回`a*b`，但仅使用加法（即，不能直接使用乘法）。首先以上一练习和本节其余部分的风格进行数学定义，然后编写代码。

练习
定义一个递归函数`my_map`，其行为与标准函数`map`相同。

交互性

如果您熟悉其他（命令式）语言的书籍，您可能想知道为什么在其他语言的教程中没有看到许多标准程序（例如，要求用户输入姓名，然后用姓名向他打招呼的程序）。原因很简单：作为一种纯函数式语言，如何处理用户输入并不完全清楚。

毕竟，假设您有一个从键盘读取字符串的函数。如果您调用此函数两次，并且用户第一次输入一个内容，第二次输入另一个内容，那么您将不再拥有一个函数，因为它将返回两个不同的值。这个问题的解决方案在形式数学的一个分支——范畴论中被发现：单子。我们还没有准备好正式讨论单子，但现在，可以简单地将它们视为表达输入/输出等操作的便捷方式。我们将在章节Io中对此进行更详细的讨论，然后在章节Monads中讨论单子本身。

假设我们想编写一个交互式函数。实现此目的的方法是使用do关键字。这使我们能够指定操作顺序（请记住，通常情况下，由于 Haskell 是一种惰性语言，因此它评估操作的顺序是不确定的）。因此，要编写一个简单的程序，要求用户输入姓名，然后直接称呼他，请将以下代码输入“Name.hs”

module Main
    where

import System.IO

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

注意

第二个putStrLn需要括号，而第一个不需要。这是因为函数应用比++的优先级更高，因此如果没有括号，第二个将被解释为(putStrLn "Hello, ") ++ name ++ ...。

然后，您可以将此代码加载到解释器中并通过简单地键入“main”来执行main，或者可以编译它并从命令行运行它。我将展示交互式方法的结果

示例

Main> main
Please enter your name:
Hal
Hello, Hal, how are you?
Main>

这就是交互性。不过，让我们回过头来仔细看看代码。我们将模块命名为“Main”，以便我们可以编译它。我们将主要函数命名为“main”，以便编译器知道在运行程序时要运行哪个函数。在第四行，我们导入IO库，以便我们可以访问IO函数。在第七行，我们以do开头，告诉 Haskell 我们正在执行一系列命令。

第一个命令是hSetBuffering stdin LineBuffering，您现在可以忽略它（顺便说一句，这仅由GHC需要——在Hugs中，您可以不用它）。这是必要的，因为当GHC读取输入时，它期望以相当大的块读取它。一个典型的人的名字远不足以填满这个块。因此，当我们尝试从stdin读取时，它会等到获得一个完整的块。我们想摆脱这一点，所以我们告诉它使用LineBuffering而不是块缓冲。

下一个命令是putStrLn，它将字符串打印到屏幕上。在第九行，我们说name <- getLine。这通常写成name = getLine，但使用箭头而不是等号表示getLine不是一个真正的函数，可以返回不同的值。此命令表示“运行操作getLine，并将结果存储在name中”。

最后一行使用我们在前一行读取的内容构造一个字符串，然后将其打印到屏幕上。

另一个不是真正函数的函数示例是返回随机值的函数。在这种情况下，执行此操作的函数称为randomRIO。使用它，我们可以编写一个“猜数字”程序。将以下代码输入“Guess.hs”

module Main
    where

import System.IO
import System.Random

main = do
  hSetBuffering stdin LineBuffering
  num <- randomRIO (1::Int, 100)
  putStrLn "I'm thinking of a number between 1 and 100"
  doGuessing num

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

让我们检查一下这段代码。在第五行，我们写“import Random”来告诉编译器我们将使用一些随机函数（这些函数没有内置在Prelude中）。在main的第一行，我们要求在范围 $(1,100)$ 内生成一个随机数。我们需要写::Int来告诉编译器我们在这里使用整数——而不是浮点数或其他数字。我们将在关于类型基础的部分中详细讨论这一点。在下一行，我们告诉用户发生了什么事，然后，在main的最后一行，我们告诉编译器执行命令doGuessing。

doGuessing函数以用户尝试猜测的数字作为参数。首先，它要求用户猜测，然后从键盘接受他们的猜测（这是一个String）。该if语句首先检查用户的猜测是否过低。但是，由于guess是一个字符串，而num是一个整数，因此我们首先需要通过read将guess转换为整数。由于“read guess”是一个普通的、纯的函数（而不是IO操作），因此我们不需要使用<-符号（实际上，我们不能使用）；我们只需将值绑定到guessNum。请注意，当我们在do符号中时，我们不需要in用于let。

如果他们猜得太低，我们通知他们，然后再次开始doGuessing。如果他们没有猜得太低，我们检查他们是否猜得太高。如果他们猜得太高，我们告诉他们，然后再次开始doGuessing。否则，他们没有猜得太低，也没有猜得太高，所以他们一定猜对了。我们告诉他们他们赢了并退出。我们退出的事实隐含在没有后续命令的事实中。我们不需要显式的return ()语句。

您可以编译此代码或将其加载到您的解释器中，您将获得类似以下内容的结果

示例

Main> main
I'm thinking of a number between 1 and 100
Enter your guess:
50
Too low!
Enter your guess:
75
Too low!
Enter your guess:
85
Too high!
Enter your guess:
80
Too high!
Enter your guess:
78
Too low!
Enter your guess:
79
You Win!

我们刚刚看到的递归操作实际上并没有返回我们在任何地方使用的值。在确实返回值的情况下，编写命令的“显而易见”方法实际上是不正确的。在这里，我们将给出错误的版本，解释它为什么错误，然后给出正确的版本。

假设我们正在编写一个简单的程序，该程序反复要求用户输入一些单词。如果用户在任何时候输入空单词（即，他只是按回车键而不输入任何内容），程序会打印出他到那时为止键入的所有内容，然后退出。此程序中的主要函数（实际上是一个操作）是询问用户一个单词，检查它是否为空，然后继续或结束。此操作的错误表述可能如下所示

askForWords = do
  putStrLn "Please enter a word:"
  word <- getLine
  if word == ""
    then return []
    else return (word : askForWords)

在继续阅读之前，看看您是否能找出上面代码中的错误。

错误在最后一行，具体是在word : askForWords这一项。请记住，当使用（:）时，我们正在从一个元素（在本例中为word）和另一个列表（在本例中为askForWords）创建一个列表。但是，askForWords不是一个列表；它是一个操作，当运行时，将产生一个列表。这意味着在我们能够将任何内容附加到前面之前，我们需要运行该操作并获取结果。在本例中，我们希望执行类似以下操作

askForWords = do
  putStrLn "Please enter a word:"
  word <- getLine
  if word == ""
    then return []
    else do
      rest <- askForWords
      return (word : rest)

在这里，我们首先运行askForWords，获取结果并将其存储在变量rest中。然后，我们返回由word和rest创建的列表。

到目前为止，您应该已经很好地理解了如何编写简单的函数、编译它们、在交互式环境中测试函数和程序以及操作列表。

练习

编写一个程序，反复询问用户输入数字，直到她输入零，此时程序会告诉她所有数字的总和、所有数字的乘积以及每个数字的阶乘。例如，一个会话可能如下所示

示例

Give me a number (or 0 to stop):
5
Give me a number (or 0 to stop):
8
Give me a number (or 0 to stop):
2
Give me a number (or 0 to stop):
0
The sum is 15
The product is 80
5 factorial is 120
8 factorial is 40320
2 factorial is 2

提示：编写一个IO操作，读取一个数字，如果它是零，则返回空列表。如果不是零，它会递归调用自身，然后从它刚刚读取的数字和递归调用的结果创建一个列表。

提示：您需要使用“show”来打印数字。putStrLn("Number " ++ show(n))