# How to represent a map data structure mathematically

Wondering how to represent a map object such as the following mathematically:

var foo = {
a: 10,
b: 'bar',
c: true
}


You could say that it was a function like this:

foo(x, y, z)


where $x$ is an integer, $y$ is a string, and $z$ is a boolean. But the question then is how to say the names of the keys a, b, c. Something like:

foo(label(x, a), label(y, b), label(z, c))


But then wondering about how type theory deals with this, so I' a bit confused. Wondering how computer science would model this data structure using mathematical notation. Maybe:

\begin{align*} foo = \left\{ \begin{array}{r@{}l} & a = x \\ & b = y \\ & c = z \end{array} \right\} \end{align*}

## 1 Answer

There are multiple ways to represent it.

The simplest way is probably as a mathematical function $f:S \to T$ where $S$ is the type of the keys and $T$ is the type of the values. In other words, you can represent it as a function/map. Here we have $f(\mathtt{a}) = 10$, etc. (so this is different from the idea you mentioned in the question).

Here are some more sophisticated ways to encode this in a type system:

If the keys a, b, c, are statically known and never dynamic, and that set is fixed in advance and never changes, this could be represented as simply a tuple or a record type.

If the keys are static but you want to extend them, you could represent this as an extensible row type. See also In type systems, is there a name for SQL's way of cutting and combining record types into new types? and Is there any difference between extensible records and dependent maps and Encoding row types.

If the keys are fully dynamic (their possible values aren't known at compile time), it needs to be represented as a function (i.e., map type).