이 Haskell 유형을 C:
에서 어떻게 표현하는지는 즉각적으로 명확하지 않습니다.

data Tree = Leaf Int | Inner Tree Tree

Haskell이나 Rust와 같은 언어와 달리 C에는 다음 기능이 내장되어 있지 않습니다.
분리된 조합. 그러나 약간의 추가 입력을 하려는 경우 이를 표현하는 데 필요한 모든 요소를 ​​제공합니다.

가장 먼저 깨달아야 할 점은 분리된 공용체는 다음으로 구성된다는 것입니다.

• 다양한 변형
• 각 항목에는 데이터가 연결되어 있습니다.

이진 트리 예에는 "리프"와 "내부"라는 두 가지 변형이 있습니다. 리프 변형은 단일 정수(해당 데이터)를 저장하고 내부 변형은 두 개의 트리(왼쪽 및 오른쪽 자식을 나타냄)를 저장합니다.

두 개의 필드가 있는 구조체를 사용하여 C에서 이러한 동물을 표현할 수 있습니다.

1. 어떤 변형이 표현되고 있는지 나타내는 "유형 태그"(일반적으로 정수)입니다.
2. 변형과 관련된 데이터를 저장하는 데이터 필드입니다.

열거형을 사용하여 다양한 변형 유형 태그를 정의하는 것이 편리합니다.

enum tree_type {
        TREE_LEAF,
        TREE_INNER,
};

데이터 저장은 어떻게 되나요? 이것이 공용체가 해결하기 위해 존재하는 문제 유형입니다.

노동조합

공용체는 다양한 유형의 데이터를 저장할 수 있는 메모리 덩어리입니다. 예를 들어, 다음은 32비트 정수 또는 5개 문자 배열을 저장할 수 있는 공용체입니다.

union int_or_chars {
        int num;
        char letters[5];
};

Union int_or_chars 유형의 변수는 특정 시간에 int 또는 5개의 문자 배열을 보유할 수 있습니다(동시에 둘 다를 보유할 수는 없음):

union int_or_chars quux;

// We can store an int:
quux.num = 42;
printf("quux.num = %d\n", quux.num);
// => quux.num = 42

// Or 5 chars:
quux.letters[0] = 'a';
quux.letters[1] = 'b';
quux.letters[2] = 'c';
quux.letters[3] = 'd';
quux.letters[4] = 0;
printf("quux.letters = %s\n", quux.letters);
// => quux.letters = abcd

// But not both. The memory is "shared", so the chars saved above are
// now being interpreted as an int:
printf("quux.num = %x\n", quux.num);
// quux.num = 64636261

return 0;

int_or_chars 유니온과 같은 유니온은 가장 큰 멤버를 수용할 수 있을 만큼 큰 메모리 덩어리를 처리할 수 있습니다. 이것이 어떻게 작동하는지 보여주는 도식은 다음과 같습니다.

  ----   ----   ----   ----   ----  
| byte |      |      |      |      |
  ----   ----   ----   ----   ----  
||
||

quux에 문자 배열을 저장한 후 quux.num을 인쇄하면 "쓰레기"가 발생하는 이유를 설명하는 데 도움이 됩니다. 그것은 쓰레기가 아니라 정수로 해석되는 문자열 "abcd"였습니다. (내 컴퓨터에서 quux.num은 64636261로 16진수로 인쇄됩니다. 문자 'a'는 ASCII 값 0x61, 'b' 값은 0x62, 'c'는 0x63, 'd'는 0x64입니다. 내 프로세서가 리틀 엔디안이므로 순서가 반대입니다.)

공용체에 대한 마지막 참고 사항으로, sizeof:
로 보고된 크기에 놀랄 수도 있습니다.

printf("%ld\n", sizeof(union int_or_chars));
// => 8

내 컴퓨터에서 Union int_or_chars 유형의 크기는 예상했던 것보다 5바이트가 아니라 8바이트입니다. 내 프로세서 아키텍처에 규정된 정렬 요구 사항으로 인해 일부 패딩이 추가되었습니다.

이진 트리로 돌아가기

이제 이진 트리 유형을 Haskell에서 C로 계속 변환할 준비가 되었습니다. 변형 유형을 나타내는 열거형을 이미 정의했습니다. 이제 데이터를 저장하기 위한 공용체가 필요합니다:

union tree_data {
        int leaf;
        struct inner_data inner;
};

여기서 struct inner_data는 "내부" 변형의 왼쪽 및 오른쪽 하위 항목을 포함하는 구조체입니다.

struct inner_data {
        struct tree *left;
        struct tree *right;
};

"내부" 변형은 왼쪽 및 오른쪽 하위 항목에 대한 포인터를 유지합니다. 그렇지 않으면 구조체 트리의 크기가 고정되지 않기 때문에 간접 참조가 필요합니다.

이러한 조각을 준비하면 트리 유형을 정의할 준비가 되었습니다.

enum tree_type {
        TREE_LEAF,
        TREE_INNER,
};

struct tree;
struct inner_data {
        struct tree *left;
        struct tree *right;
};

union tree_data {
        int leaf;
        struct inner_data inner;
};

// A representation of a binary tree.
struct tree {
        enum tree_type type;
        union tree_data data;
};

나무와 놀기

트리를 구성하는 몇 가지 함수를 작성해 보겠습니다.

// Construct a leaf node.
struct tree *leaf(int value) {
        struct tree *t = malloc(sizeof(*t));
        t->type = TREE_LEAF;
        t->data.leaf = value;
        return t;
}

// Construct an inner node.
struct tree *inner(struct tree *left, struct tree *right) {
        struct tree *t = malloc(sizeof(*t));
        t->type = TREE_INNER;
        t->data.inner.left = left;
        t->data.inner.right = right;
        return t;
}

그리고 인쇄하세요:

void print_tree(struct tree *t) {
        switch (t->type) {
        case TREE_LEAF:
                printf("%d", t->data.leaf);
                return;
        case TREE_INNER:
                printf("(");
                print_tree(t->data.inner.left);
                printf(" ");
                print_tree(t->data.inner.right);
                printf(")");
                return;
        }
}

이를 통해 하스켈 표현식을 번역할 수 있습니다:

Inner (Inner (Leaf 1) (Leaf 2)) (Leaf 3)

C로 다음과 같이:

inner(inner(leaf(1), leaf(2)), leaf(3));

예를 들어:

struct tree *t = inner(inner(leaf(1), leaf(2)), leaf(3));
print_tree(t);
// => ((1 2) 3)

좀 더 흥미로운 예로, 깊이 우선 검색 기능을 번역해 보겠습니다.

-- Check if a value is in a tree.
search :: Int -> Tree -> Bool
search v (Leaf w) = v == w
search v (Inner l r) = search v l || search v r

트리 유형 사용:

// Check if a value is in a tree.
int search(int value, struct tree *t) {
        switch (t->type) {
        case TREE_LEAF:
                return t->data.leaf == value;
        case TREE_INNER:
                return (
                        search(value, t->data.inner.left) ||
                        search(value, t->data.inner.right)
                );
        }
}

확실히 더 장황하지만 번역 과정은 간단합니다(컴파일러가 이런 종류의 작업을 수행할 수 있을 정도라면...).

트레이드오프

대체 표현과 관련된 장단점에 대해 약간의 여담으로 마무리합니다. 구체적으로 다음과 같이 가정합니다.

union tree_data {
        int leaf;
        struct inner_data inner;
};

우리는 다음을 사용했습니다:

union tree_data {
        int leaf;
        struct inner_data *inner;
        //                ^ The difference.
};

첫 번째 경우 공용체에는 구조체 inner_data가 포함되어 있는 반면, 두 번째 경우에는 이 구조체에 대한 포인터를 저장합니다. 결과적으로 첫 번째 공용체는 16바이트로 약간 더 크며, 내 컴퓨터의 포인터 버전은 8바이트입니다. 불행하게도 영향을 받는 것은 내부 노드만이 아닙니다. 리프 노드는 이와 동일한 16바이트 공용체를 사용하지만 단일(4바이트) int만 저장합니다. 좀 낭비적인 느낌이네요.

그러나 이것이 전부는 아닙니다. 내부 노드의 왼쪽 및 오른쪽 하위 항목에 액세스할 때마다 추가 간접 비용을 지불하게 됩니다. 특히 가리키는 메모리가 캐시되지 않은 경우 읽기 비용이 반드시 저렴하지는 않습니다.

여기에 제시된 주요 접근 방식이 대부분의 경우 더 나은 출발점이 될 것이라고 생각하며 몇 바이트를 줄이려는 노력(추가 읽기가 발생하는 흰색)은 그렇게 될 때까지 그만한 가치가 없다고 생각합니다.