haskell - 在 Haskell 中创建多态递归类型

Question

我正在尝试在 Haskell 中创建树类型。我使用这个简单的数据构造函数来存储一棵树，其中每个节点可以为空，可以是包含整数的叶子，也可以是包含整数且分支到其他两个叶子/节点的节点。这是我得到的:

module Tree ( Tree(Empty, Leaf, Node) ) where

data Tree = Empty
| Leaf Int
| Node Tree Int Tree
deriving(Eq, Ord, Show, Read)

效果很好，但我需要使 Tree 类型具有多态性。我尝试简单地将“Int”替换为“a”，但似乎不起作用。是否有另一个系统可以使这些类型具有多态性？

Answer 1

事实上，您可以为 Tree 提供一个类型参数，如 Alexander Poluektov 的示例所示。够简单的!但为什么要停在那里呢？我们还可以享受更多的乐趣。您可以在递归本身中使结构多态，而不只是具有多态数据的递归结构!

首先，抽象出树对自身的引用，就像抽象出对 Int 的引用一样，用新参数 t 替换递归引用。这给我们留下了这个相当模糊的数据结构:

data TNode t a = Empty
               | Leaf a
               | Node (t a) a (t a)
               deriving (Eq, Ord, Show, Read)

这里已被重命名为TNode，因为它不再是真正的树；只是一个简单的数据类型。现在，为了恢复原始递归并创建一棵树，我们扭转 TNode 并将其提供给自身:

newtype Tree a = Tree (TNode Tree a) deriving (Eq, Ord, Show, Read)

现在我们可以递归地使用这个树，尽管遗憾的是要付出一些额外的冗长的代价，如下所示:

Tree (Node (Tree Empty) 5 (Tree (Leaf 2)))

您可能会问，除了额外的打字之外，这还给我们带来了什么？简而言之，我们将基本树结构与其包含的数据以及构建和处理数据的方法分开，从而允许我们编写更通用的函数来处理某个方面或另一个方面。

例如，我们可以用额外的数据来装饰树，或者将额外的东西拼接到树中，而不会影响任何通用的树功能。假设我们想为树的每一部分命名:

newtype NameTree a = NameTree (String, TNode NameTree a) deriving (Eq, Ord, Show, Read)

另一方面，我们可以编写通用的树遍历逻辑:

toList f t = toList' f (f t) []
    where toList' f (Node t1 x t2) xs = toList' f (f t1) (x : toList' f (f t2) xs)
          toList' f (Leaf x) xs = x:xs
          toList' _ Empty xs = xs

给定一个从递归树中提取当前TNode的函数，我们可以在任何此类结构上使用它:

treeToList = toList (\(Tree t) -> t)
nameTreeToList = toList (\(NameTree (_, t)) -> t)

当然，这可能远远超出了您想要做的事情，但它很好地体现了 Haskell 允许(不，是鼓励)程序员创建多少多态性和通用代码。