62

我试图完全理解 Haskell 的所有概念。

代数数据类型在哪些方面类似于泛型类型，例如，在 C# 和 Java 中？它们有什么不同？他们到底有什么代数？

我熟悉通用代数及其环和域，但我对 Haskell 的类型如何工作只有一个模糊的概念。

4

8 回答 8

103
于 2011-05-06T21:20:55.787 回答
23

Haskell 中的“代数数据类型”支持完整的参数多态性，这是泛型在技术上更正确的名称，作为一个简单的示例列表数据类型：

 data List a = Cons a (List a) | Nil

等效（尽可能多，忽略非严格评估等）

 class List<a> {
     class Cons : List<a> {
         a head;
         List<a> tail;
     }
     class Nil : List<a> {}
 }

当然，Haskell 的类型系统允许更多......类型参数的有趣使用，但这只是一个简单的例子。关于“代数类型”的名称，老实说，我从来没有完全确定它们被命名的确切原因，但假设这是由于类型系统的数学基础。我相信原因归结为 ADT 的理论定义是“一组构造函数的产物”，但是我从大学毕业已经有几年了，所以我不再记得具体细节了。

[编辑：感谢 Chris Conway 指出我的愚蠢错误，ADT 当然是总和类型，构造函数提供产品/字段元组]

于 2008-08-19T19:46:24.647 回答
20

在通用代数中 ，代数由一些元素集（将每个集视为类型的值集）和一些将元素映射到元素的操作组成。

例如，假设您有一种“列表元素”类型和一种“列表”类型。作为操作，您有“空列表”，它是一个返回“列表”的 0 参数函数，以及一个“cons”函数，它接受两个参数，一个“列表元素”和一个“列表”，并生成一个“列表” ”。

在这一点上，有许多代数符合描述，因为可能会发生两种不希望的事情：

  • “list”集合中可能存在无法从“empty list”和“cons operation”构建的元素，即所谓的“junk”。这可能是从某个从天而降的元素开始的列表，或者是没有开始的循环，或者是无限列表。

  • 应用于不同参数的“cons”的结果可能是相等的，例如，将一个元素约束到一个非空列表可能等于空列表。这有时被称为“混乱”。

不具有这些不良属性的代数称为 initial，这是抽象数据类型的预期含义。

initial 的名字来源于这样一个性质，即从初始代数到任何给定的代数都只有一个同态。本质上，您可以通过应用其他代数中的操作来评估列表的值，并且结果是明确定义的。

多态类型变得更加复杂......

于 2009-03-13T21:23:55.290 回答
12

将它们称为代数的一个简单原因；有 sum（逻辑析取）和 product（逻辑合取）类型。sum 类型是有区别的联合，例如：

data Bool = False | True

产品类型是具有多个参数的类型：

data Pair a b = Pair a b

在 O'Caml 中，“产品”变得更加明确：

type 'a 'b pair = Pair of 'a * 'b
于 2009-03-16T01:28:07.177 回答
9

Haskell 的数据类型被称为“代数”，因为它们与分类初始代数有关。但这就是疯狂。

@olliej：ADT 实际上是“总和”类型。元组是产品。

于 2008-08-19T20:53:36.477 回答
3

@Timbo：

您基本上是正确的，它有点像具有三个派生类（Empty、Leaf 和 Node）的抽象 Tree 类，但您还需要强制保证使用您的 Tree 类的人永远不会添加任何新的派生类，因为使用 Tree 数据类型的策略是编写在运行时根据树中每个元素的类型切换的代码（并且添加新的派生类型会破坏现有代码）。你可以想象这在 C# 或 C++ 中变得令人讨厌，但在 Haskell、ML 和 OCaml 中，这是语言设计和语法的核心，因此编码风格通过模式匹配以更方便的方式支持它。

ADT（求和类型）也有点像C 或 C++ 中的标记联合或变体类型。

于 2008-08-30T07:21:17.733 回答
2

老问题，但没有人提到可空性，这是代数数据类型的一个重要方面，也许是最重要的方面。由于每个值都是备选值之一，因此可以进行详尽的基于大小写的模式匹配。

于 2008-12-19T22:49:23.787 回答
0

对我来说，Haskell 的代数数据类型的概念总是看起来像 C# 等面向对象语言中的多态性。

查看来自http://en.wikipedia.org/wiki/Algebraic_data_types的示例：

data Tree = Empty 
          | Leaf Int 
          | Node Tree Tree

这可以在 C# 中实现为 TreeNode 基类，具有派生的 Leaf 类和派生的 TreeNodeWithChildren 类，如果您甚至想要派生的 EmptyNode 类。

（好吧，我知道，没有人会那样做，但至少你可以做到。）

于 2008-08-19T19:58:06.400 回答