Qual è la differenza tra costruttori di valori e tuple?

Question

It's written che le tuple di Haskell sono semplicemente una sintassi diversa per i tipi di dati algebrici. Allo stesso modo, ci sono esempi su come ridefinire i costruttori di valori con le tuple.

Per esempio, un tipo di dati Albero in Haskell potrebbe essere scritto come

data Tree a = EmptyTree | Node a (Tree a) (Tree a) 

che potrebbe essere convertito a "forma di tupla" come questo:

data Tree a = EmptyTree | Node (a, Tree a, Tree a) 

Qual è la differenza tra il Node costruttore di valori nel primo esempio e l'attuale tuple nel secondo esempio? vale a dire Node a (Tree a) (Tree a) rispetto a (a, Tree a, Tree a) (a parte solo la sintassi)?

Sotto il cofano, è Node a (Tree a) (Tree a) solo una sintassi diversa per una tupla di 3 tipi appropriati in ogni posizione?

So che è possibile applicare in parte un costruttore di valore, come Node 5 che avrà Tipo: (Node 5) :: Num a => Tree a -> Tree a -> Tree a

È sorta di possibile applicare parzialmente una tupla troppo, utilizzando (,,) in funzione ... ma questo doesn' t sapere circa i potenziali tipi per le voci non-bound, come ad esempio:

Prelude> :t (,,) 5 
(,,) 5 :: Num a => b -> c -> (a, b, c) 

a meno che, immagino, si dichiara esplicitamente un tipo con ::.

Oltre alle specialità sintattiche come questa, oltre a questo ultimo esempio del tipo scoping, esiste una differenza sostanziale tra qualunque cosa una "funzione di costruzione del valore" sia effettivamente in Haskell, rispetto a una tupla usata per memorizzare valori posizionali degli stessi tipi sono gli argomenti del costruttore del valore?

Answer 1

Bene, coneptually non c'è davvero alcuna differenza e in effetti altri linguaggi (OCaml, Elm) presentano i sindacati taggati esattamente in questo modo - cioè tag su tuple o record di prima classe (che Haskell non ha). Personalmente ritengo che questo sia un difetto di design in Haskell.

ci sono alcune differenze pratiche però:

1. Pigrizia. Le tuple di Haskell sono pigre e non puoi cambiarlo. È tuttavia possibile contrassegnare i campi costruttore altrettanto rigorose: impronta

   data Tree a = EmptyTree | Node !a !(Tree a) !(Tree a) 
   

2. memoria e prestazioni. L'aggiramento dei tipi intermedi riduce l'ingombro e aumenta le prestazioni. Puoi leggere ulteriori informazioni a riguardo in this fine answer.

   È anche possibile contrassegnare i campi rigorosi con the UNPACK pragma per ridurre ulteriormente l'ingombro. In alternativa è possibile utilizzare the -funbox-strict-fields compiler option. Riguardo l'ultimo, preferisco semplicemente accedervi di default in tutti i miei progetti. Vedere the Hasql's Cabal file per esempio.

---

Considerando il detto sopra, se si tratta di un tipo pigro che stai cercando, quindi i seguenti frammenti dovrebbero compilare alla stessa cosa:

data Tree a = EmptyTree | Node a (Tree a) (Tree a) 

data Tree a = EmptyTree | Node {-# UNPACK #-} !(a, Tree a, Tree a) 

Quindi credo che si può diciamo che è possibile utilizzare le tuple per memorizzare i campi pigri di un costruttore senza penalità. Anche se va detto che questo modello è un po 'non convenzionale nella comunità di Haskell.

Se si tratta della riduzione rigorosa del tipo e dell'impronta che si sta cercando, non c'è altro modo che denormalizzare le tuple direttamente nei campi del costruttore.

Answer 2

Sono quello che viene chiamato isomorfo, che significa "avere la stessa forma". È possibile scrivere qualcosa di simile

data Option a = None | Some a 

e questo è isomorfo a

data Maybe a = Nothing | Just a 

il che significa che è possibile scrivere due funzioni

f :: Maybe a -> Option a 
g :: Option a -> Maybe a 

Tale che f . g == id == g . f per tutti i possibili ingressi. Possiamo quindi dire che (,,) è un costruttore di dati isomorfo al costruttore

data Triple a b c = Triple a b c 

Poiché è possibile scrivere

f :: (a, b, c) -> Triple a b c 
f (a, b, c) = Triple a b c 

g :: Triple a b c -> (a, b, c) 
g (Triple a b c) = (a, b, c) 

E Node come un costruttore è un caso particolare di Triple, vale a dire Triple a (Tree a) (Tree a). In realtà, si potrebbe anche arrivare a dire che la tua definizione di Tree potrebbe essere scritto come

newtype Tree' a = Tree' (Maybe (a, Tree' a, Tree' a)) 

Il newtype è necessaria dal momento che non si può avere un alias type essere ricorsiva. Tutto quello che devi fare è dire che EmptyLeaf == Tree' Nothing e Node a l r = Tree' (Just (a, l, r)). Potresti semplicemente scrivere funzioni che convertono tra i due.

Si noti che questo è tutto da un punto di vista matematico. Il compilatore può aggiungere ulteriori metadati e altre informazioni per essere in grado di identificare un particolare costruttore, in modo che si comportino in modo leggermente diverso durante il runtime.