Haskell의 대수 데이터 유형

Haskell의 대수 데이터 유형

---

나는 Haskell의 모든 개념을 완전히 이해하려고 노력하고 있습니다.

대수 데이터 유형은 예를 들어 C # 및 Java와 같은 일반 유형과 어떤면에서 유사합니까? 그리고 그들은 어떻게 다릅니 까? 어쨌든 그들에 대해 그렇게 대수적인 것은 무엇입니까?

나는 범용 대수와 그 고리와 장에 익숙하지만 Haskell의 유형이 어떻게 작동하는지에 대한 모호한 아이디어 만 있습니다.

---

Haskell의 "Algebraic Data Types" 는 목록 데이터 유형의 간단한 예와 같이 제네릭에 대해 기술적으로 더 정확한 이름 인 완전한 매개 변수 다형성을 지원 합니다.

 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의 유형 시스템은 유형 매개 변수의 더 흥미로운 사용을 허용하지만 이것은 단순한 예일뿐입니다. "Algebraic Type"이름과 관련하여, 나는 그들이 그 이름이 붙여진 정확한 이유를 완전히 확신하지 못했지만 그것이 유형 시스템의 수학적 토대 때문이라고 생각했습니다. 나는 생각 난 더 이상 세부 사항을 기억하지 수 있도록 내가 대학을 탈출 한 이후, 그러나 그것은 몇 년이었다, 그 이유는 "생성자의 일련의 제품"인 ADT의 이론적 정의로 귀결있다.

[편집 : 내 어리석은 오류를 지적 해준 Chris Conway에게 감사합니다. ADT는 물론 합계 유형이며 필드의 제품 / 튜플을 제공하는 생성자입니다.]

---

Haskell의 대수 데이터 유형 은 범주 이론 의 초기 대수 에 해당하기 때문에 이름이 지정 되어 일부 법칙, 일부 연산 및 조작 할 기호를 제공합니다. 일반 데이터 구조를 설명하기 위해 대수 표기법을 사용할 수도 있습니다.

• +합계 유형을 나타냅니다 (예 : 분리형 공용체 Either).
• • 제품 유형 (예 : 구조체 또는 튜플)을 나타냅니다.
• X싱글 타입 (예를 들어 data X a = X a)
• 1 단위 유형 ()
• 그리고 μ최소한의 고정 점 (예를 들어 재귀 유형)의 경우, 일반적으로 암시.

추가 표기법 :

• X² ...에 대한 X•X

사실, 당신은이 표현 될 수있는 경우 하스켈의 데이터 유형은 일반입니다 (브렌트 Yorgey 다음) 말할 수있다 1, X, +, •, 및 최소 Fi를 고정 된 점.

이 표기법을 사용하면 많은 일반 데이터 구조를 간결하게 설명 할 수 있습니다.

• 단위 : data () = ()

  1

• 옵션 : data Maybe a = Nothing | Just a

  1 + X

• 기울기: data [a] = [] | a : [a]

  L = 1+X•L

• 이진 트리 : data BTree a = Empty | Node a (BTree a) (BTree a)

  B = 1 + X•B²

다른 작업은 보류됩니다 (참조에 나열된 Brent Yorgey의 논문에서 발췌) :

• 확장 : 수정 점을 펼치면 목록을 생각하는 데 도움이 될 수 있습니다. L = 1 + X + X² + X³ + ...(즉, 목록이 비어 있거나 하나의 요소 또는 두 개의 요소 또는 세 개 또는 ...가 있습니다.)

• 구성, ◦주어진 유형 F및 G구성 F ◦ G은 "G 구조로 만들어진 F 구조"를 구성 하는 유형입니다 (예 : 목록이있는 R = X • (L ◦ R)곳 L은 장미 나무입니다.

• 미분, 데이터 유형 D의 파생물 (D '로 제공됨)은 단일 "구멍", 즉 데이터를 포함하지 않는 구별 된 위치가있는 D- 구조 유형입니다. 그것은 미적분학의 미분과 동일한 규칙을 놀랍게 만족시킵니다.

  1′ = 0

  X′ = 1

  (F + G)′ = F' + G′

  (F • G)′ = F • G′ + F′ • G

  (F ◦ G)′ = (F′ ◦ G) • G′

---

참조 :

• Species and Functors and Types , Oh My !, Brent A. Yorgey, Haskell'10, 2010 년 9 월 30 일, 미국 메릴랜드 주 볼티모어
• 내 왼쪽의 광대, 오른쪽의 조커 (데이터 구조 해부) , Conor McBride POPL 2008

---

에서는 보편적 대수 대수 일부 요소 세트 구성 요소에 대한 요소를 매핑 및 일부 동작 (형태의 값들의 세트와 같은 각 세트 생각할).

예를 들어 "목록 요소"유형과 "목록"유형이 있다고 가정합니다. 연산으로 "목록"을 반환하는 인수가 0 개인 함수 인 "빈 목록"과 "목록 요소"와 "목록"이라는 두 개의 인수를 사용하여 "목록"을 생성하는 "단점"함수가 있습니다. ".

이 시점에서 두 가지 바람직하지 않은 일이 발생할 수 있으므로 설명에 맞는 많은 대수가 있습니다.

• "빈 목록"과 "소위"정크 "라고하는"단점 작업 "에서 만들 수없는"목록 "집합에 요소가있을 수 있습니다. 이것은 하늘에서 떨어진 일부 요소에서 시작하는 목록이거나 시작이없는 루프이거나 무한한 목록 일 수 있습니다.

• The results of "cons" applied to different arguments could be equal, e.g. consing an element to a non-empty list could be equal to the empty list. This is sometimes called "confusion".

An algebra which has neither of these undesirable properties is called initial, and this is the intended meaning of the abstract data type.

The name initial derives from the property that there is exactly one homomorphism from the initial algebra to any given algebra. Essentially you can evaluate the value of a list by applying the operations in the other algebra, and the result is well-defined.

It gets more complicated for polymorphic types ...

---

A simple reason why they are called algebraic; there are both sum (logical disjunction) and product (logical conjunction) types. A sum type is a discriminated union, e.g:

data Bool = False | True

A product type is a type with multiple parameters:

data Pair a b = Pair a b

In O'Caml "product" is made more explicit:

type 'a 'b pair = Pair of 'a * 'b

---

Haskell's datatypes are called "algebraic" because of their connection to categorical initial algebras. But that way lies madness.

@olliej: ADTs are actually "sum" types. Tuples are products.

---

@Timbo:

You are basically right about it being sort of like an abstract Tree class with three derived classes (Empty, Leaf, and Node), but you would also need to enforce the guarantee that some one using your Tree class can never add any new derived classes, since the strategy for using the Tree datat type is to write code that switches at runtime based on the type of each element in the tree (and adding new derived types would break existing code). You can sort of imagine this getting nasty in C# or C++, but in Haskell, ML, and OCaml, this is central to the language design and syntax so coding style supports it in a much more convenient manner, via pattern matching.

ADT (sum types) are also sort of like tagged unions or variant types in C or C++.

---

old question, but no one's mentioned nullability, which is an important aspect of Algebraic Data Types, perhaps the most important aspect. Since each value most be one of alternatives, exhaustive case-based pattern matching is possible.

---

For me, the concept of Haskell's algebraic data types always looked like polymorphism in OO-languages like C#.

Look at the example from http://en.wikipedia.org/wiki/Algebraic_data_types:

data Tree = Empty 
          | Leaf Int 
          | Node Tree Tree

This could be implemented in C# as a TreeNode base class, with a derived Leaf class and a derived TreeNodeWithChildren class, and if you want even a derived EmptyNode class.

(OK I know, nobody would ever do that, but at least you could do it.)

참고URL : https://stackoverflow.com/questions/16770/haskells-algebraic-data-types