Qual è il termine per diversi tipi che contengono le stesse informazioni?

2

Qual è il / i termine / i corretto / i per diversi tipi che contengono esattamente le stesse informazioni? Ad esempio (F #):

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

Quando si descrive che questi tipi possono contenere esattamente le stesse informazioni, potrei dire che Type1 e Type2 sono

posta cmeeren 18.11.2017 - 12:36
fonte

1 risposta

7

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.

    
risposta data 18.11.2017 - 16:19
fonte

Leggi altre domande sui tag