Haskell의 대수 데이터 유형

Question

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

대수 데이터 유형은 C# 및 Java와 같은 일반 유형과 어떤 면에서 유사합니까?그리고 그것들은 어떻게 다른가요?어쨌든 그들에 대한 대수학적인 점은 무엇입니까?

나는 보편적인 대수학과 그 고리와 필드에 대해 잘 알고 있지만 Haskell의 유형이 어떻게 작동하는지에 대해서는 막연하게만 알고 있습니다.

Answer 1

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는 물론 필드의 곱/튜플을 제공하는 생성자인 합계 유형입니다.]

Answer 2

하스켈의 대수 데이터 유형 에 해당하기 때문에 그렇게 명명되었습니다. 초기 대수학 범주 이론에서는 조작할 몇 가지 법칙, 연산 및 기호를 제공합니다.정규 데이터 구조를 설명하기 위해 대수적 표기법을 사용할 수도 있습니다.

• + 합계 유형을 나타냅니다(분리된 합집합, 예: Either).
• • 제품 유형을 나타냅니다(예:구조체 또는 튜플)
• X 싱글톤 유형의 경우(예: data X a = X a)
• 1 유닛 유형에 대해 ()
• 그리고 μ 최소 고정점(예:재귀 유형), 일반적으로 암시적입니다.

몇 가지 추가 표기법을 사용하면 다음과 같습니다.

• X² ~을 위한 X•X

사실, (Brent Yorgey를 따라) 하스켈 데이터 유형이 다음과 같이 표현될 수 있다면 규칙적이라고 말할 수도 있습니다. 1, X, +, •, 그리고 최소 고정점.

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

• 단위: 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′

---

참고자료:

• 종, 기능자 및 유형, 오 마이!, 브렌트 A.Yorgey, Haskell'10, 2010년 9월 30일, 미국 메릴랜드 주 볼티모어
• 내 왼쪽은 광대, 오른쪽은 조커(데이터 구조 분석), 코너 맥브라이드 POPL 2008

Answer 3

~ 안에 보편적 대수학 안 대수학 일부 요소 세트 (각 세트를 유형 값 세트로 생각)와 요소를 요소에 매핑하는 일부 작업으로 구성됩니다.

예를 들어, "목록 요소"유형과 "목록"유형이 있다고 가정하십시오.연산으로서 "빈 목록"을 가지고 있으며, "목록"을 반환하는 0- 연락 함수와 "목록 요소"와 "목록", "목록"을 가져 오는 "cons"함수는 "목록을 작성합니다. ".

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

• "빈 목록"에서 구축 할 수없는 "목록"세트와 소위 "정크"에서 구축 할 수없는 요소가있을 수 있습니다.이것은 하늘에서 떨어진 일부 요소에서 시작하거나 시작이없는 루프 또는 무한한 목록 일 수 있습니다.

• 다른 인수에 적용되는 "단점"의 결과는 평등 할 수 있습니다.비어 있지 않은 목록에 요소를 고려하는 것은 빈 목록과 동일 할 수 있습니다.이것을 때때로 "혼란"이라고 합니다.

이러한 바람직하지 않은 특성을 모두 갖지 않는 대수를 다음과 같이 부릅니다.초기의, 이는 추상 데이터 유형의 의도된 의미입니다.

이름은 초기 대수에서 주어진 대수까지 정확히 하나의 동종이라는 속성에서 파생됩니다.기본적으로 다른 대수에서 작업을 적용하여 목록의 값을 평가할 수 있으며 결과는 잘 정의되어 있습니다.

다형성 유형의 경우 더 복잡해집니다 ...

Answer 4

대수라고 불리는 간단한 이유;합계(논리적 분리) 유형과 곱(논리적 결합) 유형이 모두 있습니다.합계 유형은 구별된 공용체입니다. 예:

data Bool = False | True

제품 유형은 여러 매개변수가 있는 유형입니다.

data Pair a b = Pair a b

O'Caml에서는 "제품"이 더욱 명확해졌습니다.

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

Answer 5

Haskell의 데이터 유형은 다음과 연결되어 있기 때문에 "대수적"이라고 불립니다. 범주형 초기 대수학.그러나 그 길에는 광기가 있습니다.

@olliej:ADT는 실제로 "합계" 유형입니다.튜플은 제품입니다.

Answer 6

@팀보:

기본적으로 세 가지 파생 클래스(Empty, Leaf 및 Node)가 있는 추상 Tree 클래스와 비슷하다는 점은 맞습니다. 그러나 Tree 클래스를 사용하는 일부 사용자가 새 파생 클래스를 추가할 수 없다는 보장도 적용해야 합니다. , Tree 데이터 유형을 사용하는 전략은 트리의 각 요소 유형에 따라 런타임에 전환하는 코드를 작성하는 것이기 때문입니다(새 파생 유형을 추가하면 기존 코드가 손상됨).C#이나 C++에서는 이것이 불쾌하다고 상상할 수 있지만 Haskell, ML 및 OCaml에서는 이것이 언어 디자인과 구문의 핵심이므로 코딩 스타일은 패턴 일치를 통해 훨씬 더 편리한 방식으로 이를 지원합니다.

ADT(합계 유형)도 다음과 같습니다. 태그된 노동조합 또는 변형 유형 C 또는 C++에서.

Answer 7

오래된 질문이지만 Null 허용 여부는 아무도 언급하지 않았습니다. 이는 대수 데이터 유형의 중요한 측면이자 아마도 가장 중요한 측면일 것입니다.각 값은 대부분 대안 중 하나이므로 철저한 사례 기반 패턴 일치가 가능합니다.

Answer 8

나에게 Haskell의 대수 데이터 유형 개념은 항상 C#과 같은 OO 언어의 다형성처럼 보였습니다.

의 예를 보세요 http://en.wikipedia.org/wiki/Algebraic_data_types:

data Tree = Empty 
          | Leaf Int 
          | Node Tree Tree

이는 C#에서 파생된 Leaf 클래스와 파생된 TreeNodeWithChildren 클래스를 사용하여 TreeNode 기본 클래스로 구현될 수 있으며, 원하는 경우 파생된 EmptyNode 클래스도 구현할 수 있습니다.

(알겠습니다. 누구도 그렇게 하지 않을 것입니다. 하지만 적어도 당신은 그렇게 할 수 있습니다.)