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 1


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).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.