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

  • 3
    I would say that Type3 is homomorphic to Type4 and Type1 is isomorphic to Type2. en.wikipedia.org/wiki/Homomorphism – Giorgio Nov 18 '17 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. – Giorgio Nov 18 '17 at 12:15
  • 1
    @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 – Christophe Nov 18 '17 at 13:45
up vote 7 down vote accepted

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.) – cmeeren Nov 19 '17 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. – Giorgio Nov 19 '17 at 11:30

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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