Iniziamo con Type3
e Type4
. Suppongo che la mappatura "senza perdita" che hai in mente sia la funzione di libreria toList
. Questo mapperà solo un Map
a un List
corrispondente contenente tutte le coppie chiave / valore dalla mappa. Tuttavia, questa mappatura non è sufficiente. È inoltre necessario trasformare tutte le funzioni che coinvolgono Type3
in funzioni di conservazione delle strutture che coinvolgono Type4
.
Proverò una definizione formale ma, come detto nel mio commento, vorrei che qualcuno con più conoscenza su questo argomento scrivesse una risposta migliore.
Quindi, formalmente, dato due tipi T1
e T2
, un omomorfismo h : T1 -> T2
è una coppia (d, f)
, dove d : T1 -> T2
mappa tutti i valori in T1
in valori in T2
e f : (T1 -> T) -> (T2 -> T)
associa qualsiasi funzione t : T1 -> T
a una nuova funzione f t = t' : T2 -> T
, tale che t = (f t) . d
.
Ciò significa che d
mappa la rappresentazione dei dati dal tipo T1
a una rappresentazione di tipo T2
, mentre f
associa tutte le funzioni su T1
a funzioni su T2
in un modo che preserva il struttura.
Nel tuo esempio, T1 = Map<string, int>
, T2 = (string * int) list
e d = toList
. Per tutti i tipi T
, la funzione f
deve mappare qualsiasi funzione t : Map<string, int> -> T
a una funzione f t : (string * int) list -> T
in modo che t m = (f t) (d m)
per ogni mappa m
.
Ad esempio, la funzione isEmpty : Map<string, int> -> bool
deve essere mappata a f isEmpty = isEmpty'
in modo che se isEmpty m
è equivalente a isEmpty' (d m)
. In parole: se isEmpty
ti dice che una mappa è vuota, allora isEmpty'
dovrebbe dirti che anche la rappresentazione della lista corrispondente è vuota.
Una volta che hai entrambi i mapping (sui dati e sulle funzioni), puoi dire che il primo tipo è omomorfo al secondo.
Due tipi sono isomorfi se ci sono omomorfismi in entrambe le direzioni.
Per il tuo primo esempio, la funzione di mappatura dei dati d : (int * string) -> (string * int)
è d (i, s) = (s, i)
e, per tutti i tipi T
e funzioni t : (int * string) -> T
, puoi definire t' = f t : (int * string) -> T
lasciando t' (i, s) = t (s, i)
. In questo modo, puoi vedere che Type1
è omomorfo a Type2
. Definendo funzioni simili nell'altra direzione, puoi vedere che Type2
è omomorfo a Type1
. Pertanto i due tipi sono isomorfi.