抽象数据类型和代数数据类型之间的区别

Question

有人可以告诉我,抽象数据类型和代数数据类型有什么区别？

Answer 1

代数数据类型是由和和产品组成的类型(不同的构造函数和具有多个字段的构造函数).抽象数据类型是一种数据类型,其实现由定义的API抽象化...通常对其实现进行某种封装.

例如,优先级队列是抽象数据类型.在内存中,它可以实现为数组,或堆上的已分配单元格,或C中的结构,或莎士比亚十四行诗.但是,您使用定义良好的界面对其进行抽象:push和pop.您可以优先将项目推入队列,并且可以随时弹出最高优先级项目.另一个例子是关联映射或字典,它可以用散列,二叉搜索树或训练有素的海獭来实现.重要的是您定义了对底层实现进行抽象的查找,插入和删除操作.

所以他们真的在谈论根本不同的事情.实际上,某些数据结构可以看作是作为代数数据类型实现的抽象数据类型!与Prelude中的commom链表抽象数据类型一样,它实现为[]代数数据类型.它提供的接口是consing和unconsing,但它实现为多个构造函数,其中一个具有多个字段 - 总和和产品.

Answer 2

我假设您指的是抽象类型和代数数据类型。Scala 中的大多数人将 ADT（代数数据类型）称为求和类型。[产品类型]也是代数数据类型。一个非常简单的例子是树（您实际上已经在之前的问题之一中定义了它）：

sealed abstract class Tree[+A]
case object Leaf extends Tree[Nothing]
case class Branch[A](left: Tree[A], right: Tree[A], value: A) extends Tree[A]

Scala 中的抽象类型可以通过在特征/抽象类中未定义类型别名来定义，以实现粒度表示。这个问题已经在这里得到解答。

抽象类型通常用于隐藏有关组件内部结构的信息，因此基本上是对某些组件的具体类型进行抽象。尝试使用抽象类型重写树表示会得到如下结果：

sealed trait Tree {
  type A
}
case object Leaf extends Tree {
  override type A = Nothing
}
case class Branch(left: Tree, right: Tree) {
  // This doesn't really make sense, we don't want to hide A!
  override type A = ???
}

最后，抽象类型更多的是 Scala 类型系统的一个特性（在本例中），而代数数据类型只是定义复合类型的一种形式，并且独立于编程语言。