抽象数据类型与Haskell中的参数多态性 [英] Abstract Data Types vs. Parametric Polymorphism in Haskell

问题描述

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

 数据树a =无
 |节点{left :: Tree a，
 value :: a，
 right :: Tree a} 
  

根据Haskell wiki：

这种类型是抽象的，因为它的结构的某些方面未定义，由数据类型的用户提供。这是一种抽象数据类型的弱形式。 来源

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

参数多态一个值的类型包含一个或多个（不受约束的）类型变量，以便该值可以采用通过用具体类型替换这些变量而产生的任何类型。 - 来源

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

例如，函数 id :: a - > ;一个包含一个不受约束的类型变量a

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

解决方案

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

I am trying to get a grip on the relationship between these two concepts.

First consider an example of an Abstract Data Type:

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

According to Haskell wiki:

This type is abstract because it leaves some aspects of its structure undefined, to be provided by the user of the data type. This is a weak form of abstract data type. Source

Now consider the notion of parametric polymorphism:

Parametric polymorphism refers to when the type of a value contains one or more (unconstrained) type variables, so that the value may adopt any type that results from substituting those variables with concrete types. -- Source

Here an example of id :: a -> a is given:

For example, the function id :: a -> a contains an unconstrained type variable a in its type

Question: What is the formal relationship between these two concepts? In particular, are all instances of abstract data types also instances of parametric polymorphism? What about vice versa?

解决方案

Two things to realize. First, your example Tree is actually a parametric type, which is a special kind of abstract type. Second, parametric polymorphisms can be types or functions. With both of these things in mind, it is obvious that neither abstract types nor parametric polymorphisms are supersets of the other. However, any parametric polymorphism which is a type is also an abstract type. In otherwords, abstract types are a superset of parametrically polymorphic types (dunno if they're actually called that).

这篇关于抽象数据类型与Haskell中的参数多态性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！