再帰データ型
同型再帰型では、再帰型 μ α . T {\displaystyle \mu \alpha .T} とその展開結果である T [ μ α . T / α ] {\displaystyle T[\mu \alpha .T/\alpha ]} は別の型であり、特殊な項構成 fold と unfold で識別され、これらの間で同型写像を構成する。正確に記せば、 fold : T [ μ α . T / α ] → μ α . T {\displaystyle {\mbox{fold}}:T[\mu \alpha .T/\alpha ]\to \mu \alpha .T} と unfold : μ α . T → T [ μ α . T / α ] {\displaystyle {\mbox{unfold}}:\mu \alpha .T\to T[\mu \alpha .T/\alpha ]} であり、これらは互いに逆関数である。
部分型付けにおいてよく使われる方法として Amber 規則があり、μX.
例えば、自然数を Haskell のデータ型として表すと次のようになる(ペアノの公理参照):
また、型理論では n a t = μ α .1 + α {\displaystyle nat=\mu \alpha .1+\alpha } となる。ここでは、Zero と Succ コンストラクタで表現されており、Zero は引数をとらず(型理論の定義の α {\displaystyle \alpha } に相当)、Succ は別の Nat を引数としている(型理論での定義の 1 + α {\displaystyle 1+\alpha } に相当)。
構造的型システムでの再帰型には、同型再帰型(iso-recursive type)と同値再帰型(equi-recursive type)の2つの形式がある。同型再帰型の実装は簡単であるが、同値再帰型は議論と証明が複雑で、ほとんどのプログラミング言語は名前的型システムか構造的型システムの同型再帰型を使用している。
再帰型(英: recursive type)とは、型の定義中にそれ自身の型が出現するような再帰する型のこと。相互再帰により直接は現れないものもある。再帰データ型(英: recursive data type)とは、データ型における再帰型のこと。
↑ (More) Recursive Type Aliases - Announcing TypeScript 3.7 - TypeScript
↑ Benjamin C. Pierce「19.3 名前的型システムと構造的型システム」『型システム入門 −プログラミング言語と型の理論−』オーム社、2013年3月26日。ISBN 978-4274069116。
1 2 Benjamin C. Pierce『型システム入門 −プログラミング言語と型の理論−』オーム社、2013年3月26日。ISBN 978-4274069116。
この記事は2008年11月1日以前にFree On-line Dictionary of Computingから取得した項目の資料を元に、GFDL バージョン1.3以降の「RELICENSING」(再ライセンス) 条件に基づいて組み込まれている。