为什么“代数数据类型”使用“代数”在名字里？ [英] Why "Algebraic data type" use "Algebraic" in the name?

问题描述

当我学习Scala / Haskell时，我看到有一个代数数据类型的概念。我读过维基百科的解释，但我仍然有一个问题：

为什么它在名称中使用代数一词？它与代数有一些关系吗？

解决方案

考虑类型 Bool 。这种类型当然可以采用两种可能的值之一：True或False。

现在考虑$ b $

 数据EitherBool = Left Bool |右Bool 
  

这种类型可以使用多少个值？有4个： Left False，Left True，Right False，Right True 。怎么样

  data EitherBoolInt = Left Bool | Right Int8 
  

这里左分支有2个可能的值，右分支有2 ^ 8个。对于 EitherBoolInt ，总共可能有2 + 2 ^ 8个值。应该很容易看出，对于任何一组构造函数和类型，这种构造将为您提供一个数据类型，其中可能值的空间是每个构造函数可能值的 sum 的大小。出于这个原因，它被称为总和类型。

换而言之

  data BoolAndInt = BAndI Bool Int8 
  

或简单地

  type BoolAndInt =（Bool，Int）
  

这可能会有多少值？对于每个可能的Int8，都有两个BoolAndInts，总共为2 * 2 ^ 8 = 2 ^ 9个总值。可能值的总数是构造函数每个字段值的乘积，所以这称为 product 类型。

这个想法可以进一步扩展 - 例如，a-> b的函数是指数数据类型（参见代数数据类型的代数）。您甚至可以为数据类型的派生创建合理的概念。这甚至不是一个纯粹的理论思想 - 它是拉链功能性结构的基础。请参阅数据类型的派生类型是其单一上下文类型和拉链维基百科条目。

When I learn Scala/Haskell, I see there is a concept of Algebraic data type. I've read the explanation from the wikipedia, but I still have a question:

Why does it use the word "Algebraic" in its name? Does it have some relationship with "Algebraic"?

解决方案

Consider the type Bool. This type, of course, can take on one of two possible values: True or False.

Now consider

data EitherBool = Left Bool | Right Bool

How many values can this type take on? There are 4: Left False, Left True, Right False, Right True. How about

data EitherBoolInt = Left Bool | Right Int8

Here there are 2 possible values in the Left branch, and 2^8 in the Right branch. For a total of 2 + 2^8 possible values for EitherBoolInt. It should be easy to see that for any set of constructors and types, this kind of construction will give you a datatype with a space of possible values the size of the sum of the possible values of each individual constructor. For this reason, it's called a sum type.

Consider instead

data BoolAndInt = BAndI Bool Int8

or simply

type BoolAndInt = (Bool, Int)

How many values can this take on? For each possible Int8, there are two BoolAndInts, for a total of 2*2^8 = 2^9 total values. The total number of possible values is the product of the number of values of each field of the constructor, so this is called a product type.

This idea can be extended further -- for example, functions from a->b are an exponential datatype (see The Algebra of Algebraic Datatypes). You can even create a reasonable notion of the derivative of a datatype. This is not even a purely theoretical idea -- it's the basis for the functional construct of "zippers". See The Derivative of a Datatype is the Type of its One-Hole Contexts and The Wikipedia entry on zippers.

这篇关于为什么“代数数据类型”使用“代数”在名字里？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！