# What is the term for different types that contain the same information?

What is the correct term(s) for different types that contain exactly the same information? For example (F#):

``````type Type1 = (int * string)
type Type2 = (string * int)
``````

When describing that these types can contain exactly the same information, I could say that `Type1` and `Type2` are ______. Which word(s) could I use?

And is there a corresponding term for types that are similar, but not exactly so? For example:

``````type Type3 = Map<string, int>
type Type4 = (string * int) list
``````

There is a "lossless" mapping from `Type3` to `Type4`, but not the other way around (a `Map` can only contain unique keys, whereas `Type4`, being a list, has no such restriction).

I'll accept an answer that provides relevant terms along with some credibly sourced definition (or convinces me that there are no relevant terms).

• I would say that `Type3` is homomorphic to `Type4` and `Type1` is isomorphic to `Type2`. en.wikipedia.org/wiki/Homomorphism Nov 18, 2017 at 11:47
• I guess in you example both concepts (homomorphism and isomorphism) can be expressed in terms of functors in an appropriate category whose objects are types. I tried to write up a detailed answer but I lack the knowledge to write something sensible. I am curious to see what answers you get. Nice question. Nov 18, 2017 at 12:15
• @Giorgio your answer is very accurate: isomorphic means that there is a one to one correspondence, homomorphic means the relations are preserved. I'll upvote when you post the answer Nov 18, 2017 at 13:45

Let's start with `Type3` and `Type4`. I assume that the "lossless" mapping you have in mind is the library function `toList`. This will just map a `Map` to a corresponding `List` containing all key / value pairs from the map. However, this mapping is not enough. You also need to transform all functions involving `Type3` to structure-preserving functions involving `Type4`. I will try a formal definition but, as said in my comment, I would like someone with more knowledge on this topic to write a better answer.

So, formally, given two types `T1` and `T2`, a homomorphism `h : T1 -> T2` is a pair `(d, f)`, where `d : T1 -> T2` maps all values in `T1` to values in `T2`, and `f : (T1 -> T) -> (T2 -> T)` maps any function `t : T1 -> T` to a new function `f t = t' : T2 -> T`, such that `t = (f t) . d`.

This means that `d` maps the data representation from type `T1` to a representation of type `T2`, while `f` maps all functions on `T1` to functions on `T2` in a way that preserves the structure.

In your example, `T1 = Map<string, int>`, `T2 = (string * int) list`, and `d = toList`. For all types `T`, the function `f` should map any function `t : Map<string, int> -> T` to a function `f t : (string * int) list -> T` in such a way that `t m = (f t) (d m)` for each map `m`.

For example, the function `isEmpty : Map<string, int> -> bool` should be mapped to `f isEmpty = isEmpty'` in such a way that if `isEmpty m` is equivalent to `isEmpty' (d m)`. In words: if `isEmpty` tells you that a map is empty, then `isEmpty'` should tell you that the corresponding list representation is empty as well.

Once you have both mappings (on data and on functions), you can say that the first type is homomorphic to the second. Two types are isomorphic if there are homomorphisms in both directions.

For your first example, the data mapping function `d : (int * string) -> (string * int)` is `d (i, s) = (s, i)` and, for all type `T` and functions `t : (int * string) -> T`, you can define `t' = f t : (int * string) -> T` by letting `t' (i, s) = t (s, i)`. In this way, you can see that `Type1` is homomorphic to `Type2`. By defining similar functions in the other direction you can see that `Type2` is homomorphic to `Type1`. Therefore the two types are isomorphic.

• Thanks. AFAICS all possible functions on `Map<string, int>` should be mappable to corresponding functions on `(string * int) list`, just as the type itself can be mapped (but not in the other direction). Is this correct (and can it be proved easily), and does that mean that `Map<string, int>` is homomorphic to `(int * string) list`? (You never state that explicitly.) Nov 19, 2017 at 11:10
• "Is this correct (and can it be proved easily), and does that mean that Map<string, int> is homomorphic to (int * string) list?": Yes, this is what I meant with the definition of homorphism: a pair of functions, the first (`d`) mapping data values, and the second (`f`) mapping functions on the original data to function on the target data. To prove formally that such a function `f` exists for `Map<string, int>` and `(string * int) list` can be verbose (no idea, I didn't try), but it should be feasible. Nov 19, 2017 at 11:30