Haskell/其他数据结构

其他数据结构

中级 Haskell

在本章中，我们将通过示例说明如何使用我们迄今为止研究的技术来处理更复杂的数据类型。特别是，我们将看到递归数据结构的示例，这些数据结构是包含相同类型的值的数据类型。递归数据结构在许多编程技术中发挥着至关重要的作用，因此即使您不需要经常定义一个新的数据结构（与使用库中的现有数据结构相比），了解它们是什么以及如何操作它们也很重要。除此之外，仔细遵循本章中的实现是您初学者 Haskell 能力的一个很好的练习。

注意

Haskell 库生态系统提供了大量的数据结构（递归的和非递归的），涵盖了广泛的实际需求。除了列表之外，还有映射、集合、有限序列和数组，等等。学习主要数据结构的最佳起点是 Haskell 实践跟踪中的数据结构入门。我们建议您在完成接下来的几个中级 Haskell 章之后至少快速浏览一遍。

树

递归数据结构中最重要的类型之一是树。树的类型有很多，所以我们任意选择一个简单的树作为例子。以下是它的定义

data Tree a = Leaf a | Branch (Tree a) (Tree a)

如您所见，它是参数化的；也就是说，我们可以有 Int 类型的树，String 类型的树，Maybe Int 类型的树，(Int, String) 对类型的树等等。使这个数据类型特殊的是 Tree 出现在它自己的定义中。一个 Tree a 要么是一个叶，包含类型 a 的值，要么是一个分支，从它悬挂着另外两棵类型 Tree a 的树。

列表作为树

正如我们在 Lists II 和 Lists III 中所见，我们将列表分解为两种情况：一个空列表（用[]表示），以及指定类型的一个元素加上另一个列表（用(x:xs)表示）。这意味着列表数据类型的定义可能看起来像这样

 -- Pseudo-Haskell, will not actually work (because lists have special syntax).
data [a] = [] | (a:[a])

您可以实际操作的等效定义是

data List a = Nil | Cons a (List a)

与树一样，列表也是递归的。对于列表，构造函数是 [] 和 (:)。它们分别对应于上面 Tree 定义中的 Leaf 和 Branch。这意味着我们可以像使用空列表和 (x:xs) 一样使用 Leaf 和 Branch 进行模式匹配。

映射和折叠

我们已经了解了列表的映射和折叠。现在，我们可以为新的 Tree 类型编写映射和折叠函数。回顾一下

data Tree a = Leaf a | Branch (Tree a) (Tree a) deriving (Show)
data [a]    = []     | (:)    a [a]
  -- (:) a [a] is the same as (a:[a]) with prefix instead of infix notation.

注意

推导将在后面的类和类型部分进行解释。现在，将其理解为告诉 Haskell（以及扩展到您的解释器）如何显示 Tree 实例。

映射

让我们看一下列表 map 的定义

map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = f x : map f xs

如果我们要编写 treeMap，它的类型是什么？如果您知道它的类型应该是什么，定义函数就会更容易。

我们希望 treeMap 在某个类型的 Tree 上工作，并通过对树的每个元素应用一个函数来返回另一个某个类型的 Tree。

treeMap :: (a -> b) -> Tree a -> Tree b

这与列表示例一样。

现在，当谈论 Tree 时，每个 Leaf 只包含一个值，因此我们所要做的就是将给定的函数应用于该值，然后返回一个带有更改后的值的 Leaf

treeMap :: (a -> b) -> Tree a -> Tree b
treeMap f (Leaf x) = Leaf (f x)

这与 map 中的空列表情况非常相似。现在，如果我们有一个 Branch，它将包含两个子树；我们该如何处理这些子树？列表 map 对列表的尾部（递归）使用了一个对自身的调用，因此我们也应该对这两个子树这样做。treeMap 的完整定义如下

treeMap :: (a -> b) -> Tree a -> Tree b
treeMap f (Leaf x) = Leaf (f x)
treeMap f (Branch left right) = Branch (treeMap f left) (treeMap f right)

我们可以通过注意到 treeMap f 本身是一个类型为 Tree a -> Tree b 的函数来使代码更具可读性。这给了我们以下修改后的定义

treeMap :: (a -> b) -> Tree a -> Tree b
treeMap f = g where
  g (Leaf x) = Leaf (f x)
  g (Branch left right) = Branch (g left) (g right)

如果您没有立即理解这一点，请尝试重新阅读。这种模式匹配的使用乍一看可能很奇怪，但对于数据类型的使用至关重要。请记住，模式匹配发生在构造函数上。

准备好了就继续阅读有关树的折叠的信息。

折叠

与映射一样，让我们首先回顾一下列表 foldr 的定义

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f acc [] = acc
foldr f acc (x:xs) = f x (foldr f acc xs)

回想一下列表有两个构造函数

(:) :: a -> [a] -> [a]  -- takes an element and combines it with the rest of the list
[] :: [a]  -- the empty list takes zero arguments

因此 foldr 接受两个参数，分别对应于这两个构造函数

f :: a -> b -> b  -- a function takes two elements and operates on them to return a single result
acc :: b  -- the accumulator defines what happens with the empty list

让我们花点时间澄清这一点。如果初始 foldr 给定一个空列表，则返回默认累加器。对于非空列表，将第一个元素与折叠列表尾部的结果（使用 f）组合起来，因此折叠会一直进行，直到我们到达空列表。

与列表的 foldr 一样，我们希望 treeFold 将某个类型的树转换为另一个类型的值；因此，我们将使用 Tree a -> b 而不是 [a] -> b。我们如何指定转换？首先要注意 Tree a 有两个构造函数（就像列表有两个构造函数一样）

Branch :: Tree a -> Tree a -> Tree a
Leaf :: a -> Tree a

所以 treeFold 将有两个参数，分别对应于这两个构造函数

fbranch :: b -> b -> b
fleaf :: a -> b

综合起来，我们得到以下类型定义

treeFold :: (b -> b -> b) -> (a -> b) -> Tree a -> b

也就是说，第一个参数的类型为 (b -> b -> b)，是一个指定如何将子树组合成单个结果的函数；第二个参数的类型为 a -> b，是一个指定如何处理叶子（它是递归的结尾，就像空列表对于列表一样）的函数；第三个参数的类型为 Tree a，是我们想要折叠的整个树。

与 treeMap 一样，我们将通过引入一个局部函数 g 来避免重复参数 fbranch 和 fleaf

treeFold :: (b -> b -> b) -> (a -> b)  -> Tree a -> b
treeFold fbranch fleaf = g where
  -- definition of g goes here

参数 fleaf 告诉我们如何处理 Leaf 子树

g (Leaf x) = fleaf x

参数 fbranch 告诉我们如何将两个子树的“折叠”结果组合起来

g (Branch left right) = fbranch (g left) (g right)

我们的完整定义变为

treeFold :: (b -> b -> b) -> (a -> b) -> Tree a -> b
treeFold fbranch fleaf = g where
  g (Leaf x) = fleaf x
  g (Branch left right) = fbranch (g left) (g right)

有关这些工作原理的示例，将 Tree 数据定义以及 treeMap 和 treeFold 函数复制到一个 Haskell 文件中，以及以下示例树和折叠示例函数。

tree1 :: Tree Integer
tree1 = 
    Branch
       (Branch 
           (Branch 
               (Leaf 1) 
               (Branch (Leaf 2) (Leaf 3))) 
           (Branch 
               (Leaf 4) 
               (Branch (Leaf 5) (Leaf 6)))) 
       (Branch
           (Branch (Leaf 7) (Leaf 8)) 
           (Leaf 9))
 
doubleTree = treeMap (*2)  -- doubles each value in tree
sumTree = treeFold (+) id -- sum of the leaf values in tree
fringeTree = treeFold (++) (: [])  -- list of the leaves of tree

然后将它加载到 GHCi 中并进行评估

doubleTree tree1
sumTree tree1

其他数据类型

映射和折叠函数可以为任何类型的数据类型定义。为了概括应用于列表和树的策略，在本节的最后，我们将为一个非常奇怪、人为构建的数据类型计算映射和折叠

data Weird a b = First a
               | Second b
               | Third [(a,b)]
               | Fourth (Weird a b)

在您按照示例操作时编写函数可能是一个有益的练习，尝试让编码领先于阅读一步。

一般映射

在使用这种 Weird 类型时，第一个重要的区别是它具有两个类型参数。因此，我们希望映射函数接受两个函数作为参数，一个用于应用于类型a的元素，另一个用于应用于类型b的元素。考虑到这一点，我们可以编写 weirdMap 的类型签名

weirdMap :: (a -> c) -> (b -> d) -> Weird a b -> Weird c d

下一步是定义weirdMap。关键是映射保留了数据类型的结构，因此该函数必须计算为一个使用与原始Weird相同的构造函数的Weird。因此，我们需要一个定义来处理每个构造函数，这些构造函数被用作编写它们的模式。和以前一样，为了避免重复weirdMap的参数列表，where 子句非常有用。下面是该函数的草图。

weirdMap :: (a -> c) -> (b -> d) -> Weird a b -> Weird c d
weirdMap fa fb = g
  where
    g (First x)          = --More to follow
    g (Second y)         = --More to follow
    g (Third z)          = --More to follow
    g (Fourth w)         = --More to follow

前两种情况相当简单，因为Weird内部只有一个a或b类型的元素。

weirdMap :: (a -> c) -> (b -> d) -> Weird a b -> Weird c d
weirdMap fa fb = g
  where
    g (First x)          = First (fa x)
    g (Second y)         = Second (fb y)
    g (Third z)          = --More to follow
    g (Fourth w)         = --More to follow

Third 比较棘手，因为它包含一个列表，其元素本身是数据结构（元组）。因此，我们需要遍历嵌套的数据结构，对所有类型为a和b的元素应用fa和fb，最后（因为映射必须保留结构）生成一个元组列表 - [(c,d)] - 用于构造函数。最简单的方法似乎只是分解Weird内部的列表并使用模式进行操作。

    g (Third []) = Third []
    g (Third ((x,y):zs)) = Third ( (fa x, fb y) : ( (\(Third z) -> z) (g (Third zs)) ) )

这似乎是作为列表的典型递归函数编写的。我们首先将感兴趣的函数应用于第一个元素以获得新列表的头部，(fa x, fb y)。但我们会把它与什么连接起来呢？由于g需要一个Weird参数，我们需要使用列表尾部创建一个Weird以进行递归调用。但是，g将返回一个Weird而不是一个列表，因此我们必须从该Weird中检索修改后的列表 - 这就是 lambda 函数的作用。最后，还需要定义空列表基本情况。

经过所有这些，我们得到一个混乱的函数。每次递归调用g都需要将zs包装到一个Weird中，而我们真正想要做的是使用(fa x, fb y)和修改后的xs来构建一个列表。此解决方案的问题在于g可以（通过模式匹配）直接作用于列表头，但（由于其类型签名）不能直接调用列表尾部。因此，最好在不使用模式匹配分解列表的情况下应用fa和fb（至少就g直接而言）。但是，确实存在直接逐元素修改列表的方法...

    g (Third z) = Third ( map (\(x, y) -> (fa x, fb y) ) z)

...我们久经考验的map 函数，它使用 lambda 函数修改列表z中的所有元组。事实上，编写定义的第一个尝试看起来就像一个列表映射的应用，除了多余的Weird打包和解包。我们通过让map完成z的模式拆分来消除这些，map直接与常规列表一起工作。您可能觉得将 map 定义扩展到g内部以更清楚地看到区别很有用。最后，您可能更喜欢使用列表推导语法以另一种简洁的方式编写此新版本。

    g (Third z) = Third [ (fa x, fb y) | (x,y) <- z ]

添加Third函数后，只剩下Fourth要定义了。

weirdMap :: (a -> c) -> (b -> d) -> Weird a b -> Weird c d
weirdMap fa fb = g
  where
    g (First x)          = First (fa x)
    g (Second y)         = Second (fb y)
    g (Third z)          = Third ( map (\(x, y) -> (fa x, fb y) ) z)
    g (Fourth w)         = --More to follow

我们只需要递归地应用g即可。

weirdMap :: (a -> c) -> (b -> d) -> Weird a b -> Weird c d
weirdMap fa fb = g
  where
    g (First x)          = First (fa x)
    g (Second y)         = Second (fb y)
    g (Third z)          = Third ( map (\(x, y) -> (fa x, fb y) ) z)
    g (Fourth w)         = Fourth (g w)

通用折叠

虽然我们能够通过为每个单独的类型指定一个函数来定义映射，但这对于折叠来说还不够。对于折叠，我们需要为每个构造函数提供一个函数。在列表中，构造函数是[]和(:)。foldr 函数中的acc参数对应于[]构造函数。foldr 函数中的f参数对应于(:)构造函数。Weird 数据类型有四个构造函数，因此我们需要四个函数 - 一个用于处理每个构造函数指定的数据类型的内部结构。接下来，我们有一个Weird a b类型的参数，最后我们希望整个折叠函数计算为其他一些任意类型的值。此外，我们传递给weirdFold的每个函数必须计算为与weirdFold相同的类型。这使我们能够制作一个模拟类型签名并草拟定义。

weirdFold :: (something1 -> c) -> (something2 -> c) -> (something3 -> c) -> (something4 -> c) -> Weird a b -> c
weirdFold f1 f2 f3 f4 = g
  where
    g (First x)          = --Something of type c here
    g (Second y)         = --Something of type c here
    g (Third z)          = --Something of type c here
    g (Fourth w)         = --Something of type c here

现在，我们需要弄清楚哪些类型对应于something1、something2、something3和something4。这是通过分析构造函数来完成的，因为函数必须以数据类型元素作为参数（这些元素的类型由构造函数类型签名指定）。同样，前两个函数的类型和定义很简单。第三个也不难，因为就折叠(a,b)列表而言，元组与简单类型没有区别（与 map 示例不同，现在内部结构并不重要）。然而，第四个构造函数是递归的，我们需要小心。与weirdMap一样，我们还需要递归地调用g函数。这使我们得到了最终的定义。

weirdFold :: (a -> c) -> (b -> c) -> ([(a,b)] -> c) -> (c -> c) -> Weird a b -> c
weirdFold f1 f2 f3 f4 = g
  where
    g (First x)          = f1 x
    g (Second y)         = f2 y
    g (Third z)          = f3 z
    g (Fourth w)         = f4 (g w)

注意

如果您期望在上面的weirdFold中看到非常复杂的表达式，并对解决方案的直接性感到惊讶，那么看看如果我们用这种风格编写常见的foldr并且没有列表的特殊方括号语法来分散我们的注意力，它会是什么样子可能会有所帮助。

-- List a is [a], Cons is (:) and Nil is []
data List a = Cons a (List a) | Nil

listFoldr :: (a -> b -> b) -> (b) -> List a -> b
listFoldr fCons fNil = g
  where
    g (Cons x xs) = fCons x (g xs)
    g Nil         = fNil

现在更容易看到其中的相似之处。额外的复杂之处在于Cons（即(:)）接受两个参数（因此，fCons也是如此）并且是递归的，需要调用g。此外，fNil当然不是一个真正的函数，因为它不接受任何参数。

递归数据类型上的折叠

就折叠而言，Weird是一个相当容易处理的数据类型。只有一个递归构造函数，它甚至没有嵌套在其他结构中。如果我们添加一个真正复杂的第五个构造函数会发生什么？

    Fifth [Weird a b] a (Weird a a, Maybe (Weird a b))

这是一个有效但又棘手的问题。通常，以下规则适用。

要提供给折叠的函数与对应构造函数具有相同数量的参数。
此类函数参数的类型与构造函数参数的类型匹配，除非构造函数是递归的（即，接受其自身类型的参数）。
如果构造函数是递归的，构造函数的任何递归参数将对应于折叠计算结果的类型的一个参数。^[1]
如果构造函数是递归的，则应将完整的折叠函数（递归地）应用于递归构造函数参数。
如果递归元素出现在另一个数据结构内部，则应使用该数据结构的适当映射函数将折叠函数应用于它。

因此，f5将具有以下类型

f5 :: [c] -> a -> (Weird a a, Maybe c) -> c

因为Fifth的类型是

Fifth :: [Weird a b] -> a -> (Weird a a, Maybe (Weird a b)) -> Weird a b

Fifth构造函数的g定义将是

    g (Fifth list x (waa, mc)) = f5 (map g list) x (waa, maybeMap g mc)
      where
        maybeMap f Nothing = Nothing
        maybeMap f (Just w) = Just (f w)

请注意，Weird a a部分没有发生任何奇怪的事情。没有调用g。怎么回事？这是递归，对吧？好吧，不完全是。Weird a a和Weird a b是不同的类型，因此它不是真正的递归。不能保证例如，f2将适用于类型为 'a' 的东西，而它期望一个类型为 'b' 的东西。它在某些情况下可能是真的，但在所有情况下都不可靠。

还要查看maybeMap的定义。验证它是否确实是一个映射函数，因为