Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Algebraic data type equivalent in C

Tags:

c

types

I'm writing a program that reads a stream of data and parses it into some values: either integers, floats, characters, or a compound value that contains a set of values (can be nested). How could I represent that in C? I was thinking of an union of int, float, char, then having an array of pointers to such unions for the compound value, but that can't be nested.

like image 544
Igor Avatar asked Aug 30 '10 19:08

Igor


2 Answers

(I'm imagining that you are parsing an Xml file)

We'll assume that you have a bunch of nodes. Each node can have a value, it can be one of a set of sibling, and it could have children. That would give you a struct like:

 struct Node
 {
       DATA Value;
       DATATYPE  Type;
       Node* nextSibling;
       Node* firstChild;
 };

DATA could be a union like you described, or separate variables. However, since you will reading values from it in the same form as you stored them, a union should be fine. DATATYPE should be an enum.

like image 182
James Curran Avatar answered Sep 27 '22 23:09

James Curran


You mean char and not char[]? All char values can be stored in an int. For that matter, it's a safe bet that all the int values you want (and all possible int values on your machine) can be represented exactly by double.

So, I recommend a tree structure with double payloads in the nodes. Use an enum to discriminate the type, if necessary. You can represent an n-ary tree using a single child pointer and a single linked-list "next" pointer… Wikipedia has a diagram somewhere but I can't find it :v( .

like image 27
Potatoswatter Avatar answered Sep 27 '22 23:09

Potatoswatter