Tipi di impressioni rispetto al vecchio sottotipo vecchio

Question

Una mia amica ha posto una domanda di lingua Scala apparentemente innocua la settimana scorsa a cui non ho avuto una buona risposta: se esiste un modo semplice per dichiarare una raccolta di elementi appartenenti a una comune classe di tipi . Ovviamente non esiste una nozione di classe "typeclass" di prima classe in Scala, quindi dobbiamo pensarci in termini di tratti e limiti di contesto (cioè impliciti).

In concreto, dato qualche tratto T[_] che rappresenta una typeclass, e tipi A, B e C, con impliciti corrispondenti portata T[A], T[B] e T[C], vogliamo dichiarare qualcosa di simile a un List[T[a] forAll { type a }], in cui siamo in grado di gettare le istanze di A , B e C con impunità. Questo ovviamente non esiste in Scala; uno question last year ne parla in modo più approfondito.

La domanda di follow-up naturale è "come fa Haskell a farlo?" Bene, GHC in particolare ha un'estensione di sistema di tipo denominata impredicative polymorphism, descritta nella carta "Boxy Types". In breve, data una classe di caratteri T si può legalmente costruire un elenco [forall a. T a => a]. Data una dichiarazione di questo modulo, il compilatore esegue alcune magie di passaggio del dizionario che ci consentono di conservare le istanze di typeclass corrispondenti ai tipi di ciascun valore nell'elenco in fase di esecuzione.

Il fatto è che "la magia del dizionario" somiglia molto a "vtables". In un linguaggio orientato agli oggetti come Scala, la sottotipizzazione è un meccanismo molto più semplice e naturale rispetto all'approccio "Tipi Boxy". Se il nostro A, B e C estendono tutti i tratti T, allora possiamo semplicemente dichiarare List[T] ed essere felici. Allo stesso modo, come nota Miles in un commento qui sotto, se tutti estendono i tratti T1, T2 e T3, allora posso usare List[T1 with T2 with T3] come equivalente all'imprevedibile Haskell [forall a. (T1 a, T2 a, T3 a) => a].

Tuttavia, il principale svantaggio noto con sottotipo rispetto al typeclasses è accoppiamento stretto: i miei A, B e C tipi devono avere il loro T comportamento cotto in Supponiamo che questo è un importante dealbreaker, e io può. 't utilizza la sottotipizzazione. Così la terra di mezzo in Scala è ruffiani^conversioni H^H^H^H^Himplicit: dato qualche A => T, B => T e C => T portata implicita, posso di nuovo tranquillamente popolare un List[T] con i miei A, B e C valori ...

... Fino a quando non vogliamo List[T1 with T2 with T3]. A quel punto, anche se abbiamo conversioni implicite A => T1, A => T2 e A => T3, non possiamo inserire un A nell'elenco. Potremmo ristrutturare le nostre conversioni implicite per fornire letteralmente lo A => T1 with T2 with T3, ma non ho mai visto nessuno farlo prima e sembra ancora un'altra forma di accoppiamento stretto.

Va bene, quindi la mia domanda è, infine, suppongo, una combinazione di un paio di domande che sono state in precedenza chiesto qui: "why avoid subtyping?" e "advantages of subtyping over typeclasses" ... c'è qualche teoria unificante che dice il polimorfismo impredicativa e sottotipo il polimorfismo sono la stessa cosa ? Le conversioni implicite sono in qualche modo il segreto amore-figlio dei due? E qualcuno può articolare un modello buono e pulito per esprimere limiti multipli (come nell'ultimo esempio sopra) in Scala?

Answer 1

Stai confondendo tipi impredicativi con tipi esistenziali.I tipi di impreditorialità consentono di inserire i valori polimorfici in una struttura dati, non quelli concreti arbitrari. In altre parole, [forall a. Num a => a] significa che hai una lista in cui ogni elemento funziona come qualsiasi tipo numerico, quindi non puoi inserire ad es. Int e Double in un elenco di tipo [forall a. Num a => a], ma è possibile inserire qualcosa come 0 :: Num a => a in esso. I tipi di impredicamento non sono ciò che vuoi qui.

Quello che vuoi sono i tipi esistenziali, ad esempio [exists a. Num a => a] (non la vera sintassi Haskell), che dice che ogni elemento è un tipo numerico sconosciuto. Per scrivere questo in Haskell, però, abbiamo bisogno di introdurre un tipo di dati con avvolgitore:

data SomeNumber = forall a. Num a => SomeNumber a 

nota il cambiamento exists-forall. Questo perché stiamo descrivendo il costruttore . Possiamo inserire qualsiasi tipo numerico in, ma il tipo di sistema "dimentica" che tipo era. Una volta che lo ritiriamo (per corrispondenza di pattern), tutto ciò che sappiamo è che è un tipo numerico. Quello che sta succedendo sotto il cofano, è che il tipo SomeNumber contiene un campo nascosto che memorizza il dizionario di classe del tipo (conosciuto come vtable/implicito), motivo per cui abbiamo bisogno del tipo di wrapper.

Ora possiamo utilizzare il tipo [SomeNumber] per un elenco di numeri arbitrari, ma è necessario avvolgere ciascun numero in entrata, ad es. [SomeNumber (3.14 :: Double), SomeNumber (42 :: Int)]. Il dizionario corretto per ogni tipo viene cercato e memorizzato automaticamente nel campo nascosto nel punto in cui avvolgiamo ciascun numero.

La combinazione di tipi esistenziali e classi di tipi è in qualche modo simile alla sottotipizzazione, poiché la differenza principale tra classi di tipi e interfacce è che con classi di tipi il vtable viaggia separatamente dagli oggetti e tipi di pacchetti di oggetti e oggetti vtables indietro ancora insieme.

Tuttavia, a differenza del sottotipo tradizionale, non sei obbligato ad accoppiarli uno a uno, quindi possiamo scrivere cose come questa che confeziona un vtable con due valori dello stesso tipo.

data TwoNumbers = forall a. Num a => TwoNumbers a a 

f :: TwoNumbers -> TwoNumbers 
f (TwoNumbers x y) = TwoNumbers (x+y) (x*y) 

list1 = map f [TwoNumbers (42 :: Int) 7, TwoNumbers (3.14 :: Double) 9] 
-- ==> [TwoNumbers (49 :: Int) 294, TwoNumbers (12.14 :: Double) 28.26] 

o anche cose più elaborate. Una volta che il pattern si abbina sul wrapper, siamo di nuovo nella terra delle classi di tipi. Sebbene non sappiamo quale sia il tipo x e , sappiamo che sono uguali e abbiamo il dizionario corretto disponibile per eseguire operazioni numeriche su di essi.

Tutto sopra funziona in modo simile con più classi di tipi. Il compilatore genererà semplicemente campi nascosti nel tipo di wrapper per ogni vtable e li porterà tutti nello scope quando coincidiamo.

data SomeBoundedNumber = forall a. (Bounded a, Num a) => SBN a 

g :: SomeBoundedNumber -> SomeBoundedNumber 
g (SBN n) = SBN (maxBound - n) 

list2 = map g [SBN (42 :: Int32), SBN (42 :: Int64)] 
-- ==> [SBN (2147483605 :: Int32), SBN (9223372036854775765 :: Int64)] 

Come Sono molto un principiante quando si tratta di Scala, io non sono sicuro di poter aiutare con la parte finale della tua domanda, ma spero che questo ha almeno chiarito alcune delle confusione e ti ha dato alcune idee su come procedere.

Answer 2

@ hammar's answer ha perfettamente ragione. Ecco il modo in scala per farlo.Per l'esempio io ti porterò Show come classe tipo ei valori i e d per il confezionamento in un elenco:

// The type class 
trait Show[A] { 
    def show(a : A) : String 
} 

// Syntactic sugar for Show 
implicit final class ShowOps[A](val self : A)(implicit A : Show[A]) { 
    def show = A.show(self) 
} 

implicit val intShow = new Show[Int] { 
    def show(i : Int) = "Show of int " + i.toString 
} 

implicit val stringShow = new Show[String] { 
    def show(s : String) = "Show of String " + s 
} 


val i : Int = 5 
val s : String = "abc" 

Ciò che vogliamo è essere gestito in grado il seguente codice

val list = List(i, s) 
for (e <- list) yield e.show 

costruzione la lista è facile ma la lista non "ricorderà" il tipo esatto di ciascuno dei suoi elementi. Invece trasmetterà ciascun elemento a un tipo di super comune T. Il tipo super super più preciso tra String e Int è Any, il tipo di elenco è List[Any].

Il problema è: cosa dimenticare e cosa ricordare? Vogliamo dimenticare il tipo esatto degli elementi, ma vogliamo ricordare che sono tutte le istanze di Show. La seguente classe fa esattamente che

abstract class Ex[TC[_]] { 
    type t 
    val value : t 
    implicit val instance : TC[t] 
} 

implicit def ex[TC[_], A](a : A)(implicit A : TC[A]) = new Ex[TC] { 
    type t = A 
    val value = a 
    val instance = A 
} 

Questa è una codifica del esistenziale:

val ex_i : Ex[Show] = ex[Show, Int](i) 
val ex_s : Ex[Show] = ex[Show, String](s) 

Si confezionare un valore con l'istanza tipo di classe corrispondente.

Infine possiamo aggiungere un'istanza per Ex[Show]

implicit val exShow = new Show[Ex[Show]] { 
    def show(e : Ex[Show]) : String = { 
    import e._ 
    e.value.show 
    } 
} 

Il import e._ è necessario per portare l'istanza in ambito. Grazie alla magia degli impliciti:

val list = List[Ex[Show]](i , s) 
for (e <- list) yield e.show 

che è molto vicino al codice previsto.