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

问题描述

我试图掌握这两个概念之间的关系.

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

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

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

根据 Haskell 维基:

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

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

参数多态是指当一个值的类型包含一个或多个(不受约束的)类型变量时，该值可以采用用具体类型替换这些变量所产生的任何类型.-- 来源

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

这里是 id :: a -> 的例子给出了一个:

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

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?

推荐答案

要实现的两件事.首先，您的示例 Tree 实际上是一种 参数类型，它是一种特殊的抽象类型.其次，参数多态可以是类型或函数.考虑到这两点，很明显抽象类型和参数多态都不是另一个的超集.但是，任何参数多态性属于类型的也是抽象类型.换句话说，抽象类型是参数化多态类型的超集(不知道他们是否真的这么叫).

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屋！