재귀 데이터 유형

컴퓨터 프로그래밍 언어에서 재귀 데이터 유형(재귀 정의, 유도 정의 또는 유도 데이터 유형이라고도 함)은 동일한 유형의 다른 값을 포함할 수 있는 값의 데이터 유형입니다.재귀 유형의 데이터는 일반적으로 방향^{[citation needed]} 그래프로 표시됩니다.

컴퓨터 과학에서 재귀의 중요한 적용은 목록과 나무와 같은 동적 데이터 구조를 정의하는 것입니다.재귀 데이터 구조는 런타임 요건에 따라 임의로 큰 크기로 확장할 수 있습니다.반대로 정적 배열의 크기 요구사항은 컴파일 시 설정해야 합니다.

때때로 "유도적 데이터 유형"이라는 용어는 반드시 재귀적이지 않은 대수적 데이터 유형에 사용됩니다.

예

예를 들어 Haskell의 목록 유형을 들 수 있습니다.

데이터. 목록. a = 제로   단점 a (목록. a)

이는 a 목록이 빈 목록이거나 'a'(목록의 "머리")와 다른 목록("꼬리")을 포함하는 cons 셀임을 나타냅니다.

다른 예로는 Java에서 동일한 단일 링크 유형을 들 수 있습니다.

학급 목록.< >E> {     E 가치;     목록.< >E> 다음 분.; }

이것은 타입 E의 빈 목록에 타입 E의 데이터 멤버와 리스트의 나머지 부분에 대한 다른 List 오브젝트에 대한 참조(또는 이것이 리스트의 끝임을 나타내는 늘 참조)가 포함되어 있음을 나타냅니다.

상호 재귀적 데이터 유형

데이터 유형은 상호 재귀로도 정의할 수 있습니다.가장 중요한 기본 예는 트리이며, 포레스트(트리 리스트)의 관점에서 상호 재귀적으로 정의할 수 있습니다.기호:

f: [t[1], ..., t[k] t: v f

포레스트 f는 트리 리스트로 구성되며 트리 t는 값 v와 포레스트 f(자녀)의 쌍으로 구성된다.이 정의는 한 가지 유형의 목록과 두 가지 유형의 쌍으로 구성된 간단한 용어로 트리를 표현하기 때문에 우아하고 추상적으로 작업하기 쉽습니다(예: 나무의 속성에 대한 이론을 증명할 때).

이 상호 재귀 정의는 포리스트의 정의를 삽입함으로써 단일 재귀 정의로 변환할 수 있습니다.

t: v [t[1], ..., t[k]

트리 t는 값 v와 트리 리스트(자녀)로 구성됩니다.이 정의는 보다 콤팩트하지만 다소 복잡합니다.트리는 한 가지 타입과 다른 타입의 리스트로 구성되어 있습니다.이것에 대해서는, 결과를 증명하기 위해서, 혼란의 해소가 필요합니다.

표준 ML에서는 트리 및 포레스트 데이터 유형을 다음과 같이 상호 재귀적으로 정의할 수 있으므로 ^[1]빈 트리가 허용됩니다.

데이터형 'a' 트리 = 빈   노드 의 'a' * 'a' 숲 그리고.      'a' 숲 = 제로   단점 의 'a' 트리 * 'a' 숲

Haskell에서는 트리 및 포레스트 데이터 유형을 비슷하게 정의할 수 있습니다.

데이터. 트리 a = 빈               노드 (a, 숲 a)  데이터. 숲 a = 제로                 단점 (트리 a) (숲 a)

이론.

유형 이론에서 재귀형은 일반형 μα를 가진다.T형 변수α는 T형에서 나타날 수 있으며, T형 자체를 나타낸다.

예를 들어 자연수(페아노 산술 참조)는 Haskell 데이터 형식으로 정의할 수 있습니다.

데이터. 내트 = 영   성공. 내트

유형 이론에서, $nat=\mu \alpha .1+\alpha$ 는 다음과 같이 말할 수 있다: n a $nat=\mu \alpha .1+\alpha$ $=$ $nat=\mu \alpha .1+\alpha$ α $nat=\mu \alpha .1+\alpha$ .1 + α {\ $displaystyle nat=\mu \alpha .$ 1+\alpha $}$ 여기서 $nat=\mu \alpha .1+\alpha$ , 합 유형의 두 암은 제로 및 Suc 데이터 생성자를 나타낸다.0은 인수를 사용하지 않고(따라서 유닛타입으로 나타남), Suc는 다른 Nat를 사용합니다(따라서 $\mu \alpha .1+\alpha$ + $α$ 의 다른 요소(\ $displaystyle \mu \alpha .$ 1+\alpha $\mu \alpha .1+\alpha$ }). $\mu \alpha .1+\alpha$

재귀 유형에는 두 가지 형식이 있습니다. 이른바 등귀 유형과 등귀 유형입니다.두 가지 형태는 재귀 유형의 용어가 도입되고 제거되는 방식에 따라 다릅니다.

등각형

등귀형에서는 $\mu \alpha .T$ $\mu \alpha .T$ . $\mu \alpha .T$ \ $displaystyle \ mu$ \ alpha 입니다 $.$ $T}$ 및 $\mu \alpha .T$ 그 확장(또는 전개) $T[\mu \alpha .T/\alpha ]$ [ $T[\mu \alpha .T/\alpha ]$ α . $T[\mu \alpha .T/\alpha ]$ / $T[\mu \alpha .T/\alpha ]$ α $T[\mu \alpha .T/\alpha ]$ ]{ $displaystyle$ T [ \ $mu$ \ $alpha$ ] $T/\alpha ]}$ (Where the notation $X[Y/Z]$ indicates that all instances of Z are replaced with Y in X) are distinct (and disjoint) types with special term constructs, usually called roll and unroll, that form an isomorphism between them. $roll:T[\mu \alpha .T/\alpha ]\to \mu \alpha .T$ 는 $roll:T[\mu \alpha .T/\alpha ]\to \mu \alpha .T$ $roll:T[\mu \alpha .T/\alpha ]\to \mu \alpha .T$ $roll:T[\mu \alpha .T/\alpha ]\to \mu \alpha .T$ : $roll:T[\mu \alpha .T/\alpha ]\to \mu \alpha .T$ [ $roll:T[\mu \alpha .T/\alpha ]\to \mu \alpha .T$ α . $roll:T[\mu \alpha .T/\alpha ]\to \mu \alpha .T$ / $roll:T[\mu \alpha .T/\alpha ]\to \mu \alpha .T$ α ] $roll:T[\mu \alpha .T/\alpha ]\to \mu \alpha .T$ $roll:T[\mu \alpha .T/\alpha ]\to \mu \alpha .T$ α . $roll:T[\mu \alpha .T/\alpha ]\to \mu \alpha .T$ \ \ $display style$ roll : $T[\mu \alpha]$ $T/\alpha ]\to \mu \$ $T}$ $unroll:\mu \alpha .T\to T[\mu \alpha .T/\alpha ]$ $unroll:\mu \alpha .T\to T[\mu \alpha .T/\alpha ]$ $unroll:\mu \alpha .T\to T[\mu \alpha .T/\alpha ]$ $unroll:\mu \alpha .T\to T[\mu \alpha .T/\alpha ]$ $unroll:\mu \alpha .T\to T[\mu \alpha .T/\alpha ]$ l $unroll:\mu \alpha .T\to T[\mu \alpha .T/\alpha ]$ : $unroll:\mu \alpha .T\to T[\mu \alpha .T/\alpha ]$ α . $unroll:\mu \alpha .T\to T[\mu \alpha .T/\alpha ]$ $unroll:\mu \alpha .T\to T[\mu \alpha .T/\alpha ]$ [ $unroll:\mu \alpha .T\to T[\mu \alpha .T/\alpha ]$ α . $unroll:\mu \alpha .T\to T[\mu \alpha .T/\alpha ]$ / $unroll:\mu \alpha .T\to T[\mu \alpha .T/\alpha ]$ α $]$ \ $display$ style $unroll$ : \ $mu$ \ $alpha$ 。 $T\to T [\mu \alpha]$ $T/\alpha$ $unroll:\mu \alpha .T\to T[\mu \alpha .T/\alpha ]$ 입니다.이 두 가지는 역함수입니다.

등가형

등가 규칙에서는 재귀 $\mu \alpha .T$ $.\displaystyle \mu \$ alpha. $T$ $T[\mu \alpha .T/\alpha ]$ 및 $\mu \alpha .T$ 그 $T[\mu \alpha .T/\alpha ]$ $T[\mu \alpha .T/\alpha ]$ [ $α$ . T / α $]{ displaystyle$ T [ \ mu \ alpha $T[\mu \alpha .T/\alpha ]$ ] $T/\alpha ]}$ 은 $T[\mu \alpha .T/\alpha ]$ (는) 같습니다.즉, 이 두 가지 유형의 표현은 같은 유형을 나타내는 것으로 이해됩니다.사실, 대부분의 등가형 이론은 더 나아가서 본질적으로 "무한 확장"이 동일한 두 가지 유형의 표현식이 동등하다는 것을 명시한다.이러한 규칙의 결과, 등가형은 등가형보다 훨씬 더 복잡합니다.유형 확인 및 유형 추론과 같은 알고리즘 문제는 등가형에서도 더 어렵습니다.직접 비교는 등가형에서는 의미가 없기 때문에 O(n log n) 시간 내에 표준 형식으로 변환하여 쉽게 ^[2]비교할 수 있습니다.

등각형은 공칭 객체 지향 프로그래밍 언어에서 볼 수 있는 자기 참조형(또는 상호 참조형) 정의의 형태를 포착하고 객체 및 클래스의 유형 이론 의미론에서도 발생합니다.함수형 프로그래밍 언어에서는 (^[3]데이터형을 가장한) 등각형도 일반적입니다.

재귀형 동의어

TypeScript의 유형 별칭에서 ^[4]재귀가 허용됩니다.다음의 예를 사용할 수 있습니다.

Tree = number Tree[]; let tree:트리 = [1, [2, 3];

단, OCaml 미란다의 동의어 유형에는 재귀가 허용되지 않습니다.-rectypes플래그가 사용되었거나 레코드 또는 변종) 및 Haskell. 예를 들어 다음과 같은 Haskell 유형은 불법입니다.

유형 나빠 = (내부, 나빠) 유형 사악한 = 불 -> 사악한

대신 대수적 데이터 유형(컨스트럭터가 1개뿐인 경우에도) 내에 래핑해야 합니다.

데이터. 좋아요. = 짝 내부 좋아요. 데이터. 좋아. = 재밌어요 (불 -> 좋아.)

이는 C의 typedef와 같이 type synonym이 컴파일 시 정의로 대체되기 때문입니다.(유형 동의어는 "실제" 유형이 아니라 프로그래머의 편의를 위해 "에일리어스"일 뿐입니다.)그러나 재귀 유형을 사용하여 이 작업을 시도하면 에일리어스가 대체되는 횟수에 관계없이 자신을 참조하기 때문에 무한 루프됩니다. 예를 들어 "Bad"는 무한히 증가합니다.Bad→(Int, Bad)→(Int, (Int, Bad))→....

또 다른 방법은 등각형 시스템이 롤링 및 언롤 타이밍을 파악할 수 있도록 하기 위해 간접(대수 데이터형) 레벨이 필요하다는 것입니다.

「」를 참조해 주세요.

레퍼런스

^ Harper 2000, "데이터 유형". sfn 오류: 대상 없음: CITREFHarper 2000 (도움말)
^ "Numbering Matters: First-Order Canonical Forms for Second-Order Recursive Types". CiteSeerX 10.1.1.4.2276. {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)
^ 프로그래밍 언어에 관한 ACM의 iso-recursive 서브타이핑 절차 재검토
^ (기타) 재귀형 에일리어스 - Announcing TypeScript 3.7 - TypeScript

[FOOTNOTEHarper2000"[httpswwwcscmuedu~rwhintrosmlcoredatatypeshtm_Data_Types]"-1] Harper 2000, "데이터 유형". sfn 오류: 대상 없음: CITREFHarper 2000 (도움말)

[canonicalize-2] "Numbering Matters: First-Order Canonical Forms for Second-Order Recursive Types". CiteSeerX 10.1.1.4.2276. {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)

[3] 프로그래밍 언어에 관한 ACM의 iso-recursive 서브타이핑 절차 재검토

[4] (기타) 재귀형 에일리어스 - Announcing TypeScript 3.7 - TypeScript

[1]

[2]

[3]

[4]

v t 데이터형
해석되지 않다	조금 바이트 트리트 트릿 단어 비트 배열
숫자	임의 정밀도 또는 bignum 복잡한 십진수 고정점 부동 소수점 정밀도 저하 미니 인초 반정밀 플로트 16 단일 정밀도 2배 정밀도 4배 정밀도 8배 정밀도 정밀도 향상 롱 더블 정수 서명성 간격 합리적인
포인터	주소. 물리적. 가상 언급
본문	성격 스트링 무효로 종료되었다
컴포지트	대수 데이터형 일반화된 어레이 연관 배열 학급 의존하는 평등 귀납적 교차로 목록. 물건 메타 오브젝트 옵션 타입 제품. 레코드 또는 구조 세련 세트 유니언 태그 부착
다른.	부울 하단 타입 수집 열거형 예외. 기능 유형 불투명 데이터 유형 재귀 데이터 유형 세마포 개울. 톱 타입 유형 클래스 유닛 타입 무효
관련된 토픽	추상 데이터 유형 data 구조 포괄적인 친절한 메타클래스 오브젝트 타입 파라메트릭 다형 원시 데이터 유형 프로토콜 인터페이스 서브타이핑 형식 생성자 유형 변환 유형계 유형 이론 변수

Search

재귀 데이터 유형

네임스페이스

더

목차

예

상호 재귀적 데이터 유형

이론.

등각형

등가형

재귀형 동의어

「」를 참조해 주세요.

레퍼런스

Search

재귀 데이터 유형

예

상호 재귀적 데이터 유형

이론.

등각형

등가형

재귀형 동의어

「 」를 참조해 주세요.

레퍼런스

「」를 참조해 주세요.