Perché abbiamo bisogno di "Tipi di dati algebrici"?

Question

Ho letto alcune spiegazioni dei tipi algebrica dati:

• The Algebra of Algebraic Data types I
• The Algebra of Algebraic Data types II
• The Algebra of Algebraic Data types III
• The Algebra of Data, and Calculus of Mutation

Questi articoli danno molto campioni descrizione dettagliata e il codice.

All'inizio pensavo che il tipo di dati algebrico fosse solo per la definizione di alcuni tipi e possiamo abbinarli alla corrispondenza dei modelli. Ma dopo aver letto questi articoli, ho trovato che "pattern matching" non è nemmeno menzionato lì, e il contenuto sembra interessante ma molto più complesso di quanto mi aspettassi.

Così ho alcune domande (che non trovano risposta in questi articoli):

• Perché ne abbiamo bisogno, per esempio, a Haskell o Scala?
• Cosa possiamo fare se ce l'abbiamo, e cosa non possiamo fare se non ce l'abbiamo?

Answer 1

Dovremmo cominciare con l'articolo wiki Haskell Algebraic Data Types

E qui, in breve, solo la mia visione:

• abbiamo bisogno di loro per modellare la logica di business in vecchia maniera orientata agli oggetti (o addirittura in vecchio modo basato su categorie), e renderlo più tipicamente utile in quanto il compilatore può verificare di aver abbinato tutte le possibili scelte. O, in altre parole, che la tua funzione è total, non parziale. Alla fine, dà al compilatore la possibilità di provare la correttezza del tuo codice (ecco perché sono raccomandati i tratti sigillati). Quindi, più tipi diversi hai, meglio è ... la programmazione generica, invece, ti aiuta qui perché produce più tipi.
• caratteristiche standard: possiamo rappresentare il tipo come un "set" di oggetti, possiamo abbinare l'oggetto con il tipo (usando la corrispondenza del modello), o anche decostruire (analizzare) con i corrispondenti. Possiamo anche aggiungere dinamicamente un comportamento (in fase di compilazione) a tale tipo con tipo classess. È possibile anche per la classe regolare, ma qui ci dà la possibilità di separare il modello algebrico (tipi) dal comportamento (funzioni)
• possiamo costruire tipi come products/coproducts di oggetti/tipi diversi. Si può pensare al sistema di tipo algebrico come un insieme (o più in generale - come una categoria chiusa da cartesiano). type Boolean = True | False significa che Boolean è un'unione (coprodotto) di True e False. Cat(height: Height, weight: Weight) è una "tupla" (più in generale - prodotto) di Height e Weight. Il prodotto (più-meno) rappresenta la relazione "parte di" da OOP, coprodotto - "è" (ma nel modo opposto).

Esso ci dà anche un modo per spedire il comportamento in fase di esecuzione in multimethod stile (come se fosse in CLOS):

sealed trait Animal 
    case class Cat extends Animal 
    case class Dog extends Animal 

def move(c: Animal) = c match { 
    case Cat(...) => ... 
    case Dog(...) => 
    case a: Animal => ...//if you need default implementation 
} 

Haskell-like:

data Animal = Dog | Cat //coproduct 

let move Dog d = ... 
let move Cat c = ... 

Invece di:

trait Animal { 
    ... 
    def move = ... 
} 

class Cat(val ...) extends Animal { 
    override def move = ... 
} 

class Dog(val ...) extends Animal { 
    override def move = ... 
} 

PS Teoricamente, se stai modellando il mondo in modo algebrico e le tue funzioni sono totali e pure, puoi provare che la tua applicazione è corretta. Se compila - funziona :).

P.S.2. Dovrei anche menzionare che la gerarchia di tipi di Scala che ha Any in esso non è così buona per typesafety (ma è utile per l'interoperabilità con Java e IO) poiché interrompe la bella struttura definita dai GADT. Oltre a ciò, case class potrebbe essere sia GADT (algebrico) che ADT (astratto), il che riduce anche le garanzie.

Answer 2

Il post del blog che si menziona riguarda più gli aspetti matematici dei tipi di dati algebrici che riguardano il loro utilizzo pratico nella programmazione. Penso che molti programmatori funzionali abbiano prima imparato a conoscere i tipi di dati algebrici usandoli in qualche linguaggio di programmazione, e solo successivamente hanno studiato le loro proprietà algebriche.

Infatti, l'intento del post sul blog è chiaro fin dal suo inizio:

In questa serie di post ti spiego il perché i tipi di dati di Haskell sono chiamati algebrica - senza menzionare la teoria delle categorie o avanzato matematica.

In ogni caso, l'utilità pratica dei tipi algebrici è meglio apprezzata giocando con loro.

Supponiamo, ad esempio, di voler scrivere una funzione per intersecare due segmenti su un piano.

def intersect(s1: Segment, s2: Segment): ??? 

Quale dovrebbe essere il risultato? Si è tentati di scrivere

def intersect(s1: Segment, s2: Segment): Point 

ma cosa succede se non ci sono intersezioni? Si potrebbe tentare di applicare una patch a tale angolo restituendo null o lanciando un'eccezione NoIntersection. Tuttavia, due segmenti potrebbero anche sovrapporsi a più di un punto, quando si trovano sulla stessa linea retta. Cosa dovremmo fare in questi casi? Lanciare un'altra eccezione?

L'approccio tipi algebrici è quello di progettare un tipo che copre tutti i casi:

sealed trait Intersection 
case object NoIntersection extends Intersection 
case class SinglePoint(p: Point) extends Intersection 
case class SegmentPortion(s: Segment) extends Intersection 

def intersect(s1: Segment, s2: Segment): Intersection 

ci sono molti casi pratici in cui tale approccio si sente del tutto naturale. In alcune altre lingue prive di tipi algebrici, è necessario ricorrere alle eccezioni, a null s (vedere anche the billion-dollar mistake), a classi non sigillate (rendendo impossibile per il compilatore verificare l'esaustività della corrispondenza del modello) o ad altre funzionalità fornite dalla lingua Probabilmente, l'opzione "migliore" in OOP è usare lo Visitor pattern per codificare i tipi algebrici e la corrispondenza dei pattern in lingue che non hanno tali caratteristiche.Tuttavia, avere questo direttamente supportato nella lingua, come in scala, è molto più conveniente.