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

Question

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

Answer 1

代数数据类型是由和和产品（不同的构造函数和具有多个字段的构造函数）组成的类型。抽象数据类型是一种数据类型，它的实现被定义的API抽象出来......通常在其实现上进行某种封装。

例如，优先级队列是一种抽象数据类型。在内存中，它可能被实现为一个数组，或者堆中的分配单元，或者C中的结构，或者作为莎士比亚的十四行诗。但是，您可以通过定义良好的界面对其进行抽象：push和pop。您可以优先将物品推入队列，并且可以随时弹出最高优先级的物品。 另一个例子是关联映射或字典，它可以用哈希，二叉搜索树或训练有素的海獭来实现。重要的是您定义了查找，插入和删除操作，这些操作对基础实现进行抽象。

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

Answer 2

我假设你指的是抽象类型和代数数据类型。 Scala中的大多数人参考了sum types的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中可以通过让在特质/抽象类未定义一个类型别名实现定义一个粒度表示。这个问题已经回答了here。

抽象类型通常用于隐藏有关组件内部结构的信息，因此基本上抽象出某个组件的具体类型。试图重写使用抽象类树表示给出了类似：

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的类型系统的功能（在这种情况下），同时代数数据类型仅仅是定义的形式复合类型并且独立于编程语言。