Haskell中的抽象数据类型与参数多态性

Question

我正在努力理解这两个概念之间的关系。

首先考虑一个抽象数据类型的例子：

data Tree a = Nil 
            | Node { left  :: Tree a,
                     value :: a,
                     right :: Tree a }

根据 Haskell 维基百科：

这种类型是抽象的，因为它留下了一些结构方面的未定义之处，需要数据类型的用户提供。这是一种较弱的抽象数据类型。来源 现在考虑参数多态的概念：

参数多态是指值的类型包含一个或多个（无约束的）类型变量，使得该值可以采用任何由将这些变量替换为具体类型而产生的类型。-- 来源 这里给出了一个 id :: a -> a 的例子：

例如，函数 id :: a -> a 在其类型中包含一个无约束的类型变量 a。

问题：这两个概念之间的正式关系是什么？特别地，所有的抽象数据类型实例是否也是参数多态性的实例？反之呢？

- George

---

请注意，即使参考页面后面继续说，这也不是人们通常所说的“抽象数据类型”的意思。实际上，我觉得有些奇怪，有人决定以那种方式使用这个术语。正如维基页面所述，参数化数据类型确实需要参数多态性（至少某种形式），这样的类型只是参数化类型的一个示例。然而，“抽象数据类型”的通常含义确实与参数化多态性密切相关。 - Derek Elkins left SE

Answer 1

有两件事需要注意。首先，你的例子 Tree 实际上是一个参数化类型，这是一种特殊的抽象类型。其次，参数化多态可以是类型或函数。考虑到这两点，很明显抽象类型和参数化多态不是彼此的超集。然而，任何一个作为类型的参数化多态也是一个抽象类型。换句话说，抽象类型是参数化多态类型（不知道它们实际上是否被称为这样）的超集。

- Kwarrtz

Answer 2

Tree 是一个抽象数据类型，因为它没有指定任何关于如何实现它的细节。你如何向树中添加值？如何删除值？该类型仅定义了树的结构：它可以是空的或者是一个存储类型为 a 的值和引用另外两个树的节点。

参数多态与类型的结构或动态无关。相反，它指的是您实际上定义了一组相关类型。无论您有一个 Tree Int、Tree Char 还是 Tree (StateT (Int, Char) (MaybeT Float IO ()))，实现都将保持不变。

- chepner