Necessità di wrapper di tipo esistenziale

Question

Si scopre che è sorprendentemente difficile utilizzare correttamente i tipi di tipo existential/rank-n nonostante l'idea molto semplice alla base.

Perché è necessario includere tipi esistenziali nei tipi data?

Ho il seguente semplice esempio:

{-# LANGUAGE RankNTypes, ImpredicativeTypes, ExistentialQuantification #-} 
module Main where 

c :: Double 
c = 3 

-- Moving `forall` clause from here to the front of the type tuple does not help, 
-- error is the same 
lists :: [(Int, forall a. Show a => Int -> a)] 
lists = [ (1, \x -> x) 
     , (2, \x -> show x) 
     , (3, \x -> c^x) 
     ] 

data HRF = forall a. Show a => HRF (Int -> a) 

lists' :: [(Int, HRF)] 
lists' = [ (1, HRF $ \x -> x) 
     , (2, HRF $ \x -> show x) 
     , (3, HRF $ \x -> c^x) 
     ] 

Se io commento la definizione di lists, il codice viene compilato con successo. Se non lo commento, ricevo i seguenti errori:

test.hs:8:21: 
    Could not deduce (a ~ Int) 
    from the context (Show a) 
     bound by a type expected by the context: Show a => Int -> a 
     at test.hs:8:11-22 
     `a' is a rigid type variable bound by 
      a type expected by the context: Show a => Int -> a at test.hs:8:11 
    In the expression: x 
    In the expression: \ x -> x 
    In the expression: (1, \ x -> x) 

test.hs:9:21: 
    Could not deduce (a ~ [Char]) 
    from the context (Show a) 
     bound by a type expected by the context: Show a => Int -> a 
     at test.hs:9:11-27 
     `a' is a rigid type variable bound by 
      a type expected by the context: Show a => Int -> a at test.hs:9:11 
    In the return type of a call of `show' 
    In the expression: show x 
    In the expression: \ x -> show x 

test.hs:10:21: 
    Could not deduce (a ~ Double) 
    from the context (Show a) 
     bound by a type expected by the context: Show a => Int -> a 
     at test.hs:10:11-24 
     `a' is a rigid type variable bound by 
      a type expected by the context: Show a => Int -> a at test.hs:10:11 
    In the first argument of `(^)', namely `c' 
    In the expression: c^x 
    In the expression: \ x -> c^x 
Failed, modules loaded: none. 

Perché sta succedendo? Non dovrebbe il secondo esempio essere equivalente al primo? Qual è la differenza tra questi usi di tipi n-rank? È possibile escludere una definizione ADT extra e usare solo tipi semplici quando voglio un tale tipo di polimorfismo?

Answer 1

ci sono due questioni è necessario considerare per quanto riguarda la gestione dei tipi esistenziali:

• Se si memorizzano "tutto ciò che può essere show n," è necessario memorizzare la cosa che può essere visualizzata con come mostrarlo.
• Una variabile effettiva può avere sempre un solo tipo.

Il primo punto è il motivo per cui è necessario disporre di tipo involucri esistenziali, perché quando si scrive questo:

data Showable = Show a => Showable a 

Quello che accade è che qualcosa di simile viene dichiarato:

data Showable a = Showable (instance of Show a) a 

ie un riferimento all'istanza di classe di Show a viene memorizzato insieme al valore a. In questo caso, non è possibile avere una funzione che scarichi uno Showable, perché quella funzione non saprebbe come mostrare a.

Il secondo punto è perché a volte si ottiene qualche stranezza di tipo e perché non è possibile associare i tipi esistenziali nei collegamenti let, ad esempio.

---

Hai anche un problema con il tuo ragionamento nel codice. Se hai una funzione come forall a . Show a => (Int -> a) ottieni una funzione che, dato un numero intero, sarà in grado di produrre qualsiasi tipo di valore visualizzabile che il chiamante sceglie. Probabilmente si intende exists a . Show a => (Int -> a), il che significa che se la funzione ottiene un numero intero, restituirà un tipo per cui esiste un'istanza Show.

Answer 2

Gli esempi non sono equivalenti. Il primo,

lists :: [(Int, forall a. Show a => Int -> a)] 

dice che ciascun secondo componente può produrre qualsiasi tipo desiderato, fintanto che è un esempio di Show da un Int.

Il secondo esempio è modulo del tipo involucro equivalente

lists :: [(Int, exists a. Show a => Int -> a)] 

Per esempio, ogni secondo componente può produrre certo tipo appartenendo a Show da un Int, ma non avete idea che tipo che funziona ritorna.

Inoltre, le funzioni che mettete nelle tuple non soddisfano il primo contratto:

lists = [ (1, \x -> x) 
     , (2, \x -> show x) 
     , (3, \x -> c^x) 
     ] 

\x -> x produce lo stesso tipo di risultato che si è dato come input, ecco, questo è Int. show produce sempre un String, quindi è un tipo fisso. infine, \x -> c^x produce lo stesso tipo di c, ovvero Double.

Answer 3

Il tuo primo tentativo è non utilizzando tipi esistenziali. Piuttosto tuoi

lists :: [(Int, forall a. Show a => Int -> a)] 

richieste che i secondi componenti possono fornire un elemento di qualsiasi tipo showable che ho scelto, non solo un certo tipo showable che si sceglie. Stai cercando

lists :: [(Int, exists a. Show a * (Int -> a))] -- not real Haskell 

ma non è quello che hai detto. Il metodo di impacchettamento dei tipi di dati consente di ripristinare exists da forall tramite la conversione. Hai

HRF :: forall a. Show a => (Int -> a) -> HRF 

il che significa che per costruire un valore HRF, è necessario fornire una tripla che contiene un tipo a, un Show dizionario per a e una funzione in Int -> a. Cioè, il tipo HRF del costruttore di curry in modo efficace questo non-tipo

HRF :: (exists a. Show a * (Int -> a)) -> HRF -- not real Haskell 

Potreste essere in grado di evitare il metodo tipo di dati utilizzando i tipi di rango-n di Chiesa-codificare l'esistenziale

type HRF = forall x. (forall a. Show a => (Int -> a) -> x) -> x 

ma questo è probabilmente eccessivo.