[haskell] 대수 데이터 유형의 대수를 남용-왜 이것이 작동합니까?

Program / 글쓴이

대수 데이터 유형에 대한 ‘대수’표현은 수학 배경 지식이있는 사람에게 매우 암시 적으로 보입니다. 내가 의미하는 바를 설명하려고 노력하겠습니다.

기본 유형을 정의한 경우

  • 생성물 •
  • 노동 조합 +
  • 하나씩 일어나는 것 X
  • 단위 1

그리고 속기를 사용 X²하기위한 X•X및 2X대한 X+X등등, 우리는 연결리스트를 예에 대한 대수식을 정의 할 수 있습니다

data List a = Nil | Cons a (List a) ↔ L = 1 + X • L

이진 트리 :

data Tree a = Nil | Branch a (Tree a) (Tree a) ↔ T = 1 + X • T²

자, 수학자로 내 첫 번째 본능이 표현 견과류 가서에 대한 해결하려고하는 것입니다 L및 T. 반복되는 대체를 통해이 작업을 수행 할 수는 있지만 끔찍하게 표기법을 남용하고 마음대로 재 배열 할 수있는 척하는 것이 훨씬 쉽습니다. 예를 들어, 링크 된 목록의 경우 :

L = 1 + X • L

(1 - X) • L = 1

L = 1 / (1 - X) = 1 + X + X² + X³ + ...

여기서 파워 시리즈 확장을 1 / (1 - X)완전히 정당화되지 않은 방식으로 사용하여 흥미로운 결과를 도출했습니다. 즉, L유형이이거나 Nil1 요소를 포함하거나 2 요소 또는 3을 포함한다는 것입니다.

이진 트리에 대해 그렇게하면 더 흥미로워집니다.

T = 1 + X • T²

X • T² - T + 1 = 0

T = (1 - √(1 - 4 • X)) / (2 • X)

T = 1 + X + 2 • X² + 5 • X³ + 14 • X⁴ + ...

다시 파워 시리즈 확장 ( Wolfram Alpha로 수행 )을 사용합니다. 이것은 하나의 요소가있는 2 개의 이진 트리, 두 개의 요소가있는 2 개의 이진 트리 (두 번째 요소가 왼쪽 또는 오른쪽 분기에있을 수 있음), 3 개의 요소가있는 5 개의 이진 트리가 있다는 명백한 사실을 나타냅니다. .

내 질문은-내가 여기서 뭐하는거야? 이러한 연산은 정당화되지 않은 것처럼 보이지만 (어쨌든 대수 데이터 유형의 제곱근은 무엇입니까?) 합리적인 결과를 초래합니다. 두 가지 대수적 데이터 유형의 몫은 컴퓨터 과학에서 의미가 있습니까? 아니면 표기법이 아닌가?

그리고 아마도 더 흥미롭게도 이러한 아이디어를 확장 할 수 있습니까? 예를 들어 유형에 대한 임의의 함수를 허용하거나 유형에 거듭 제곱 표현이 필요한 유형의 대수 이론이 있습니까? 함수 클래스를 정의 할 수 있다면 함수 구성에 의미가 있습니까?

답변

면책 조항 : this를 설명 할 때 많은 것이 실제로 제대로 작동하지 않으므로 간단하게하기 위해 그것을 무시할 것입니다.

몇 가지 초기 사항 :

  • 여기서 “연합 (Union)”은 A + B에 가장 적합한 용어가 아닐 수 있습니다 . 두 유형의 유형이 동일하더라도 두 측면이 구별되기 때문에 특히 두 유형 의 분리 된 결합 입니다. 가치가있는 것에 대해,보다 일반적인 용어는 단순히 “sum type”입니다.

  • 싱글 톤 유형은 사실상 모든 단위 유형입니다. 그것들은 대수 조작 하에서 동일하게 동작하며, 더 중요한 것은 존재하는 정보의 양이 여전히 보존된다는 것입니다.

  • 아마도 제로 타입을 원할 것입니다. Haskell은 다음과 같이 제공합니다 Void. 유형이 1 인 값이 하나 인 것처럼 유형이 0 인 값은 없습니다.

여기에는 여전히 하나의 주요 작업이 누락되었지만 잠시 후 다시 설명하겠습니다.

알다시피, Haskell은 범주 이론에서 개념을 빌리는 경향이 있으며 위의 모든 내용은 다음과 같이 매우 간단합니다.

  • 에서 A와 B 개체 감안 Hask 개의 돌기를 허용 형 (동형까지) 그 부 생성물 × B가 독특 FST × B → A와 : SND 하십시오 × B → B, 어떤 타입 C와 기능 주어진 F를 : C → A, g : C → B 페어링 f &&& g : C → A × B를 정의하여 fst∘ (f && g) = f 와 같이 g에 대해서도 정의 할 수 있습니다 . 파라 메트릭은 보편적 인 속성을 자동으로 보장하며, 미묘한 이름을 선택하면 아이디어를 얻게됩니다. 그런데 (&&&)연산자는에 정의되어 Control.Arrow있습니다.

  • 위의 이중은 주입 inl : A → A + B 및 inr : B → A + B가있는 보조 제품 A + B입니다. 여기서 C 유형과 기능 f : A → C, g : B → C 가 주어지면 코 페어링 정의 f ||| g : A + B → C로 명백한 동등성이 유지됩니다. 다시 말하지만, 파라 메트릭은 까다로운 부분을 자동으로 보장합니다. 이 경우 표준 주사는 간단 Left하며 Right코 페어링은 기능 either입니다.

제품 및 합계 유형의 많은 속성이 위로부터 파생 될 수 있습니다. 단일 유형은 Hask 의 터미널 객체이고 빈 유형은 초기 객체입니다.

(A)에, 상기 누락 된 동작으로 되돌아 데카르트 닫힌 범주 는이 지수 개체 대응 카테고리의 화살표로한다. 우리의 화살표는 함수이고, 우리의 객체는 종류가 *있는 유형이며, 유형 은 대수적 유형의 조작에서 A -> B실제로 B A 로 작동 합니다. 이것이 왜 유지되어야하는지 분명하지 않은 경우 type을 고려하십시오 Bool -> A. 두 개의 가능한 입력 만 있으면 해당 유형의 함수는 유형의 두 값 A, 즉에 대해 동형 (A, A)입니다. 위해 Maybe Bool -> A우리는 세 가지 입력 등이있다. 또한, 대수 표기법을 사용하기 위해 위의 코 페어링 정의를 바꾸면 C A × C B = CA + B 라는 ID를 얻습니다..

에 관해서는 왜 특히 멱급수 확장의 사용이 정당화 이유 – – 위의 많은 종류의 “주민”(즉, 해당 유형을 가진 고유 한 값) 순서를 의미합니다이 모든 말이 대수적 행동을 보여줍니다. 해당 관점을 명시 적으로 만들려면 :

  • 제품 유형 (A, B)은 A및 B에서 각각 독립적으로 취한 값을 나타냅니다 . 따라서 모든 고정 값 에 대해 주민마다 a :: A하나의 유형 값 (A, B)이 B있습니다. 이것은 물론 직교 곱이며, 제품 유형의 주민 수는 요인의 주민 수의 곱입니다.

  • 합계 유형 Either A B은 왼쪽 및 오른쪽 분기가 구분 된 A또는 의 값을 나타냅니다 B. 앞에서 언급했듯이, 이것은 분리 된 연합이며 합계 유형의 주민 수는 소환 자의 주민 수의 합입니다.

  • 지수 형이 B -> A타입의 값으로 매핑 나타내는 B유형의 값을 A. 고정 인수의 b :: B경우 모든 값을 A할당 할 수 있습니다. 유형의 값 B -> A의 몇 장 같은 제품에 상당 각 입력에 대한 하나의 이러한 매핑 픽업 A로 B주민을 가지며, 따라서 지수화.

처음에는 유형을 세트로 취급하려는 유혹이 있지만 실제로는 문맥에서 잘 작동하지 않습니다. 우리는 표준 세트 조합이 아닌 분리 된 조합을 가지고 있지만 교차 또는 다른 많은 세트 작업에 대한 명확한 해석은 없으며 일반적으로 집합 멤버 자격에 신경 쓰지 마십시오 (유형 검사기에게 맡김).

반면에 위의 구성은 주민 수 를 계산 하는 데 많은 시간을 소비 하며 유형의 가능한 값을 열거 하는 것이 유용한 개념입니다. 그것은 우리를 열거 형 조합론으로 빠르게 이끌어 주며 , 당신이 링크 된 Wikipedia 기사를 참조하면 가장 먼저하는 것 중 하나는 제품 및 합계 유형과 정확히 같은 의미로 “쌍”과 “연합”을 정의한다는 것입니다. 함수를 생성 한 다음 정확히 동일한 기술을 사용하여 Haskell의 목록과 동일한 “시퀀스”에 대해 동일하게 수행합니다.

편집 : 아, 여기 요점을 눈에 띄게 보여주는 빠른 보너스가 있습니다. 당신은 주석에서 나무 유형에 T = 1 + T^2대해 정체성을 도출 할 수 있다고 언급했습니다 T^6 = 1. 그러나, T^7 = T 하지 홀드를하고, 나무와 나무의 일곱 튜플 사이에 전단 사 함수는 직접 참조를 구성 할 수있다 Andreas Blass의 “7 개의 나무” .

편집 × 2 : 다른 답변에서 언급 한 “유형의 파생”구성의 주제에 대해 분할 개념 및 기타 흥미로운 개념을 포함하여 아이디어를 더 발전 시킨 동일한 저자 의이 논문을 즐길 수도 있습니다 .

답변

이진 트리는 T=1+XT^2유형의 반올림 에서 방정식으로 정의됩니다 . 구성에 T=(1-sqrt(1-4X))/(2X)의해 복소수의 반올림에서 동일한 방정식으로 정의됩니다. 따라서 우리가 같은 종류의 대수적 구조에서 같은 방정식을 풀고 있다는 사실을 감안할 때 실제로 우리가 몇 가지 유사점을 본다는 것은 놀라운 일이 아닙니다.

잡는 것은 우리가 복소수의 반올림에서 다항식에 대해 추론 할 때 일반적으로 복소수가 고리 또는 필드를 형성한다는 사실을 사용하므로 반올림에 적용되지 않는 빼기와 같은 연산을 사용하여 자신을 찾습니다. 그러나 방정식의 양변에서 취소 할 수있는 규칙이있는 경우 종종 인수에서 빼기를 제거 할 수 있습니다. 이것은 Fiore와 Leinster에 의해 입증 된 것으로 링에 대한 많은 논증이 반반 지로 전달 될 수 있음을 보여줍니다.

이것은 링에 대한 많은 수학적 지식이 유형으로 확실하게 전달 될 수 있음을 의미합니다. 결과적으로 복소수 또는 거듭 제곱과 관련된 일부 주장 (정식 거듭 제곱의 고리에있는)은 완전히 엄격한 방식으로 유형에 이어질 수 있습니다.

그러나 이것보다 더 많은 이야기가 있습니다. 두 개의 전력 계열이 동일하다는 것을 보여줌으로써 두 가지 유형이 동일하다는 것을 증명하는 것은 한 가지입니다. 그러나 전력 계열의 항을 검사하여 유형에 대한 정보를 추론 할 수도 있습니다. 나는 공식적인 진술이 무엇인지 확신하지 못한다. (I 브렌트 Yorgey의 추천 종이 에 조합 종 밀접한 관련이 있지만, 종이있어 어떤 작업 하지 유형과 동일.)

내가 완전히 불면하는 것은 당신이 발견 한 것이 미적분으로 확장 될 수 있다는 것입니다. 미적분학에 대한 이론은 유형의 반고리로 넘어갈 수 있습니다. 사실, 유한 한 차이에 대한 논증조차도 전이 될 수 있으며 수치 해석의 고전 이론은 유형 이론에 대한 해석이 있음을 알 수 있습니다.

즐기세요!

답변

당신이하고있는 모든 것은 재발 관계를 확장하는 것 같습니다.

L = 1 + X • L
L = 1 + X • (1 + X • (1 + X • (1 + X • ...)))
  = 1 + X + X^2 + X^3 + X^4 ...

T = 1 + X • T^2
L = 1 + X • (1 + X • (1 + X • (1 + X • ...^2)^2)^2)^2
  = 1 + X + 2 • X^2 + 5 • X^3 + 14 • X^4 + ...

그리고 유형에 대한 연산 규칙이 산술 연산 규칙처럼 작동하기 때문에 대수적 수단을 사용하여 재발 관계를 확장하는 방법을 알 수 있습니다 (확실하지 않기 때문에).

답변

나는 완전한 대답을 얻지 못했지만 이러한 조작은 ‘그냥 작동하는 경향이 있습니다. 관련 논문은 Fiore와 Leinster의 Complex Numbers 인 카테고리의 객체 일 수 있습니다 . 관련 주제에 대한 sigfpe의 블로그 를 읽는 동안 그 논문을 발견했습니다 . 그 블로그의 나머지 부분은 비슷한 아이디어를위한 금광이며 점검 할 가치가 있습니다!

또한 데이터 유형을 차별화 할 수 있습니다-데이터 유형에 적합한 지퍼를 얻을 수 있습니다!

답변

의사 소통 과정 대수 (ACP)는 프로세스에 대해 비슷한 종류의 표현을 다룹니다. 또한 중립 요소와 관련하여 선택 및 시퀀스를위한 연산자로 더하기 및 곱셈을 제공합니다. 이를 기반으로 병렬 처리 및 중단과 같은 다른 구성에 대한 연산자가 있습니다. http://en.wikipedia.org/wiki/Algebra_of_Communicating_Processes를 참조하십시오 . “프로세스 대수의 간략한 역사”라는 온라인 문서도 있습니다.

ACP로 프로그래밍 언어를 확장하고 있습니다. 지난 4 월 저는 Scala Days 2012에서 http://code.google.com/p/subscript/ 에서 연구 논문을 발표했습니다 .

컨퍼런스에서 백의 병렬 재귀 사양을 실행하는 디버거를 시연했습니다.

백 = A; (가방 & a)

여기서 A와 입력 및 출력 동작을위한 스탠드; 세미콜론과 앰퍼샌드는 시퀀스와 병렬 처리를 나타냅니다. 이전 링크에서 도달 할 수있는 SkillsMatter의 비디오를 참조하십시오.

가방 사양에 비해

L = 1 + X • L

될 것이다

B = 1 + X & B

ACP는 공리를 사용하여 선택 및 순서 측면에서 병렬 처리를 정의합니다. Wikipedia 기사를 참조하십시오. 가방 비유가 무엇인지 궁금합니다.

L = 1 / (1-X)

ACP 스타일 프로그래밍은 텍스트 파서 및 GUI 컨트롤러에 편리합니다. 같은 사양

searchCommand = clicked (searchButton) + 키 (Enter)

cancelCommand = 클릭 (취소 버튼) + 키 (이스케이프)

“클릭”과 “키”를 암시 적으로 만들어서 (스칼라가 함수로 허용하는 것과 같이)보다 간결하게 기록 될 수 있습니다. 따라서 다음과 같이 쓸 수 있습니다.

searchCommand = searchButton + Enter

cancelCommand = cancelButton + 이스케이프

오른쪽에는 이제 프로세스가 아니라 데이터 인 피연산자가 포함됩니다. 이 수준에서는 어떤 암시 적 개선이 이러한 피연산자를 프로세스로 변환 할 것인지 알 필요가 없습니다. 그들은 반드시 입력 행동으로 다듬을 필요는 없다. 출력 동작은 예를 들어 테스트 로봇의 사양에도 적용됩니다.

프로세스는 이런 방식으로 데이터를 동반자로 가져옵니다. 따라서 나는 “항목 대수학”이라는 용어를 사용합니다.

답변

유형을 가진 미적분학 및 Maclaurin 시리즈

여기에 또 다른 사소한 추가 사항이 있습니다-시리즈 확장의 계수가 왜 작동 해야하는지에 대한 조합 통찰력, 특히 미적분학 의 Taylor-Maclaurin 접근법을 사용하여 도출 할 수있는 시리즈에 중점을 둡니다 . 주의 : 조작 된 목록 유형에 대한 예제 시리즈 확장은 Maclaurin 시리즈입니다.

다른 답변과 의견은 대수 유형 표현 (합계, 곱 및 지수)의 동작을 다루므로이 답변은 그 세부 사항을 없애고 ‘미적분학’유형에 중점을 둡니다.

이 답변에서 쉼표가 거꾸로 들리는 것을 볼 수 있습니다. 두 가지 이유가 있습니다.

  • 우리는 한 도메인에서 다른 도메인의 엔티티로 해석을 제공하는 사업에 있으며 이러한 외국 개념을 이런 식으로 구분하는 것이 적절 해 보입니다.
  • 어떤 개념은 좀 더 엄격하게 공식화 될 수 있지만 모양과 아이디어는 세부 사항보다 더 중요해 보인다 (쓰기 공간이 더 적게 걸린다).

Maclaurin 시리즈의 정의

Maclaurin은 시리즈 함수의은 f : ℝ → ℝ으로 정의되고

f(0) + f'(0)X + (1/2)f''(0)X² + ... + (1/n!)f⁽ⁿ⁾(0)Xⁿ + ...

여기서는 f⁽ⁿ⁾의 n도함수를 의미합니다 f.

유형으로 해석 된 Maclaurin 시리즈를 이해하려면 유형 컨텍스트에서 세 가지를 해석하는 방법을 이해해야합니다.

  • (아마도 다중) 유도체
  • 에 함수를 적용 0
  • 같은 용어 (1/n!)

그리고 분석으로부터의 이러한 개념은 유형 세계에서 적절한 대응 물을 가지고 있음이 밝혀졌습니다.

‘적합한 대응 자’란 무엇을 의미합니까? 그것은 동형의 풍미를 가져야한다-만약 우리가 양방향으로 진실을 보존 할 수 있다면, 한 맥락에서 도출 될 수있는 사실은 다른쪽으로 옮겨 질 수있다.

유형 미적분

타입 표현의 미분은 무엇을 의미합니까? 크고 잘 동작하는 ( ‘차별 가능한’) 클래스 식과 펑터 클래스에는 적절한 해석이 될 정도로 자연스럽게 작동하는 자연 연산이 있습니다.

펀치 라인을 망치기 위해 차별화와 유사한 작업은 ‘한 홀 컨텍스트’를 만드는 것입니다. 이것은 이 특정 지점에서 더 확장 할 수있는 훌륭한 장소이지만 원홀 컨텍스트 ( da/dx) 의 기본 개념은 특정 유형 ( x) 의 단일 하위 항목을 (유형 a) 용어에서 추출하여 보존 한 결과를 나타냅니다. 하위 항목의 원래 위치를 결정하는 데 필요한 정보를 포함한 기타 모든 정보 예를 들어, 목록에 대한 단일 홀 컨텍스트를 나타내는 한 가지 방법은 두 개의 목록을 사용하는 것입니다. 하나는 추출 된 항목 앞에 오는 항목과 뒤에 오는 항목에 대한 것입니다.

차별화를 통해이 작업을 식별하는 동기는 다음 관찰에서 비롯됩니다. 우리는 hole of type 유형에 da/dx대한 one-hole 컨텍스트의 유형을 의미합니다 .ax

d1/dx = 0
dx/dx = 1
d(a + b)/dx = da/dx + db/dx
d(a × b)/dx = a × db/dx + b × da/dx
d(g(f(x))/dx = d(g(y))/dy[f(x)/a] × df(x)/dx

여기에, 1그리고 0각각 정확히 하나의 정확히 제로 주민를 가지는 형태를 나타내며, +그리고 ×평소와 같이 합 및 제품 유형을 나타냅니다. f및 g입력 기능을 나타내고, 또는 식 형성기를 입력하기 위해 사용되며, [f(x)/a]대체 수단의 조작 f(x)각에 대한 a위 식을.

이것은 point-free 스타일로 작성 될 수 있으며, f'function 유형의 미분 함수를 의미합니다 f.

(x ↦ 1)' = x ↦ 0
(x ↦ x)' = x ↦ 1
(f + g)' = f' + g'
(f × g)' = f × g' + g × f'
(g ∘ f)' = (g' ∘ f) × f'

바람직 할 수 있습니다.

NB 유형과 펑터의 동형 변형 클래스를 사용하여 미분을 정의하면 평등을 엄격하고 정확하게 만들 수 있습니다.

이제 우리는 특히 대수, 곱셈 및 구성의 대수 연산 (합계, 곱 및 체인 규칙이라고 함)과 관련된 미적분학 규칙이 ‘구멍 만들기’연산에 정확하게 반영됨을 알 수 있습니다. 또한, 상수 표현이나 용어 x자체 에서 ‘구멍 만들기’의 기본 사례는 또한 미분처럼 행동하므로, 유도를 통해 모든 대수 유형 표현식에 대해 미분과 같은 행동을 얻습니다.

이제 우리는 차별화를 해석 할 수 있습니다 n. 타입 표현의 ‘파생’ dⁿe/dxⁿ은 무엇을 의미합니까? n-place 컨텍스트를 나타내는 유형입니다. 유형의 용어로 ‘채울 때’는 n항을 x생성합니다 e. (1/n!)나중에 ‘ ‘ 와 관련된 또 다른 주요 관찰 사항이 있습니다.

유형 functor의 고정 부분 : 0에 함수 적용

우리 0는 타입 월드에서 이미 멤버가없는 빈 타입에 대한 해석을 가지고 있습니다 . 조합 관점에서 유형 기능을 적용한다는 것은 무엇을 의미합니까? 좀 더 구체적으로 말하면, f유형 함수라고 가정 하면 어떤 f(0)모양입니까? 글쎄, 우리는 확실히 어떤 유형의 접근도 할 수 0없기 때문에, 어떤 구성도 f(x)필요 하지 않다 x. 남은 것은 부재시 액세스 할 수있는 용어이며,이를 유형의 ‘불변’또는 ‘일정한’부분이라고 부를 수 있습니다.

명백한 예를 들어, Maybe대수적으로 표현할 수있는 functor를 사용하십시오 x ↦ 1 + x. 우리가 이것을 적용 할 때 0, 우리가 얻을 1 + 0– 그것은 단지처럼 1: 유일하게 가능한 값은이다 None값. 목록의 경우와 마찬가지로 빈 목록에 해당하는 용어 만 얻습니다.

다시 가져 와서 유형 f(0)을 숫자로 해석하면 다음에 액세스하지 않고 얻을 수있는 유형의 용어 수 (임의의 수 ) 의 수로 간주 할 수 있습니다 . 즉, ‘빈 같은’용어 수 .f(x)xx

종합 : Maclaurin 시리즈의 완전한 해석

(1/n!)유형 에 대한 적절한 직접 해석을 생각할 수 없습니다 .

우리가 고려하는 경우,하지만, 유형 f⁽ⁿ⁾(0)위의 빛, 우리는의 유형으로 해석 될 수있는 참조 n유형의 임기의 자리 표시 컨텍스트 에 이미 포함하지 않는 우리가 그들에게 ‘통합’때, – 번 결과 항은 정확히 s, 더 이상, 더 이상을 갖지 않습니다. 그런 다음 (Maclaurin 시리즈의 계수에서와 같이) 숫자로 유형 을 해석하는 것은 빈 컨텍스트가 얼마나 많은지를 계산 한 것입니다 . 우리는 거의 다왔다!f(x) xn n xf⁽ⁿ⁾(0)fn

그러나 어디에서 끝나는가 (1/n!)? ‘차등화’유형의 프로세스를 조사하면 여러 번 적용될 때 하위 용어가 추출되는 ‘순서’를 유지한다는 것을 알 수 있습니다. 예를 들어, (x₀, x₁)유형 의 용어 x × x와 ‘구멍 만들기’작업을 두 번 고려하십시오. 우리는 두 시퀀스를 얻는다

(x₀, x₁)  ↝  (_₀, x₁)  ↝  (_₀, _₁)
(x₀, x₁)  ↝  (x₀, _₀)  ↝  (_₁, _₀)
(where _ represents a 'hole')

둘 다 같은 용어에서 나왔지만 2! = 2순서를 유지하면서 두 요소에서 두 요소를 취하는 방법이 있기 때문 입니다. 일반적으로, 거기에n! 걸릴 수있는 방법 n에서 요소 n. 그래서이 펑터 유형의 구성의 수를 카운트 얻기 위해 n요소를, 우리는 형 계산해야 f⁽ⁿ⁾(0)으로 나눈다 n!, 정확히 에 Maclaurin 시리즈의 계수로.

따라서 나누는 n!것은 그 자체로 해석 할 수있는 것으로 밝혀졌습니다.

최종 생각 : ‘재귀 적’정의 및 분석

먼저 몇 가지 관찰 사항 :

  • 함수 f : ℝ → ℝ에 미분이있는 경우이 미분은 고유합니다
  • 유사하게, 함수 f : ℝ → ℝ가 분석적이면, 정확히 하나의 대응 다항식 계열이 있습니다.

우리는 사슬 규칙을 가지고 있기 때문에 타입 파생어를 동형 클래스로 공식화하면 암시 적 차별화를 사용할 수 있습니다 . 그러나 암묵적인 차별화에는 빼기 나 나누기와 같은 외계인의 기동이 필요하지 않습니다! 이를 사용하여 재귀 유형 정의를 분석 할 수 있습니다. 귀하의 목록 예를 들어, 우리는

L(X) ≅ 1 + X × L(X)
L'(X) = X × L'(X) + L(X)

그리고 우리는 평가할 수 있습니다

L'(0) = L(0) = 1

X¹Maclaurin 시리즈 의 계수를 구합니다 .

그러나 우리는 이러한 표현이 실제로 ‘차별적’이라는 확신을 가지고 있기 때문에, 암시 적으로 만, 파생물이 확실히 고유 한 함수 correspond → ℝ와의 대응 관계를 갖기 때문에 ‘ 잘못된 ‘작업, 결과가 유효합니다.

이제 유사하게, observation → ℝ 함수와의 대응 성 (동형화?)으로 인해 두 번째 관측치를 사용하기 위해 함수 에 Maclaurin 시리즈 가 있다고 만족 한다면 어떤 시리즈를 찾을 수 있다면 위에서 설명한 원칙을 모두 엄격하게 적용 할 수 있습니다.

함수 구성에 대한 귀하의 질문에 대해서는 체인 규칙이 부분 답변을 제공한다고 가정합니다.

이것이 얼마나 많은 Haskell 스타일 ADT에 적용되는지는 확실하지 않지만 전부는 아니지만 많은 것 같습니다. 나는이 사실에 대한 놀라운 증거를 발견했지만,이 한계는 그것을 포함하기에는 너무 작습니다 …

자, 이것은 확실히 여기서 일어나는 일을 해결하는 한 가지 방법 일 뿐이며 다른 많은 방법이있을 것입니다.

요약 : TL; DR

  • ‘차등화’유형은 ‘ 구멍 만들기 ‘에 해당합니다 .
  • functor를 적용하여 해당 functor 0의 ‘빈’조건 을 얻습니다.
  • 따라서 Maclaurin power series는 (어떤) functor 유형의 멤버 수를 특정 수의 요소로 열거하는 것과 엄격하게 일치합니다.
  • 암시 적 차별화 는 이것을 더 수밀하게 만듭니다.
  • 파생 상품의 독창성과 파워 시리즈의 독창성은 세부 사항을 퍼지 할 수 있으며 작동합니다.

답변

종속 유형 이론 및 ‘임의’유형 기능

이 질문에 대한 나의 첫 번째 대답은 개념이 높고 세부 사항이 낮았으며 ‘무슨 일이 일어나고 있습니까?’라는 하위 질문에 반영되었습니다. 이 답변은 동일하지만 ‘임의의 유형 함수를 얻을 수 있습니까?’라는 하위 질문에 중점을 둡니다.

합 생성물의 대수 조작을 한 확장 시퀀스 (또는 도메인을 통해 함수보다 일반적으로, 합 및 제품)의 합 생성물을 나타내는 소위 “대규모 사업자의 일반적 기록 Σ하고 Π각각을. 시그마 표기법을 참조하십시오 .

그래서 합계

a₀ + a₁X + a₂X² + ...

쓰여질지도 모른다

Σ[i ∈ ℕ]aᵢXⁱ

여기서 a실수의 일부 순서는, 예를 들면. 제품이 Π대신 유사하게 표시 됩니다 Σ.

멀리서 보면 이런 종류의 표현은 ‘임의’기능과 비슷합니다 X. 우리는 물론 표현 가능한 시리즈 및 관련 분석 기능으로 제한됩니다. 이것은 유형 이론의 표현에 대한 후보입니까? 명확히!

이러한 표현들을 즉각적으로 표현하는 유형 이론의 종류는 ‘종속적 인’유형 이론의 종류입니다 : 종속 유형을 가진 이론. 당연히 용어에 따라, 유형 함수 및 유형 수량 화가있는 Haskell과 같은 언어, 유형에 따라 용어 및 유형이 있습니다. 종속 설정에서는 용어에 따라 유형이 추가로 있습니다. Haskell은 종속 유형 언어가 아니지만 , 언어를 약간 고문함으로써 종속 유형의 많은 기능을 시뮬레이션 할 수 있습니다 .

카레 하워드 및 종속 유형

‘Curry-Howard isomorphism’은 단순한 유형의 람다 미적분학의 용어와 유형 판단 규칙이 직감적 인 제안 논리에 적용된 자연 공제 (Gentzen에 의해 공식화 된)와 정확히 일치한다는 관찰로 인생을 시작했습니다. , 및 두 가지가 독립적으로 발명 / 발견되었지만 증거를 대신하는 용어. 그 이후로, 그것은 유형 이론가들에게 큰 영감의 원천이었습니다. 고려해야 할 가장 명백한 사항 중 하나는 제안 논리에 대한 이러한 대응 관계를 술어 또는 상위 논리로 확장 할 수 있는지 여부와 방법입니다. 의존적 유형 이론은 처음에이 탐사 길에서 생겨났다.

단순 유형 람다 미적분학에 대한 Curry-Howard 동형에 대한 소개는 여기를 참조 하십시오 . 예를 들어, 증명하고 싶다면 A ∧ B증명 A하고 증명 해야합니다 B. 결합 된 증명은 단순히 한 쌍의 증명입니다 (각 연결마다 하나씩).

자연 공제에서 :

Γ ⊢ A    Γ ⊢ B
Γ ⊢ A ∧ B

간단하게 입력 된 람다 미적분학에서 :

Γ ⊢ a : A    Γ ⊢ b : B
Γ ⊢ (a, b) : A × B

비슷한 ∨유형 및 합계 유형, →함수 유형 및 다양한 제거 규칙이 존재합니다.

입증 할 수없는 (직관적으로 거짓 인) 제안은 무인도 유형에 해당합니다.

논리적 명제와 같은 유형의 유추를 고려하여 유형 세계에서 술어를 모델링하는 방법을 고려할 수 있습니다. 이것이 공식화되는 방법에는 여러 가지가 있지만 (일반적으로 사용되는 표준에 대한 Martin-Löf의 직관적 유형 이론 소개 참조 ) 추상적 인 접근 방식은 일반적으로 술어가 자유 용어 변수의 제안과 같거나, 또는 건의안을 채택하는 기능. 유형 표현식에 용어가 포함되도록 허용하면 람다 미적분학 스타일의 처리가 즉시 가능한 것으로 나타납니다!

건설적인 증거 만 고려하면 다음의 증거는 ∀x ∈ X.P(x)무엇입니까? 우리는이를 증거 함수로 생각할 수 있으며, x해당하는 명제 ( P(x))의 증거에 용어 ( )를 사용 합니다. 종류 (명제)의 회원 (증명) 그래서 ∀x : X.P(x)각각의 ‘종속 함수’이다 x에서이 X유형의 용어를 줄은 P(x).

무엇에 대해 ∃x ∈ X.P(x)? 우리의 모든 구성원이 필요합니다 X, x함께의 증거로 P(x). 종류 (명제)의 회원 (증명) 그래서 ∃x : X.P(x)고유 용어 : ‘좌우 쌍’이다 x에서 X함께 유형의 용어와 함께 P(x).

표기법 : 사용하겠습니다

∀x ∈ X...

클래스 멤버에 대한 실제 진술 X및

∀x : X...

type에 대한 범용 정량화에 해당하는 유형 표현식의 경우 X. 마찬가지로 ∃.

조합 고려 사항 : 제품 및 합계

제안과 유형의 카레 하워드 대응뿐만 아니라, 우리는이 질문의 주요 포인트 인 숫자와 기능을 가진 대수 유형의 조합 대응을 가지고 있습니다. 다행히도 위에서 설명한 종속 유형으로 확장 할 수 있습니다!

모듈러스 표기법을 사용하겠습니다

|A|

유형의 ‘크기’를 나타 내기 위해 A유형과 숫자 사이의 질문에 설명 된 대응 관계를 명시 적으로 나타냅니다 . 이것은 이론을 벗어난 개념입니다. 나는 언어 내에 그러한 연산자가 필요하다고 주장하지 않습니다.

유형의 가능한 (완전히 축소 된, 표준적인) 멤버를 계산해 봅시다

∀x : X.P(x)

이것은 type의 용어 x를 type의 용어 로 취하는 종속 함수 X의 유형 P(x)입니다. 이러한 각 함수에는의 모든 항에 대한 X출력이 있어야하며이 출력은 특정 유형이어야합니다. x에서의 각각 에 대해 X, 이것은 |P(x)|출력의 ‘선택’을 제공합니다.

펀치 라인은

|∀x : X.P(x)| = Π[x : X]|P(x)|

물론 Xis IO ()인 경우 큰 의미 가 없지만 대수 유형에 적용 할 수 있습니다.

마찬가지로 유형의 용어

∃x : X.P(x)

쌍 타입 (x, p)으로 p : P(x)하므로, 어떠한 주어진 x에서 X우리가 임의의 멤버가 적절한 쌍을 만들 수 P(x)주는 |P(x)|‘선택’.

그 후,

|∃x : X.P(x)| = Σ[x : X]|P(x)|

같은 경고로.

이것은 기호 Π와를 사용하여 이론에서 종속 유형에 대한 공통 표기법을 정당화 Σ하며 실제로 많은 이론은 위에서 언급 한 서신으로 인해 ‘모두’와 ‘제품’, ‘존재 함’과 ‘합’사이의 구분을 흐리게합니다.

우리는 점점 가까워지고 있습니다!

벡터 : 종속 튜플을 나타내는

이제 다음과 같은 숫자 표현식을 인코딩 할 수 있습니까?

Σ[n ∈ ℕ]Xⁿ

유형 표현으로?

좀 빠지는. 유형과 자연수가 Xⁿ있는 Haskell 과 같은 표현의 의미를 비공식적으로 고려할 수 있지만 표기법의 남용입니다. 이것은 숫자를 포함하는 유형 표현식입니다. 분명히 유효한 표현식이 아닙니다 .Xn

반면에 그림에 종속 된 유형의 경우 숫자를 포함하는 유형이 정확하게 포인트입니다. 실제로 종속 튜플 또는 ‘벡터’는 종속 유형이 목록 액세스와 같은 작업에 실용적인 유형 수준의 안전성을 제공 할 수있는 방법에 대한 매우 일반적인 예입니다 . 벡터는 길이에 관한 타입 레벨 정보와 함께리스트 일뿐 Xⁿ입니다.

이 답변이 지속되는 동안

Vec X n

-type 값 의 length- nvector 유형입니다 X.

기술적으로 n여기에는 실제 자연수가 아니라 자연수 시스템의 표현이 있습니다. 우리는 (자연수를 나타낼 수 있습니다 Nat중 하나를 제로 (로 페 아노 스타일) 0) 또는 후계자 ( S또 다른 자연수의), 그리고 n ∈ ℕ내가 쓰기 ˻n˼에 용어 의미 Nat나타내는을 n. 예를 들어 ˻3˼입니다 S (S (S 0)).

그럼 우리는

|Vec X ˻n˼| = |X|ⁿ

어떤 n ∈ ℕ.

Nat 유형 : ℕ 용어를 유형으로 승격

이제 다음과 같은 표현식을 인코딩 할 수 있습니다

Σ[n ∈ ℕ]Xⁿ

유형으로. 이러한 특정 표현은 물론 X질문에서 식별 된 바와 같이 의 목록 유형에 대해 동형 인 유형을 야기 할 것이다 . (그뿐만 아니라,하지만보기의 카테고리 이론적 관점에서, 유형 기능 – 펑터이다 – 복용 X위의 유형은 자연적으로 동형 목록 펑터합니다.)

‘임의’기능을위한 퍼즐의 마지막 조각은 인코딩하는 방법입니다.

f : ℕ → ℕ

같은 표현

Σ[n ∈ ℕ]f(n)Xⁿ

전력 계수에 임의의 계수를 적용 할 수 있습니다.

우리는 이미 대수 유형과 숫자의 대응 관계를 이해하여 유형에서 숫자로, 유형 함수에서 숫자로 맵핑 할 수 있습니다. 우리는 또한 다른 길로 갈 수 있습니다! -자연수를 취하면 종속 유형이 있는지 여부에 관계없이 많은 수의 멤버와 함께 명백한 대수 유형이 있습니다. 우리는 이것을 유도함으로써 유형 이론 밖에서 쉽게 증명할 수 있습니다 . 우리가 필요한 것은 시스템 내부 에서 자연수에서 유형으로 매핑하는 방법 입니다.

우리가 의존적 유형을 가지면, 재귀에 의한 유도와 구성에 의한 증거는 매우 유사 해집니다. 실제로 많은 이론에서 똑같은 것입니다. 우리는 우리의 요구를 충족시키는 유형이 존재한다는 사실을 귀납하여 증명할 수 있기 때문에이를 구성 할 수 없어야합니까?

용어 레벨에서 유형을 나타내는 여러 가지 방법이 있습니다. 여기서는 *유형의 우주에 대한 가상의 Haskellish 표기법을 사용할 것입니다 . 그 자체는 일반적으로 종속 설정의 유형으로 간주됩니다. 1

마찬가지로, ℕ종속 유형 이론이있는 것처럼 ‘ 제거’ 를 표시하는 방법은 최소한 여러 가지 가 있습니다. Haskellish 패턴 일치 표기법을 사용하겠습니다.

우리는 매핑을 필요 α로 Nat하는 *특성과,

∀n ∈ ℕ.|α ˻n˼| = n.

다음 의사 정의가 충분합니다.

data Zero -- empty type
data Successor a = Z | Suc a -- Successor ≅ Maybe

α : Nat -> *
α 0 = Zero
α (S n) = Successor (α n)

그래서 우리는 그 α행동이 후계자의 행동 을 반영하여 S일종의 동질성을 만드는 것을 볼 수 있습니다. Successor유형의 멤버 수에 ‘1을 추가’하는 유형 함수입니다. 즉, 정의 된 크기의 |Successor a| = 1 + |a|모든 것 a입니다.

예를 들어 α ˻4˼( α (S (S (S (S 0)))))는

Successor (Successor (Successor (Successor Zero)))

이 유형의 용어는

Z
Suc Z
Suc (Suc Z)
Suc (Suc (Suc Z))

정확히 네 가지 요소를 제공합니다 |α ˻4˼| = 4.

마찬가지로, n ∈ ℕ우리는

|α ˻n˼| = n

필요에 따라.

  1. 많은 이론에 따르면 멤버는 *유형을 나타내는 대표자 일 뿐이며 유형 용어에서 *관련 유형 으로의 명시 적 매핑으로 작업이 제공됩니다 . 다른 이론은 리터럴 유형 자체가 용어 수준 엔티티가되도록 허용합니다.

‘임의’기능?

이제 우리는 완전한 일반 전력 계열을 유형으로 표현하는 장치를 갖추 었습니다!

시리즈

Σ[n ∈ ℕ]f(n)Xⁿ

유형이된다

∃n : Nat.α (˻f˼ n) × (Vec X n)

˻f˼ : Nat → Nat함수 언어 내에서 적절한 표현이 어디에 있습니까 f? 우리는 이것을 다음과 같이 볼 수 있습니다.

|∃n : Nat.α (˻f˼ n) × (Vec X n)|
    = Σ[n : Nat]|α (˻f˼ n) × (Vec X n)|          (property of ∃ types)
    = Σ[n ∈ ℕ]|α (˻f˼ ˻n˼) × (Vec X ˻n˼)|        (switching Nat for ℕ)
    = Σ[n ∈ ℕ]|α ˻f(n)˼ × (Vec X ˻n˼)|           (applying ˻f˼ to ˻n˼)
    = Σ[n ∈ ℕ]|α ˻f(n)˼||Vec X ˻n˼|              (splitting product)
    = Σ[n ∈ ℕ]f(n)|X|ⁿ                           (properties of α and Vec)

이것이 어떻게 ‘임의’입니까? 우리는이 방법에 의한 정수 계수뿐만 아니라 자연수로 제한됩니다. 그 외에도 의존 유형이 f있는 Turing Complete 언어를 고려하면 자연 수 계수로 모든 분석 함수를 나타낼 수 있습니다.

예를 들어, List X ≅ 1/(1 - X)이러한 부정적 및 비정 수 ‘유형’유형과 관련하여 어떤 상황에서 어떤 의미가 있는지에 대한 사례와의 상호 작용에 대해서는 조사하지 않았습니다 .

이 답변이 임의의 유형 함수로 얼마나 멀리 갈 수 있는지 탐구하는 데 도움이되기를 바랍니다.