関数型プログラミングを学ぶ際に登場することのある単語として「代数的データ型」というものがあり、直和型はこの代数的データ型の一種である。
代数的データ型において、「列挙型はCの列挙体(enum
)、直積型はCの構造体(struct
)に相当する」という説明に関しては概ね異論はないのだが、その中で一つだけ、「直和型はCの共用体(union
)に相当する」という説明だけはかなり違和感のある説明だと思ったため、今回、テーマとして「直和型をC共用体だと説明するのは誤解を生むだけ」という主張を書いていこうと思った次第である。
「代数的データ型」、そして「直和型」とは何か
代数的データ型は、非常にざっくりと説明すれば、型を集合的に表現する複合型である。
たとえば、Haskellで「Int
かつString
である型」を持つ場合、以下のように定義することができる。
data IntAndStr = IntAndStr Int String
これは意味論的には、IntAndStr
型はInt · String
であることによって成り立つ型であることを示している。ここからIntAndStr
型の値はInt
型とString
型の両方の情報を持っていなければ作ることができないことがわかる。
ちなみに、こうした「T1
かつT2
でなければ成り立たない型」を直積型と言い、直積型は「型を論理積的に表したものである」と考えることができる。
そして直和型とは、直積型の論理和版・・・ではない。なぜかと言うと、直和型では「T1
型とT2
型の両方の情報を持つ場合」は成り立たないからである。
Haskellで直和型を定義してみるとわかる。Haskellで直和型を定義するには、以下のようにする。
data IntXorStr = Int_ Int | Str String
そしてInt_ 0
やStr "string"
などと書くことでどちらか片方の型情報を持つ値を表現することができる。しかし、どちらの型情報もある値として表現することはできない。
以上から直和型は「T1
かT2
どちらかでなければ成り立たない」わけで、これは論理和(T1 + T2
)的ではなく、排他的論理和(T1 ⊕ T2
)的であると言うべきである。
したがって、直和型は「型を排他的論理和的に表したものである」と考えられる。
<2021/12/27 追記>
「排他的論理和」的になるのは型が2つであった場合の話であり、型が2つだった場合が偶然「排他的論理和」となっていただけの話である(排他的論理和として考えた場合3つ以上の入力において、奇数個の型を持つ場合もすべて成り立ってしまう)。したがって、直和型は、その名の通り「型を直和的に表したもの」と認識したほうが良い。自分なりにわかりやすい解釈をまとめたので以下を参照のこと。
opaupafz2.hatenablog.com
補足として、代数的データ型には直積型、直和型だけでなく、列挙型も存在する。これは複数の値を列挙した型である。直積型、直和型とは違い、列挙型には型情報がない(0個の型情報を持つ、と解釈することもできるが)。
たとえばHaskellで赤信号、黄信号、青信号を表現する型を定義すると、以下のようになる。
data TrafficLight = Red | Yellow | Green
Cの共用体とは
Cの共用体は「T1
型としてもT2
型としても表現できる型」であると考えられる。
たとえば、uint32_t
型とuint8_t[4]
型の値を表現できる共用体を考えてみる。
#include <stdint.h> typedef union { uint32_t byte4; uint8_t bytes[4]; } byte4_t;
共用体として定義されたbyte4_t
型は、uint32_t
型の値としても使えるし、uint8_t[4]
型の値としても使える。
#include <stdio.h> int main(void) { // uint32_t型の値として宣言した byte4_t b4 = { .byte4 = 100L }; // uint32_t型として使うこともできれば printf("%ld\n", b4.byte4); // uint8_t[4]型として使うこともできる printf("0x"); for (size_t i = 0; i < 4; ++i) { printf("%02x", b4.bytes[i]); } printf("\n"); return 0; }
これはたとえば32bitの値を8bit単位でも表現したい場合に役に立つ。32bitの値のうち、8bitだけを読み書きしたい場合、32bitの値だけでは不便である。
そこで共用体を使うことで、より柔軟に値を表現することが可能となる。ただしエンディアンについて気にしなければならないという欠点もあり、基本的に中~上級者が使うテクニックではないかと思われる。
Cの共用体で表現する「直和型」
まず、Cの共用体「だけ」では、直和型を表現することは不可能である。なぜかというと、直和型は「T1
かT2
のどちらかでなければならない」型であるのに対し、Cの共用体は「T1
とT2
のどちらでも良い」型であるためである。「T1
かT2
のどちらかである」と「T1
でありT2
でもある」とではまったく話が違う。
ここが違和感を覚える部分であり、「直和型を『C共用体に相当する』と説明してしまうことで誤解を生むのではないか」と懸念しているところである。
しかし、「Cで直和型を表現することは可能か?」と問われれば、「データ構造としては」可能である。
まずCの共用体は「タグなし共用体」と呼ばれ、この共用体は型の区別ができない。だから共用体は「T1
であり、T2
でもある」としか表現できない。
そこで、タグという情報を付け加えることで、Cの共用体は「タグ付き共用体」となり、型の区別が可能となる。Cによるタグ付き共用体の例を以下に示す。
#include <stdint.h> // 型情報となるタグ typedef enum { INT, STR } int_xor_str_types_t; // タグ付き共用体 typedef struct { int_xor_str_types_t types; // 型情報 union { int32_t int_; // int型の値 int8_t str[1024]; // string型の値 } int_xor_str; } int_xor_str_t;
これだけではタグ付き共用体を直和型として使うとき、使う側は「今はどの型として使っているのか」ということまで調べなければならない。そこでタグ付き共用体を直和型として扱うための関数を用意する。
#include <stddef.h> #include <stdint.h> #include <string.h> /** * int型として値を生成する */ int_xor_str_t init_int(int32_t init_value) { return (int_xor_str_t){ .types = INT, .int_xor_str = { .int_ = init_value } }; } /** * string型として値を生成する */ int_xor_str_t init_str(const int8_t *init_value, size_t size) { int_xor_str_t self = { .types = STR }; if (size >= 1024) { strncpy(self.int_xor_str.str, init_value, 1023); self.int_xor_str.str[1023] = '\0'; } else { strncpy(self.int_xor_str.str, init_value, size); self.int_xor_str.str[size] = '\0'; } return self; } /** * int型として値を取得する */ int32_t get_int(int_xor_str_t *self) { if (self->types == INT) { return self->int_xor_str.int_; } else { return 0; } } /** * string型として値を取得する */ int8_t *get_str(int_xor_str_t *self) { if (self->types == STR) { return self->int_xor_str.str; } else { return NULL; } } /** * int型として値を格納する */ int set_int(int_xor_str_t *self, int32_t set_value) { if (self->types == INT) { self->int_xor_str.int_ = set_value; return 0; } else { return -1; } } /** * string型として値を格納する */ int set_str(int_xor_str_t *self, const int8_t *set_value, size_t size) { if (self->types == STR) { if (size >= 1024) { strncpy(self->int_xor_str.str, set_value, 1023); self->int_xor_str.str[1023] = '\0'; } else { strncpy(self->int_xor_str.str, set_value, size); self->int_xor_str.str[size] = '\0'; } return 0; } else { return -1; } }
このようにしてやっとCの共用体は直和型と同等に扱える。「『データ構造としては』可能」と強調して書いたのはこのためである。
まとめ
以上から、Cにおいて直和型は「共用体を使ってデータ構造を作れば」実現することが可能であることは確かであるものの、これを「直和型はC共用体に相当」と言うのはさすがに無理がある。
以上から、自分は直和型を説明する際に「C共用体に相当する」という説明とは別のアプローチで説明したほうが誤解がなくて済むと考えている。