跳转到内容

Haskell/列表和元组

来自维基教科书，开放世界中的开放书籍

Haskell 使用两种基本结构来管理多个值：列表和元组。它们都通过将多个值组合成一个单一组合值来工作。

列表和元组 (解决方案)
Haskell 基础

入门设置
变量和函数
真值
类型基础
列表和元组
类型基础 II
下一步
构建词汇
简单的输入和输出

列表

[编辑 | 编辑源代码]

让我们在 GHCi 中构建一些列表

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

构建列表

[编辑 | 编辑源代码]

除了使用方括号和逗号一次性指定整个列表之外，还可以使用 (:) 运算符（发音为“cons”）逐个构建列表。这种构建列表的过程通常被称为consing。这个术语来自 LISP 程序员，他们发明了动词“cons”（“constructor”的助记符）来指代这种将元素追加到列表的特定任务。

示例： 将某些内容添加到列表中

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

当您将某些内容添加到列表中 (something:someList) 时，您将获得另一个列表。因此，您可以根据需要继续 consing。请注意，cons 运算符从右到左计算。另一种（更一般的）理解方式是，它将左边的第一个值和右边的整个表达式取进来。

示例： 将许多内容添加到列表中

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

实际上，Haskell 通过将所有元素添加到空列表 [] 中来构建所有列表。逗号和括号符号只是语法糖。因此，[1,2,3,4,5] 等效于 1:2:3:4:5:[]

但是，您需要注意列表构造中可能出现的一个潜在陷阱。虽然 True:False:[] 是完全合法的 Haskell，但 True:False不是

示例： 哎呦！

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

True:False 产生了一个看起来很熟悉的类型错误消息。它告诉我们 cons 运算符 (:)（实际上只是一个函数）期望列表作为它的第二个参数，但我们给它传递了另一个 Bool。(:) 只知道如何将东西添加到列表中。[1]

因此，在使用 cons 时，请记住

  • 列表的元素必须具有相同的类型。
  • 您只能将某些内容添加到列表中 ((:))，而不能反过来（您不能将列表添加到元素中）。因此，最右边的项目必须是一个列表，而左边的项目必须是独立的元素，而不是列表。
练习
  1. 以下 Haskell 代码段是否有效：3:[True,False]？为什么或者为什么不？
  2. 编写一个函数 cons8，它接受一个列表作为参数，并将 8（在开头）添加到该列表中。通过以下方式在以下列表上对其进行测试
    1. cons8 []
    2. cons8 [1,2,3]
    3. cons8 [True,False]
    4. let foo = cons8 [1,2,3]
      cons8 foo
  3. 以将 8 放在列表末尾的方式修改上述函数。（提示：回顾上一章中的连接运算符 ++。）
  4. 编写一个函数，它接受两个参数（一个列表和一个事物），并将事物添加到列表中。您可以从以下内容开始
let myCons list thing =

字符串只是列表

[编辑 | 编辑源代码]

正如我们在“类型基础”模块中简要提到的那样，Haskell 中的字符串只是字符列表。这意味着类型为 String 的值可以像任何其他列表一样被操作。例如，可以使用 (:) 连接字符并以空列表结尾，或者使用逗号和括号表示法，而不是直接将字符串输入为用双引号括起来的字符序列，而是可以通过一系列 Char 值来构造它们。

Prelude> "hey" == ['h','e','y']
True
Prelude> "hey" == 'h':'e':'y':[]
True

使用双引号字符串只是更具语法的糖。

列表的列表

[编辑 | 编辑源代码]

列表可以包含任何东西——只要它们都是相同的类型。因为列表也是事物，所以列表可以包含其他列表！在解释器中尝试以下操作

示例： 列表可以包含列表

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

列表的列表有时很棘手，因为事物的列表与事物本身的类型不同。类型 Int 与 [Int] 不同。让我们通过一些练习来理清这些含义

练习
  1. 以下哪些是有效的 Haskell，哪些不是？用 cons 表示法重写。
    1. [1,2,3,[]]
    2. [1,[2,3],4]
    3. [[1,2,3],[]]
  2. 以下哪些是有效的 Haskell，哪些不是？用逗号和括号表示法重写。
    1. []:[[1,2,3],[4,5,6]]
    2. []:[]
    3. []:[]:[]
    4. [1]:[]:[]
    5. ["hi"]:[1]:[]
  3. Haskell 可以有列表的列表的列表吗？为什么或者为什么不？
  4. 为什么以下列表在 Haskell 中无效？
    1. [[1,2],3,[4,5]]

不同类型的元素的列表不能被 cons，但空列表可以被任何类型的列表 cons。例如，[]:[[1, 2], [1, 2, 3]] 是有效的，并将产生 [[], [1, 2], [1, 2, 3]]，而 [1]:[[1, 2], [1, 2, 3]] 是有效的，并将产生 [[1], [1, 2], [1, 2, 3]]，但 ['a']:[[1, 2], [1, 2, 3]] 将产生错误消息。

列表的列表允许我们表达一些复杂的有结构数据（例如二维矩阵）。它们也是 Haskell 类型系统真正闪耀的地方之一。人类程序员（包括这本维基教科书的合著者）在处理列表的列表时总是会感到困惑，而对类型的限制通常有助于克服潜在的混乱。

元组

[编辑 | 编辑源代码]

一个不同的“许多”概念

[编辑 | 编辑源代码]

元组提供了一种在单个值中存储多个值的其他方式。元组和列表有两个主要区别

  • 元组具有固定数量的元素（不可变）；您不能对元组进行 consing。因此，当您事先知道要存储多少个值时，使用元组是有意义的。例如，我们可能想要一种类型来存储点的二维坐标。我们确切地知道每个点需要多少个值（两个 - x 和 y 坐标），因此元组是适用的。
  • 元组的元素不需要是相同的类型。例如，在电话簿应用程序中，我们可能想要通过将三个值压缩成一个来处理条目：姓名、电话号码和我们拨打电话的次数。在这种情况下，三个值不会具有相同的类型，因为姓名和电话号码是字符串，但联系人计数器将是一个数字，所以列表将不起作用。

元组用括号标记，元素用逗号分隔。让我们看一些元组示例

示例： 一些元组

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

第一个示例是一个包含两个元素的元组：True 和 1。下一个示例又包含两个元素：“Hello world” 和 False。第三个示例是一个包含五个元素的元组：4（一个数字）、5（另一个数字）、“Six”（一个字符串）、True（一个布尔值）和 'b'（一个字符）。

关于术语的快速说明：通常，您使用n 元组来表示大小为n 的元组。通常，我们将 2 元组（即包含 2 个元素的元组）称为对，并将 3 元组称为三元组。更大尺寸的元组实际上并不常见，但我们可以逻辑地将命名系统扩展为四元组、五元组等等。

练习
  1. 写下第一个元素为 4、第二个元素为“hello”、第三个元素为 True 的 3 元组。
  2. 以下哪些是有效的元组？
    1. (4, 4)
    2. (4, "hello")
    3. (True, "Blah", "foo")
    4. ()
  3. 列表可以通过对它们进行 consing 新元素来构建。将数字 cons 到数字列表中，您将获得一个数字列表。没有这种构建元组的方式。
    1. 您认为这是为什么？
    2. 为了论证，假设存在这样的函数。如果您对元组进行“consing”，您将得到什么？


当您想从函数中返回多个值时，元组非常方便。在许多语言中，一次返回两个或多个值通常需要将它们包装在单一用途的数据结构中，也许只在该函数中使用。在 Haskell 中，我们将这些结果作为元组返回。

元组中的元组（和其他组合）

[编辑 | 编辑源代码]

我们可以在关于将列表存储在列表中的元组上应用相同的推理。元组也是事物，所以你可以在元组中存储元组（在元组中，直到任意级别的复杂性）。同样，你也可以拥有元组列表，元组列表，以及各种相关的组合。

示例：嵌套元组和列表

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

元组的类型不仅由其大小定义，而且与列表一样，由它包含的对象的类型定义。例如，元组("Hello",32)和(47,"World")从根本上是不同的。一个是(String,Int)类型，而另一个是(Int,String)类型。这对构建元组列表有影响。我们可以很容易地拥有像[("a",1),("b",9),("c",9)]这样的列表，但是Haskell不能拥有像[("a",1),(2,"b"),(9,"c")]这样的列表。

练习
  1. 这些中哪些是有效的Haskell，为什么？
    • 1:(2,3)
    • (2,4):(2,3)
    • (2,4):[]
    • [(2,4),(5,5),('a','b')]
    • ([2,4],[2,2])

检索值

[编辑 | 编辑源代码]

为了使列表和元组有用，我们需要访问它们包含的内部值。

让我们从表示点(x, y)坐标的对（即 2 元组）开始。想象你想要在棋盘上指定一个特定的方格。你可以从 1 到 8 给行和列贴标签。然后，一对(2, 5)可以表示第 2 行第 5 列的方格。假设我们想要一个函数来查找给定行中的所有棋子。我们可以从所有棋子的坐标开始，然后查看行部分，看看它是否等于我们要检查的任何行。给定棋子的坐标对(x, y)，我们的函数需要提取x（行坐标）。为了达到这种目的，有两个标准函数，fst和snd，它们分别检索[2]对中的第一个和第二个元素。让我们看一些例子

示例：使用fst和snd

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

请注意，根据定义，这些函数仅适用于对。[3]

对于列表，函数head和tail大致类似于fst和snd。它们通过拆开(:)连接的部分来拆解列表。head计算列表的第一个元素，而tail给出列表的其余部分。

示例：使用head和tail

Prelude> 2:[7,5,0]
[2,7,5,0]
Prelude> head [2,7,5,0]
2
Prelude> tail [2,7,5,0]
[7,5,0]


注意

不幸的是，head和tail有一个严重的问题。如果我们将它们中的任何一个应用于空列表...

Prelude> head []
*** Exception: Prelude.head: empty list

...它会爆炸，因为空列表没有第一个元素，也没有其他任何元素。在GHCi之外，尝试在空列表上运行head或tail会使程序崩溃。

我们暂时会使用head和tail，但我们希望避免在实际代码中出现这种故障的任何风险，因此我们将在后面的章节中学习更好的选择。有人可能会问“有什么问题呢？如果我们小心，从不向它们传递空列表，或者我们以某种方式在调用它们之前测试列表是否为空，那么使用head和tail就可以正常工作。”但那条路通向疯狂。

随着程序变得越来越大、越来越复杂，空列表最终被传递给head和tail的地方数量会迅速增加，我们可能会犯错的地方数量也会随之增加。作为经验法则，你应该避免可能在没有警告的情况下失败的函数。随着我们在本书中不断前进，我们将学习更好的方法来避免这些风险。


待解决问题

[编辑 | 编辑源代码]

这里介绍的四个函数似乎并没有完全解决我们开始这部分内容时遇到的问题。虽然fst和snd为对提供了一个令人满意的解决方案，但对于有三个或更多元素的元组呢？对于列表，我们能做得比仅仅在第一个元素之后分解它们更好吗？目前，我们必须将这些问题搁置。在我们完成一些必要的准备工作之后，我们将在未来关于列表操作的章节中回到这个主题。现在，请记住，分离列表的头和尾将允许我们做任何我们想做的事情。

练习
  1. 使用fst和snd的组合从元组(("Hello", 4), True)中提取 4。
  2. 正常的象棋符号与我们的有点不同：它将行从 1-8 编号，列从 a-h 编号；并且通常首先给出列标签。我们可以用字符和数字给特定点贴标签，例如('a', 4)吗？这说明了与列表有什么重要的区别？
  3. 编写一个函数，该函数将列表的头和尾作为元组的第一个和第二个元素返回。
  4. 使用head和tail编写一个函数，该函数给出列表的第五个元素。然后，对其进行批评，指出你注意到的任何烦人和陷阱。

多态类型

[编辑 | 编辑源代码]

回想一下，列表的类型取决于其元素的类型，并用方括号将其括起来表示

Prelude> :t [True, False]
[True, False] :: [Bool]
Prelude> :t ["hey", "my"]
["hey", "my"] :: [[Char]]

Bool的列表与[Char]的列表（与String的列表相同，因为[Char]和String是同义词）是不同的类型。由于函数只接受函数类型中指定的类型的参数，这可能会导致一些复杂情况。例如，考虑head的情况。鉴于[Int]、[Bool]和[String]是不同的类型，我们似乎需要为每种情况分别创建函数——headInt :: [Int] -> Int、headBool :: [Bool] -> Bool、headString :: [String] -> String等等… 然而，这不仅非常烦人，而且毫无意义。毕竟，列表的组装方式与它们包含的值的类型无关，因此我们期望获取列表第一个元素的过程在所有情况下都保持一致。

幸运的是，我们确实有一个适用于所有列表的单一函数head

Prelude> head [True, False]
True
Prelude> head ["hey", "my"]
"hey"

这怎么可能呢？像往常一样，检查head的类型会提供一个很好的提示

示例：我们的第一个多态类型

Prelude> :t head
head :: [a] -> a

签名中的a不是类型——记住类型名称总是以大写字母开头。相反，它是一个类型变量。当Haskell看到一个类型变量时，它允许任何类型代替它的位置。在类型论（数学的一个分支）中，这被称为多态性：只有单一类型的函数或值被称为单态的，而使用类型变量来承认多种类型的东西则被称为多态的。例如，head的类型告诉我们它接受一个任意类型（a）的列表（[a]），并返回该相同类型（a）的值。

请注意，在单个类型签名中，同一个类型变量的所有情况必须是相同类型。例如，

f :: a -> a

表示f接受任何类型的参数，并返回与参数相同类型的结果，而不是

f :: a -> b

表示f接受任何类型的参数，并返回任何类型的结果，该结果可能或可能不与我们为a提供的类型匹配。不同的类型变量没有指定类型必须不同，它只是说它们可以不同。

示例：fst和snd

[编辑 | 编辑源代码]

正如我们所见，你可以使用fst和snd函数来提取对的一部分。到目前为止，你应该已经养成了习惯，即对于你遇到的每一个函数，都要问“这是什么类型？”。让我们考虑fst和snd的情况。这两个函数以对作为参数，并返回该对的一个元素。与列表一样，对的类型取决于其元素的类型，因此函数需要是多态的。还要记住，对（以及一般意义上的元组）不需要在内部类型方面是同质的。因此，如果我们要说

fst :: (a, a) -> a

那意味着fst只有在给定作为输入的对的第一个和第二个部分具有相同类型的情况下才能工作。因此，正确的类型是

示例：fst和snd的类型

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

如果你除了类型签名之外对fst和snd一无所知，你仍然可能会猜测它们分别返回对的第一个和第二个部分。虽然这是正确的，但其他函数也可能具有相同的类型签名。所有签名都表明的是，它们只需要返回与对的第一个和第二个部分相同类型的东西。

练习

为以下函数给出类型签名

  1. 前一部分的第三个练习的解决方案（“...返回列表的头和尾作为元组的第一个和第二个元素的函数”）。
  2. 前一部分的第四个练习的解决方案（“...给出列表的第五个元素的函数”）。
  3. h x y z = chr (x - 2)（记住我们在上一章中讨论了 chr）。

总结

[编辑 | 编辑源代码]

本章介绍了列表和元组。它们之间的关键相似之处和区别在于

  1. 列表由方括号和逗号定义：[1,2,3]。
    • 只要列表的所有元素都是相同类型，列表就可以包含任何东西。
    • 列表也可以通过 cons 运算符(:)构建，但你只能将东西 cons 到列表上。
  2. 元组由圆括号和逗号定义：("Bob",32)
    • 元组可以包含任何东西，即使是不同类型的东西。
    • 元组的长度在其类型中编码；不同长度的元组将具有不同的类型。
  3. 列表和元组可以以多种方式组合：列表中包含列表，元组中包含列表，等等，但它们的标准必须仍然满足才能使组合有效。

备注

  1. ↑ 此时你可能会质疑类型的价值。虽然一开始它们可能让人感到很烦人，但往往它们最终证明非常有用。无论如何，当你在 Haskell 中编程并且出现错误时，你可能希望考虑“类型错误”。
  2. ↑ 或者，更技术地说，"...投影，投影元素..." 在数学术语中，从结构中获取数据的函数称为投影。
  3. ↑ 是的，可以设计一个函数来从任何大小的元组中提取第一个元素，但它不像你想的那么简单，而且它不是标准库中的 fst 和 snd 函数的工作方式。
取自 "https://wikibooks.cn/w/index.php?title=Haskell/Lists_and_tuples&oldid=3848349"
华夏公益教科书