タグ付きユニオン

コンピュータサイエンスにおいて、タグ付き共用体(バリアント、バリアントレコード、選択型、判別共用体、分離共用体、和型、またはコプロダクトとも呼ばれる) は、複数の異なるが固定された型を取ることができる値を保持するために使用されるデータ構造です。一度に使用できるのは 1 つの型のみであり、タグフィールドはどの型が使用されているかを明示的に示します。これは、その型が操作されるときにそれぞれが正しく処理される必要がある、複数の「ケース」を持つ型と考えることができます。これは、値の一部のコンポーネントがその値と同じ型になる可能性がある再帰データ型を定義する際に重要です。たとえば、マルチノードのサブツリーとリーフを区別する必要があるツリーを表す型を定義する場合などです。通常の共用体と同様に、タグ付き共用体は、一度に 1 つのみ使用されるため、各型のストレージ領域を重複させることでストレージを節約できます。

タグ付き共用体は、 MLやHaskellなどの関数型プログラミング言語で最も重要であり、データ型(代数データ型を参照)と呼ばれ、コンパイラーはタグ付き共用体のすべてのケースが常に処理されることを検証できるため、多くの種類のエラーを回避できます。コンパイル時にチェックされる合計型はRustでも広く使用されており、 enumと呼ばれています。ただし、タグ付き共用体はほぼすべてのプログラミング言語で構築でき、タグなし共用体 (単に共用体と呼ばれることが多い) よりもはるかに安全です。タグなし共用体も似ていますが、共用体のどのメンバーが現在使用中であるかを明示的に追跡しません。

タグ付き共用体には、多くの場合、コンストラクターの概念が伴います。これは、クラスのコンストラクターに似ていますが同じではありません。コンストラクターは、タグと対応する型の値を指定して、タグ付き共用体型の値を生成する関数または式です。

数学的には、タグ付き和集合は、通常 + を使用して記述される、分離和集合または判別和集合に対応します。分離和集合A + Bの要素が与えられた場合、それがAまたはB のどちらから来たのかを判断できます。要素が両方に存在する場合、 A + Bの値の実質的に異なるコピーが 2 つ存在し、1 つはAから、もう 1 つはBからになります。

型理論では、タグ付き和は和型と呼ばれます。和型は積型の双対です。表記法はさまざまですが、通常、和型A + Bには、 inj ₁ : A → A + Bとinj ₂ : B → A + Bの 2 つの導入形式 (注入)が伴います。 除去形式はケース分析で、ML スタイルの言語ではパターン マッチングと呼ばれます。つまり、 eが型A + Bを持ち、e ₁とe _{2 がそれぞれ}x : Aとy : B の仮定の下で型を持つ場合、項は型を持ちます。和型は、カリー–ハワード対応の下で直観主義論理和に対応します。 ${\displaystyle \tau}$${\displaystyle {\mathsf {case}}\ e\ {\mathsf {of}}\ x\Rightarrow e_{1}\mid y\Rightarrow e_{2}}$${\displaystyle \tau}$

列挙型は、ユニット型のタグ付きユニオンという、退化したケースとして考えることができます。これは、nullary コンストラクタのセットに対応し、タグの値以外の追加データを保持しないため、単純なタグ変数として実装できます。

ロープ、遅延評価、クラス階層(下記参照)、任意精度演算、CDR コーディング、間接ビット、その他の種類のタグ付きポインターなど、多くのプログラミング手法とデータ構造は、通常、何らかのタグ付きユニオンを使用して実装されます。

タグ付きユニオンは、最も単純な種類の自己記述型 データ形式と見なすことができます。タグ付きユニオンのタグは、最も単純な種類のメタデータと見なすことができます。

タグ付き共用体がタグなし共用体よりも優れている主な点は、すべてのアクセスが安全であり、コンパイラーがすべてのケースが処理されているかどうかを確認できることです。タグなし共用体は、現在アクティブなフィールドを正しく識別するためにプログラム ロジックに依存しているため、そのロジックが失敗すると、異常な動作や見つけにくいバグが発生する可能性があります。

各型のフィールドを含む単純なレコードに対するタグ付きユニオンの主な利点は、すべての型のストレージを重複させることでストレージを節約できることです。実装によっては、最大の型に十分なストレージを予約するものもあれば、必要に応じてタグ付きユニオン値のサイズを動的に調整するものもあります。値が不変である場合は、必要なだけのストレージを割り当てるのは簡単です。

タグ付き共用体の主な欠点は、タグがスペースを占有することです。通常は選択肢が少ないため、スペースが見つかった場合はタグを 2 ビットまたは 3 ビットに詰め込むことができますが、これらのビットさえ利用できない場合もあります。この場合、便利な代替手段は、折りたたみ、計算、またはエンコードされたタグです。タグの値は、共用体フィールドの内容から動的に計算されます。一般的な例としては、予約値の使用(たとえば、正の数を返す関数が失敗を示すために -1 を返す場合) や、タグ付きポインタで最もよく使用されるセンチネル値があります。

タグなし共用体は、C++ で再解釈キャストと呼ばれる、型間のビットレベルの変換を実行するために使用されることがあります。タグ付き共用体はこの目的には適しておらず、通常はタグが変更されるたびに新しい値が割り当てられます。

多くの言語は、ある程度、ユニバーサル データ型をサポートしています。ユニバーサル データ型は、他のすべての型のすべての値を含む型であり、多くの場合、ユニバーサル型の値の実際の型をテストする方法が提供されています。これらは、バリアントと呼ばれることもあります。ユニバーサル データ型は、正式な定義ではタグ付き共用体に相当しますが、一般的なタグ付き共用体には比較的少数のケースが含まれており、これらのケースは、データ構造ノードや命令など、単一の一貫した概念を表現するさまざまな方法を形成します。また、タグ付き共用体の使用時には、考えられるすべてのケースが処理されることが期待されます。ユニバーサル データ型の値には関連性がなく、それらすべてを処理する現実的な方法はありません。

オプション型や例外処理と同様に、タグ付き共用体は例外的な結果の発生を処理するために使用されることがあります。多くの場合、これらのタグは予約値として型に組み込まれ、その発生は一貫してチェックされません。これはプログラミング エラーのよくある原因です。タグ付き共用体のこの使用は、次の関数を持つ モナドとして形式化できます。

${\displaystyle {\text{return}}\colon A\to \left(A+E\right)=a\mapsto {\text{value}}\,a}$

${\displaystyle {\text{bind}}\colon \left(A+E\right)\to \left(A\to \left(B+E\right)\right)\to \left(B+E\right)=a\mapsto f\mapsto {\begin{cases}{\text{err}}\,e&{\text{if}}\ a={\text{err}}\,e\\f\,a'&{\text{if}}\ a={\text{value}}\,a'\end{cases}}}$

ここで、「value」と「err」はユニオン型のコンストラクタ、AとBは有効な結果型、Eはエラー条件の型です。あるいは、同じモナドをreturnと2つの追加関数fmapとjoinで記述することもできます。

${\displaystyle {\text{fmap}}\colon (A\to B)\to \left(\left(A+E\right)\to \left(B+E\right)\right)=f\mapsto a\mapsto {\begin{cases}{\text{err}}\,e&{\text{if}}\ a={\text{err}}\,e\\{\text{value}}\,{\text{(}}\,f\,a'\,{\text{)}}&{\text{if}}\ a={\text{value}}\,a'\end{cases}}}$

${\displaystyle {\text{join}}\colon ((A+E)+E)\to (A+E)=a\mapsto {\begin{cases}{\text{err}}\,e&{\mbox{if}}\ a={\text{err}}\,e\\{\text{err}}\,e&{\text{if}}\ a={\text{value}}\,{\text{(err}}\,e\,{\text{)}}\\{\text{value}}\,a'&{\text{if}}\ a={\text{value}}\,{\text{(value}}\,a'\,{\text{)}}\end{cases}}}$

整数の二分木を構築したいとします。ML では、次のようなデータ型を作成することでこれを実現します。

データ型 tree  =  Leaf 
              |  ( int * tree * tree )のノード      

これは 2 つのケースを持つタグ付きユニオンです。1 つはリーフで、ツリーのパスを終了するために使用され、命令型言語の null 値のように機能します。もう 1 つのブランチにはノードが保持され、これには整数と左と右のサブツリーが含まれます。Leaf と Node はコンストラクターであり、これらを使用して、次のような特定のツリーを実際に生成できます。

ノード( 5 、 ノード( 1 、 リーフ、 リーフ))) ノード( 3 、 リーフ、 ノード( 4 、 リーフ、 リーフ)))

これは次のツリーに対応します:

これで、たとえばツリー内のノードの数をカウントする型安全な関数を簡単に記述できます。

fun  countNodes ( Leaf )  =  0 
  |  countNodes ( Node ( int ,  left ,  right ))  = 
      1  +  countNodes ( left )  +  countNodes ( right )

ALGOL 68では、タグ付きユニオンは統合モードと呼ばれ、タグは暗黙的であり、caseどのフィールドにタグが付けられるかを決定するために構造が使用されます。

mode node = union (real, int, compl, string);

union caseofの使用例node:

ノードn := "1234";
 
ケースn in 
  (実数r ): print(("実数:", r)),
  ( int i): print(("int:", i)),
  (補完c): print(("補完:", c)),
  (文字列s): print(("文字列:", s))
   out          print(("?:", n))
 esac

ML (1970 年代) やHaskell (1990 年代)などの関数型プログラミング言語では、タグ付き共用体に中心的な役割が与えられ、すべてのケースが処理されているかどうかをチェックする機能があります。他の言語でも、タグ付き共用体をサポートしているものがあります。

Pascal、Ada、およびModula-2では、これらをバリアント レコード(Ada では正式に判別されるタイプ) と呼び、次の Pascal の例のように、タグ フィールドを手動で作成し、タグ値を指定する必要があります。

type shapeKind = ( square , rectangle , circle ) ; shape = record centerx : integer ; centery : integer ; case kind : shapeKind of square : ( side : integer ) ; rectangle : ( width , height : integer ) ; circle : ( radius : integer ) ; end ;     
       
                  
                  
                    
                       
                        
                       
	      

そして、これは Ada と同等です:

type  Shape_Kindは ( Square 、Rectangle 、Circle )です 。type Shape ( Kind : Shape_Kind )は、record Center_X : Integer ; Center_Y : Integer です。case Kindは、when Square => Side : Integer です。when Rectangle = > Width 、Height : Integer です。when Circle => Radius : Integer です。end case ; end record ;  
     
     
     
     
        
           
        
            
        
           
    



-- 判別式が期待されたものではないのに、判別式の特定の値によって
存在が左右されるメンバーにアクセスしようとすると、エラーが発生します。

CおよびC++では、タグが常にチェックされる厳密なアクセス規則を使用して、タグなしの共用体からタグ付き共用体を作成できます。

列挙型ShapeKind {正方形、長方形、円};      

struct Shape { int centerx ; int centery ; enum ShapeKind kind ; union { struct { int side ; }; /* 正方形 */ struct { int width , height ; }; /* 長方形 */ struct { int radius ; }; /* 円 */ }; };  
     
     
      
     
                       
              
                     
    


int getSquareSide ( struct Shape * s ) { assert ( s -> kind == Square ); return s -> side ; }    
      
     


void setSquareSide ( struct Shape * s 、int side ) { s -> kind = Square ; s -> side = side ; }      
      
      


/* 等々 */

ユニオン フィールドが関数を通じてのみアクセスされる限り、アクセスは安全かつ正確になります。エンコードされたタグにも同じアプローチを使用できます。タグをデコードし、各アクセスでチェックするだけです。これらのタグ チェックの非効率性が懸念される場合は、最終バージョンで自動的に削除される可能性があります。

C と C++ には、特定のタグ付き共用体である、おそらく null のポインターoptionの言語サポートもあります。これは、ML の 型またはHaskell の 型と比較でき、タグ付きポインターMaybeと見なすことができます。タグ付き共用体 (エンコードされたタグ付き) は次の 2 つの型です。

• 有効なポインタ、
• 例外的な状態を示す、という 1 つの値のみを持つnullポインター型。null

残念ながら、C コンパイラは null ケースが常に処理されているかどうかを確認しません。例外的なケースを無視する傾向があるため、これは C コードで特によく見られるエラーの原因です。

Cycloneと呼ばれるCの高度な方言には、タグ付き共用体に対する広範な組み込みサポートがあります。^[1]

Rust、Haxe、Swift言語の列挙型もタグ付きユニオンとして機能します。

Boost C++ ライブラリのバリアント ライブラリは、関数オブジェクトを使用してアクセス可能な、安全なタグ付きユニオンを C++ のライブラリとして実装できることを実証しました。

構造体display : boost :: static_visitor < void > { void operator ()( int i ) { std :: cout << "It's an int, with value " << i << std :: endl ; }   

      
    
              
    

    void operator ()( const std :: string & s ) { std :: cout << "It's a string, with value " << s << std :: endl ; } };   
    
              
    


boost :: variant < int , std :: string > v = 42 ; boost :: apply_visitor ( display (), v );    
 

boost :: variant < int , std :: string > v = "hello world" ; boost :: apply_visitor ( display (), v );    
 

Scala にはケースクラスがあります:

シールされた抽象クラスTreeケースオブジェクトLeaf はTreeを拡張します。ケースクラスNode ( value : Int 、left : Tree 、right : Tree )はTreeを拡張します。   
    
         

val tree = Node ( 5 、Node ( 1 、Leaf 、Leaf ) 、Node ( 3 、Leaf 、Node ( 4 、Leaf 、Leaf ) )))           

クラス階層がシールされているため、コンパイラはすべてのケースがパターン マッチで処理されることを確認できます。

ツリーマッチ{ case Node ( x , _ , _ ) => println ( "トップレベルノードの値: " + x ) case Leaf => println ( "トップレベルノードはリーフです" ) }  
         
              

Scala のケースクラスでは、サブタイプによる再利用も許可されます。

シールされた抽象クラスShape ( centerX : Int 、centerY : Int )ケースクラスSquare ( side : Int 、centerX : Int 、centerY : Int )はShape ( centerX 、centerY )を拡張します。ケースクラスRectangle ( length : Int 、height : Int 、centerX : Int 、centerY : Int )はShape ( centerX 、centerY )を拡張します。ケースクラスCircle ( radius : Int 、centerX : Int 、centerY : Int )はShape ( centerX 、centerY )を拡張します。      
          
            
          

F#には区別された共用体があります:

type Tree = | Leaf |値のノード: int * left : Tree * right : Tree  
   
            

tree = Node ( 5 、Node ( 1 、Leaf 、Leaf ) 、Node ( 3 、Leaf 、Node ( 4 、Leaf 、Leaf ) )とします。           

定義されたケースは網羅的であるため、コンパイラはパターン マッチですべてのケースが処理されることを確認できます。

ツリーを| Node ( x , _, _) -> printfn "トップレベルノードの値: %i" x | Leaf -> printfn "トップレベルノードはリーフです" と一致  
        
              

Haxeの列挙型はタグ付き共用体としても機能します: ^[2]

列挙型カラー{赤;緑;青; Rgb ( r : Int , g : Int , b : Int ); }  
  
  
  
    

これらは、スイッチ式を使用して一致させることができます。

switch ( color ) { case Red : trace ( "色は赤でした" ); case Green : trace ( "色は緑でした" ); case Blue : trace ( "色は青でした" ); case Rgb ( r , g , b ): trace ( "色の赤の値は " + rでした); }  
    
    
    
       

Nimには、PascalやAdaのものと宣言が似ているオブジェクトのバリアント^{[3]があります。}

type 
ShapeKind = enum skSquare 、skRectangle 、skCircle Shape = object centerX 、centerY : int case kind : ShapeKind of skSquare : side : int of skRectangle : length 、height : int of skCircle : radius : int    
      
    
      
      
     
       
     
        
     
       

マクロは、パターン マッチングをエミュレートしたり、オブジェクト バリアントを宣言するための構文糖を作成したりするために使用できます。ここでは、パッケージ patty によって実装されているマクロを示します。

輸入パティ 

proc `~` [ A ] ( a : A ): ref A = new ( result ) result [] = a     
  
    

バリアントリスト[ A ] : Nil Cons ( x : A , xs : refリスト[ A ] ) 
  
      

proc listHelper [ A ] ( xs : seq [ A ] ): List [ A ] = if xs . len == 0 : Nil [ A ] () else : Cons ( xs [ 0 ] , ~ listHelper ( xs [ 1 .. xs . high ] ))    
      
      

proc list [ A ] ( xs : varargs [ A ] ):リスト[ A ] = listHelper ( @ xs )     

proc sum ( xs : List [ int ] ): int = ( block : match xs : Nil : 0 Cons ( y , ys ): y + sum ( ys [] ) )     
   
     
        


エコー合計(リスト( 1 、2 、3 、4 、5 ) )     

Scala 3では列挙型が追加され、^[4]以前のScalaの例をより簡潔に書き直すことができるようになりました。

enum Tree [ + T ]: case Leaf case Node ( x : Int 、左: Tree [ T ]、右: Tree [ T ]) 
   
        

enum Shape ( centerX : Int 、centerY : Int ): case Square ( side : Int 、centerX : Int 、centerY : Int )はShape ( centerY 、centerX )を拡張しますcase Rectangle ( length : Int 、height : Int 、centerX : Int 、centerY : Int )はShape ( centerX 、centerY )を拡張しますcase Circle ( radius : Int 、centerX : Int 、centerY : Int )はShape ( centerX 、centerY )を拡張します    
           
             
           

Rust言語は、列挙型と呼ばれるタグ付き共用体を幅広くサポートしています。^[5]例えば：

列挙型 Tree { Leaf 、Node ( i64 、Box < Tree > 、Box < Tree > ) } 
    
      

また、ユニオンでのマッチングも可能になります。

treeをTree :: Node ( 2 、Box :: new ( Tree :: Node ( 0 、Box :: new ( Tree :: Leaf ))) , Box :: new ( Tree :: Node ( 3 、Box :: new ( Tree :: Leaf ) ) , Box :: new ( Tree :: Node ( 4 、Box :: new ( Tree :: Leaf ) ) , Box :: new ( Tree :: Leaf ) ) )) ) ) ;   
    
      
     
          


fn  add_values ( tree : Tree )  -> i64  {
マッチツリー{ Tree :: Node ( v , a , b ) => v + add_values ( * a ) + add_values ( * b )、Tree :: Leaf => 0 } }      
                
          
    


assert_eq! ( add_values (ツリー), 9 ); 

Rustのエラー処理モデルは、これらのタグ付き共用体、特に またはのOption<T>いずれかである 型とまたは のいずれかである型に大きく依存しています。^[6]NoneSome(T)Result<T, E>Ok(T)Err(E)

Swiftは列挙型によるタグ付き共用体のサポートも充実しています。^[7]例えば:

enum  Tree  { 
    case  leaf
    間接 case  node ( Int ,  Tree ,  Tree ) 
}

 tree  =  Tree . node ( 
    2 、
    . node ( 0 、 . leaf 、 . leaf ) 、
    . node ( 3 、 . leaf 、 . node ( 4 、 . leaf 、 . leaf ) 
)とします。

func  add_values ( _  tree :  Tree )  ->  Int  { 
    switch  tree  { 
    case  let  . node ( v ,  a ,  b ): 
        return  v  +  add_values ( a )  +  add_values ( b )

    case  .leaf : 0を返す} }
         
    


アサート( add_values (ツリー)  ==  9 )

TypeScriptでは、タグ付きユニオンを作成することもできます。例:

インターフェースLeaf { kind : "leaf" ; }     

インターフェースNode { kind : "node" ; value : number ; left : Tree ; right : Tree ; }           

タイプツリー=リーフ|ノード     

const root : Tree = { kind : "node" 、value : 5 、left : { kind : "node" 、value : 1 、left : { kind : "leaf" }, right : { kind : "leaf" } }, right : { kind : "node" 、value : 3 、left : { kind : "leaf" }, right : { kind : "node" 、value : 4 、left : { kind : "leaf" }, right : { kind : "leaf" } } } }    
   
   
   
     
     
        
        
  
   
     
     
        
     
       
       
          
          
    
  


関数visit ( tree : Tree ) { switch ( tree . kind ) { case "leaf" : break case "node" : console . log ( tree . value ) visit ( tree . left ) visit ( tree . right ) break } }   
      
         
            
         
            
            
            
             
     

Python 3.9では、タグ付きユニオン型を定義するために使用できる型付け注釈のサポートが導入されました（PEP-593 ^[8]）。

通貨 = 注釈付き[ 
    TypedDict ( '通貨' ,  { 'ドル' :  float ,  'ポンド' :  float },  total = False ), 
    TaggedUnion , 
]