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

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

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

根据哈斯克尔维基：

这种类型是抽象的，因为它留下它的结构不确定的某些方面，是由数据类型的用户提供。这是一种抽象数据类型的弱形式。 Source

现在考虑参数多态性的概念：

参数多态是指当一个值的类型包含一个或多个（无约束）型变量，使得该值可以采用通过用具体类型替换这些变量而产生的任何类型。 - Source

这里id :: a -> a给出一个例子：

例如，功能id :: a -> a包含一个不受约束的类型变量在类型

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

来源

2016-04-29 George

作为警告，这不是*人们通常所说的“抽象数据类型”这个词，因为即使被引用的页面也会这样说。事实上，我发现有人决定以这种方式使用这个词是很奇怪的。正如该wiki页面中给出的那样，参数化数据类型确实需要参数化多态（至少是某种类型），而这种类型仅仅是参数化类型的一个例子。尽管“抽象数据类型”的通常意义确实与参数多态具有密切关系。 –

要实现的两件事。首先，您的示例Tree实际上是参数类型，它是一种特殊的抽象类型。其次，参数多态性可以是类型或函数。考虑到这两点，显而易见的是，抽象类型和参数多态都不是另一类的超集。然而，类型的任何参数多态性也是一种抽象类型。换句话说，抽象类型是的参数多态类型的超集（不知道是否它们实际上被称为那个）。

来源

2016-04-30 00:01:18 Kwarrtz

-2

原因Tree是一种抽象数据类型，因为它没有指定任何关于的细节您如何实现它。你如何给树添加一个值？你如何删除一个值？该类型仅定义树的结构：它是空的或存储类型为a的值的节点以及对其他两个树的引用。

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

来源

2016-04-30 00:27:13 chepner

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

回答

相关问题