È possibile definire elenchi in modo speciale in modo che contengano cose di tipo diverso?

cs.stackexchange https://cs.stackexchange.com/questions/129264

Domanda

In https://www.seas.harvard.edu/courses/cs152/2019sp/lectures/lec18-monads.pdf è scritto così

Un tipo $ au$ list è il tipo di elenchi con elementi di tipo $ au$

Perché una lista deve contenere elementi dello stesso tipo?Perché non può contenere elementi di tipo diverso?Esiste un modo per definire una lista polimorfica nel lambda calcolo tipizzato, in modo che prenda elementi di qualsiasi tipo?

Possiamo quindi utilizzare la monade List su liste, definite polimorficamente?

È stato utile?

Soluzione

La risposta breve è quella $ \ tau \ \ text {list} $ è definito come un costruttore di tipo, insieme alle regole per Formazione ed eliminazione, e così abbiamo potuto aspettare Definisci un costruttore di tipo che ha permesso i termini di diversi tipi di formare un singolo "elenco variabilmente digitato". Tuttavia, gli elenchi non possono assumere tipi diversi nella definizione indicata, semplicemente perché sono definiti rispetto a un singolo tipo. In entrambi i casi, aggiungendo liste o elenchi o elenchi in modo variabile, prevede l'estensione della semplice class $ \ Lambda $ -calculus, come elenchi di qualsiasi il tipo non esiste nella presentazione abituale.

Se disponiamo di un sistema di tipo leggermente più ricco rispetto alla semplice class $ \ Lambda $ -Calculus, possiamo codificare elenchi digitati in modo variabile utilizzando standard $ \ tau \ \ text {list} $ s

    .
  • Se abbiamo una forma di sottotyping , possiamo memorizzare i termini di diversi tipi, come finché condividono un supertipo. Tuttavia, quando proiettiamo gli elementi fuori dalla lista, non possiamo più dire specificamente quale tipo dovesse iniziare (questo potrebbe avere familiarità dalla programmazione orientata agli oggetti), quindi questo è un po 'limitato.
  • Se abbiamo Tipi di somma dipendenti (chiamato anche $ \ sigma $ -types) e un Tipo universo $ \ Mathcal U $ (cioè un "tipo di tipi"), possiamo formare il tipo $ ( \ Sigma_ {A: \ mathcal u} A) \ \ text {list} $ , i cui elementi sono coppie composte da un tipo $ A $ e a termine di quel tipo.

Infine, noto che il polimorfismo non ci aiuta se vogliamo elenchi eterogenei: ci consente solo di manipolare gli elenchi omogenei per diversi $ \ tau $ in modo più efficace. I tipi polimorfi devono essere uniforme in un certo senso, motivo per cui abbiamo bisogno di dipendenza qui. < / P >.

.

Per rispondere a una domanda di follow-up: se disponiamo di due elenchi variabili in ordine utilizzando l'approccio di tipo dipendente, possiamo concatenare e appiattire elenchi come con elenchi ordinari.

    .
  • la $ \ mathrm {list} $ monad ha un'operazione $ \ mathrm {join} $ (nella lingua di Haskell), ha dato un elenco di liste di elenchi digitati in modo variabile, $$ l= [[A, A), (B, B)], [(c , c), (d, d)]]: (\ sigma_ {x: \ mathcal u} x) \ \ text {list list} $$ possiamo eseguire $ \ mathrm {join} $ per ottenere una nuova lista: $$ \ mathrm {join} (l)= [a, a), (b, b) , (C, c), (d, d)]: (\ sigma_ {x: \ mathcal u} x) \ \ text {list} $$
  • Allo stesso modo, $ \ tau \ \ text {list} $ può essere equipaggiato con un'operazione di concatenazione $ + \! + $ , quindi dato le due liste nell'esempio precedente, possiamo concatenarli per un risultato simile: $$ [(A, A), (B, B)] \ {+ \! +} \ [(c, c), (d, d)]= [(a , a), (B, B), (c, c), (d, d)]: (\ sigma_ {x: \ mathcal u} x) \ \ text {list} $$

Altri suggerimenti

No, non è possibile, almeno non in modo utile.Pensa a cosa sarebbe il tipo di generacoloDicetagcode.Quando ogni elemento ha lo stesso tipo, head ha il tipo $ \ Tau \;\ mathsf {list} \ to \ tau $ .Senza tale garanzia, non ci sarebbe il modo di scrivere un tipo coerente per head.Per il tipo di elenco è utile, vogliamo essere in grado di trarre conclusioni utili su ciò che il tipo di output di head è;e ciò richiede che tutti gli elementi dell'elenco abbiano lo stesso tipo.

Suppongo che tu possa Definire un "elenco" un altro modo, ma non sarebbe utile (non è possibile ragionare il tipo di valori che lo esci con head)o non corrisponderebbe a qualcosa che gli scienziati informatici chiamerebbero una "lista".

Non è possibile definire utilmente un tipo $\mathsf{lista}$ che non indica il tipo dei suoi elementi.Ciò non significa che non puoi avere elenchi che contengono cose di diverso tipo:è ancora un $ au \, \mathsf{lista}$, ma puoi inserire la parte "contenere cose di diverso tipo" nel file $ au$.

(Queste idee di base erano già presenti D.W. E varkorle risposte.È importante rendersi conto che queste risposte non sono contraddittorie!Stanno esaminando diversi aspetti del quadro più ampio.)

Se il sistema dei tipi consente di definire un tipo $\mathsf{lista}$ che può contenere elementi di qualsiasi tipo, considera quindi il tipo restituito di un distruttore simile $\mathsf{testa}$ O $\mathsf{ennesimo}$, o il tipo dell'argomento della funzione $\mathsf{fold}$.Non hai informazioni sul tipo degli elementi, quindi dovrebbero consentire qualsiasi tipo.Ciò significa che ad es $\lambdax.\mathsf{testa}(\mathsf{contro}(x, \mathsf{nil}))$ non ti restituirà un valore dello stesso tipo di $x$ (O $x \, \mathsf{opzione}$, affinché $\mathsf{testa}$ può ritornare $\mathsf{Nessuno}$ su elenchi vuoti).Ma allora da cosa torni? $\mathsf{testa}$?

  • Se $\mathsf{testa}$ consente al chiamante di specificare qualsiasi tipo restituito, quindi il sistema dei tipi è praticamente inutile, poiché consente coercizioni arbitrarie tra tipi attraverso $\lambdax.\mathsf{testa}(\mathsf{contro}(x, \mathsf{nil}))$.È inutile per la logica dal momento che Corrispondenza Curry-Howard mappa una coercizione arbitraria tra tipi in modo che ogni proposizione implichi ogni altra proposizione, quindi hai una logica incoerente.
  • In caso contrario, non è possibile recuperare un valore del tipo originale $\lambdax.\mathsf{testa}(\mathsf{contro}(x, \mathsf{nil}))$.Quindi potresti essere in grado di creare elenchi, ma non puoi estrarne elementi.

Un esempio di vita reale che in realtà dimostra entrambi i comportamenti di cui sopra è prime versioni Di Giava, prima che lo fosse generici.Java ha sia un sistema di tipi statici che un sistema di tipi dinamici.Nel sistema di tipi statici, qualsiasi valore può essere impostato in modo trasparente Object, Perché Object è considerato un supertipo di tutto.Quindi puoi inserire qualsiasi valore in a List.Ma ciò che ne ottieni è il valore originale a cui attribuisci Object, non il valore originale stesso.Nel sistema di tipi dinamici, puoi forzare qualsiasi tipo a qualsiasi altro tipo, quindi in pratica, per ottenere un valore da un elenco, lo devi forzare al tipo desiderato.Ma avere coercizioni vanifica lo scopo di un sistema di tipi.Questo problema è il motivo principale per cui Java ha acquisito i generici:permettono alla lingua di avere $ au \, \mathsf{lista}$ invece di $\mathsf{lista}$ (o nella notazione Java, List<T> invece di List).

Solo perché una lista ha un tipo di elementi —$ au \, \mathsf{lista}$ è un elenco di elementi di tipo $ au$ — non significa che non puoi organizzare l'inserimento di valori di tipo diverso nello stesso elenco.Praticamente qualsiasi linguaggio che consente di definire un tipo di elenco lo fa consentendo tipo di dati algebrico definizioni, qualcosa del genere:$$ au \, \mathsf{list} ::= \mathsf{nil} \mid \mathsf{cons} \: au\:( au \, \mathsf{lista}) $$Supponiamo di voler inserire sia numeri interi che stringhe nella stessa lista.Definire un tipo$$ U ::= \mathsf{I} \:\mathsf{int} \mid \mathsf{S} \:\mathsf{stringa} $$Ora $U \, \mathsf{lista}$ è il tipo di elenchi che possono contenere una combinazione di numeri interi e stringhe, ad es. $[\mathsf{I}(3), \mathsf{S}( exttt{"foo"}), \mathsf{I}(4)]$.

È possibile creare elenchi eterogenei in questo modo nella misura in cui il sistema dei tipi consente tipi eterogenei.Tieni presente che "elenchi eterogenei" non è del tutto corretto:l'elenco stesso è omogeneo:è un elenco di elementi di tipo $U$.L'eterogeneità è nel tipo $U$.Per inserire un elemento nell'elenco, si applica un costruttore di $U$ Primo.Dopo aver estratto un elemento dall'elenco, applica un distruttore di $U$ per ottenere il valore originale con il suo tipo originale.

Puoi farlo con qualsiasi tipo supportato dalla lingua.Se desideri un elenco completamente eterogeneo, hai bisogno di un linguaggio che supporti il ​​tipo "qualsiasi".Quello è Object in Giava, per esempio.I caratteri fortemente tipizzati possono avere un tipo "qualsiasi" se contengono le informazioni sul tipo necessarie in fase di esecuzione.Java lo fa continuamente.I linguaggi tipizzati staticamente (come OCaml e altri dialetti ML, Haskell, Clean, Swift o Rust) possono farlo con un $\matematica{dyn}$ tipo la cui rappresentazione runtime contiene il tipo del valore.Con un tipo del genere, $\mathsf{dyn} \, \mathsf{lista}$ è un tipo di elenco che può contenere un valore di qualsiasi tipo.Questo tipo coesiste con altri tipi di elenco come $\mathsf{int} \, \mathsf{lista}$ (dove gli elementi dell'elenco non contengono informazioni sul tipo di runtime).

Un approccio correlato alla costruzione di strutture dati eterogenee è tipi esistenziali.I tipi esistenziali consentono di creare un pacchetto di un tipo con un valore di quel tipo: $(\esiste au :P( au).a)$ Dove $a$ è un'espressione di qualche tipo $T$ tale che $P(T)$ è vero.Per esempio, $\matematica{dyn}$ può essere modellato come un caso speciale in cui $P$ è vero per tutti i tipi (un esistenziale illimitato).Un uso comune dei tipi esistenziali è dire questo $ au$ è un record, modulo o classe con alcuni elementi o metodi particolari, senza fornire tutti i dettagli:i tipi esistenziali sono un modo per modellare tipi astratti.Con un esistenziale limitato, puoi comunque fare alcune cose utili con il valore anche senza informazioni sul tipo di runtime (ad es.puoi chiamare i metodi così $P$ descrive), ma non ottenere il tipo originale.Una lista i cui elementi hanno un tipo esistenziale $T_E = (\esiste au \ldots)$ può essere vista come una lista eterogenea (perché i suoi elementi hanno tipi “reali” diversi), ma è comunque omogenea nel senso che se recuperi un valore dalla lista, tutto ciò che conosci è il suo tipo di pacchetto $T_E$.

Se la lingua ha tipi dipendenti, puoi comprimere un valore con il suo tipo in un modo che consenta di recuperare il valore originale: $\mathsf{pacchetto} ::= \sum_{ au:\mathsf{TIPO}} au$ Dove $\mathsf{TIPO}$ è il tipo dei tipi.Questo è un tipo di somma dipendente dove il primo componente sembra essere un tipo.IL $\mathsf{pacchetto}$ type è un modo per implementare esistenziali illimitati in un linguaggio tipizzato in modo dipendente.Puoi costruire esistenziali limitati aggiungendo vincoli su $ au$.Ancora una volta, è possibile costruire elenchi eterogenei nel senso che a $\mathsf{pacchetto} \, \mathsf{lista}$ contiene elementi i cui tipi "reali" sono diversi, ma la lista stessa è omogenea nel senso che ogni elemento della lista ha il tipo $\mathsf{pacchetto}$.Come con i tipi esistenziali, non è possibile estrarre un valore da una lista e recuperare direttamente il suo tipo “reale”.È possibile distruggere un valore di tipo $\mathsf{pacchetto}$ applicando la proiezione del secondo elemento, ma tutto ciò che sai del risultato è che il suo tipo è la proiezione del primo elemento: $p:\mathsf{pacchetto} \vdash \pi_2(p) :\pi_1(p)$.

Finora abbiamo visto che in un sistema di tipi non degenerati le liste sono omogenee.È possibile creare elenchi eterogenei, ma il costruttore del tipo elenco stesso è omogeneo:l'eterogeneità deriva dal tipo di elemento.In un linguaggio che ha sia tipi di dati algebrici che tipi che dipendono da un numero intero (o qualcosa di isomorfo ai naturali), è possibile definire un tipo di elenco veramente eterogeneo.Data una famiglia tipo $(T_n)_{n \in \mathbb{N}}$, è possibile definire il tipo di elenchi di cui $n$l'elemento ha il tipo $T_n$.Ecco una definizione del genere nella lingua dei calcolo di costruzioni induttive, in particolare nella sintassi Coq.Innanzitutto, definisco un esempio di una famiglia di tipi indicizzati da un numero intero: tuple A n è il tipo di n-element tuple i cui componenti hanno tutti il ​​tipo A.Per mantenere la definizione semplice, tutte le tuple hanno un valore aggiuntivo U all'inizio del tipo di unità.Quindi definisco il tipo induttivo hlist_ che è parametrizzato da entrambe le famiglie di tipi T e un numero intero n, che è un elenco eterogeneo di cui kl'elemento ha il tipo n + k.Il parametro n è necessario mantenere la definizione costruttiva.Infine mostro alcuni termini di esempio di tipo hlist (tuple bool), cioè elenca di chi nl'elemento è un nth-elemento tupla di bool valori (con U anteposto).

Inductive unit : Type := U : unit.
Fixpoint tuple (A : Type) (n : nat) : Type :=
  match n with
    | 0 => unit
    | S m => (tuple A m) * A
  end.

Inductive hlist_ (T : nat -> Type) n :=
  | Hnil : hlist_ T n
  | Hcons : (T n) -> hlist_ T (S n) -> hlist_ T n.
Definition hlist T := hlist_ T 0.

Check (Hcons (tuple bool) 0 U (Hnil _ _) : hlist (tuple bool)).
Check (Hcons (tuple bool) 0 U (Hcons _ 1 (U, true) (Hnil _ _)) : hlist (tuple bool)).
Check (Hcons (tuple bool) 0 U (Hcons _ 1 (U, true) (Hcons _ 2 (U, true, true) (Hnil _ _))) : hlist (tuple bool)).

¹ Fatta eccezione per alcuni tipi di dati primitivi, in realtà, ma qui non è importante.Quando dico "qualsiasi" su Java in questa risposta, intendo solo oggetti, non tipi di dati primitivi.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a cs.stackexchange
scroll top