Il tipo-ritorno- (solo) -polymorphism in Haskell è una buona cosa?

26

Una cosa su cui non sono mai riuscito a fare i conti con Haskell è come avere costanti e funzioni polimorfiche il cui tipo di ritorno non può essere determinato dal loro tipo di input, come

class Foo a where
    foo::Int -> a

Alcuni dei motivi per cui non mi piace:

Trasparenza referenziale:

"In Haskell, dato lo stesso input, una funzione restituirà sempre lo stesso output", ma è proprio vero? read "3" return 3 quando utilizzato in un contesto Int , ma genera un errore quando viene utilizzato in un contesto, diciamo (Int,Int) . Sì, puoi obiettare che read sta anche prendendo un parametro di tipo, ma l'implicità del parametro type fa perdere un po 'della sua bellezza secondo me.

Limitazione monomorfismo:

Una delle cose più fastidiose di Haskell. Correggetemi se ho torto, ma l'intero motivo della MR è che il calcolo che sembra condiviso potrebbe non essere dovuto al fatto che il parametro type è implicito.

Digita come predefinito:

Ancora una delle cose più fastidiose di Haskell. Succede ad es. se passi il risultato di funzioni polimorfiche nel loro output a funzioni polimorfiche nel loro input. Ancora una volta, correggimi se sbaglio, ma questo non sarebbe necessario senza funzioni il cui tipo di ritorno non può essere determinato dal loro tipo di input (e costanti polimorfiche).

Quindi la mia domanda è (correndo il rischio di essere timbrato come una "questione di discussione"): Sarebbe possibile creare un linguaggio simile a Haskell in cui il controllo di tipo non consente questo tipo di definizioni? In tal caso, quali sarebbero i vantaggi / svantaggi di tale restrizione?

Riesco a vedere alcuni problemi immediati:

Se, per esempio, 2 ha solo il tipo Integer , 2/3 non digiterà più il controllo con la definizione corrente di / . Ma in questo caso, penso che le classi di tipi con dipendenze funzionali potrebbero venire in soccorso (sì, so che questa è un'estensione). Inoltre, penso che sia molto più intuitivo avere funzioni che possono assumere diversi tipi di input, piuttosto che avere funzioni che sono limitate nei loro tipi di input, ma semplicemente passiamo loro dei valori polimorfici.

La digitazione di valori come [] e Nothing mi sembra un dado più duro da decifrare. Non ho pensato a un buon modo per gestirli.

    
posta dainichi 03.09.2011 - 16:39
fonte

4 risposte

33

In realtà penso che il polimorfismo del tipo restituito sia una delle migliori caratteristiche delle classi di tipi. Dopo averlo usato per un po ', a volte è difficile per me tornare alla modellazione in stile OOP dove non ce l'ho.

Considera la codifica dell'algebra. In Haskell abbiamo una classe di caratteri Monoid (ignorando mconcat )

class Monoid a where
   mempty :: a
   mappend :: a -> a -> a

Come potremmo codificarlo come un'interfaccia in un linguaggio OO? La risposta breve è che non possiamo. Questo perché il tipo di mempty è (Monoid a) => a aka, restituisce il tipo di polimorfismo. Avere la capacità di modellare l'algebra è IMO incredibilmente utile. *

Inizi il tuo post con il reclamo su "Trasparenza referenziale". Ciò solleva un punto importante: Haskell è un linguaggio orientato al valore. Quindi espressioni come read 3 non devono essere intese come cose che calcolano valori, possono anche essere intese come valori. Ciò significa che il vero problema non è il tipo di polimorfismo di ritorno: si tratta di valori con tipo polimorfico ( [] e Nothing ). Se la lingua dovrebbe avere questi, allora deve davvero avere tipi di ritorno polimorfici per coerenza.

Dovremmo essere in grado di dire che [] è di tipo forall a. [a] ? Credo di si. Queste funzionalità sono molto utili e rendono la lingua molto più semplice.

Se Haskell aveva il polimorfismo del sottotipo [] potrebbe essere un sottotipo per tutto [a] . Il problema è che non conosco un modo di codificare quello senza che il tipo della lista vuota sia polimorfico. Considera come dovrebbe essere fatto in Scala (è più breve di farlo nel linguaggio OOP, Java, staticamente tipizzato staticamente)

abstract class List[A]
case class Nil[A] extends List[A]
case class Cons[A](h: A. t: List[A]) extends List[A]

Anche qui, Nil() è un oggetto di tipo Nil[A] **

Un altro vantaggio del polimorfismo del tipo di ritorno è che rende molto più semplice l'incorporamento di Curry-Howard.

Considera i seguenti teoremi logici:

 t1 = forall P. forall Q. P -> P or Q
 t2 = forall P. forall Q. P -> Q or P

Possiamo catturarli banalmente come teoremi in Haskell:

data Either a b = Left a | Right b
t1 :: a -> Either a b
t1 = Left
t2 :: a -> Either b a
t2 = Right

Per riassumere: mi piace il polimorfismo del tipo restituito, e penso solo che infrange la trasparenza referenziale se si dispone di una nozione limitata di valori (sebbene ciò sia meno convincente nel caso della classe di tipo ad hoc). D'altra parte, trovo i tuoi punti di vista su MR e digita il valore predefinito.

*. Nei commenti ysdx indica questo non è strettamente vero: potremmo ri-implementare classi di tipi modellando l'algebra come un altro tipo. Come la java:

abstract class Monoid<M>{
   abstract M empty();
   abstract M append(M m1, M m2);
}

Quindi devi passare oggetti di questo tipo con te. Scala ha una nozione di parametri impliciti che evita alcuni, ma nella mia esperienza non tutti, del sovraccarico di gestione esplicita di queste cose. Mettendo i tuoi metodi di utilità (metodi di fabbrica, metodi binari, ecc.) Su un tipo F separato, si rivela un modo incredibilmente bello di gestire le cose in un linguaggio OO che supporta i generici. Detto questo, non sono sicuro che avrei annullato questo schema se non avessi avuto esperienza nel modellare le cose con le classifiche, e non sono sicuro che gli altri lo faranno.

Ha anche delle limitazioni, fuori dalla scatola non c'è modo di ottenere un oggetto che implementa la classe di caratteri per un tipo arbitrario. Bisogna o passare i valori in modo esplicito, usare qualcosa come impliciti di Scala, o usare una qualche forma di tecnologia di iniezione delle dipendenze. La vita diventa brutta D'altra parte, è bello poter avere più implementazioni per lo stesso tipo. Qualcosa può essere un Monoid in più modi. Inoltre, portare in giro queste strutture separatamente ha IMO un aspetto più matematicamente moderno, costruttivo. Quindi, anche se generalmente preferisco il modo Haskell di farlo, probabilmente ho sopravvalutato il mio caso.

I tipi di classe con polimorfismo di tipo restituito rendono questo tipo di cose facile da gestire. Ciò non significa che sia il modo migliore per farlo.

**. Jörg W Mittag sottolinea questo non è davvero il modo canonico di farlo in Scala. Invece, seguiremmo la libreria standard con qualcosa di più simile a

abstract class List[+A] ...  
case class Cons[A](head: A, tail: List[A]) extends List[A] ...
case object Nil extends List[Nothing] ...

Questo sfrutta il supporto di Scala per i tipi di fondo, così come i parametri di tipo covariante. Quindi, Nil è di tipo Nil non Nil[A] . A questo punto siamo abbastanza lontani da Haskell, ma è interessante notare come Haskell rappresenti il tipo di fondo

undefined :: forall a. a

Cioè, non è il sottotipo di tutti i tipi, è polimorficamente (sp) un membro di tutti i tipi.
Ancora più polimorfismo del tipo di ritorno.

    
risposta data 03.09.2011 - 20:50
fonte
10

Basta notare un equivoco:

"In Haskell, given the same input, a function will always return the same output", but is that really true? read "3" return 3 when used in an Int context, but throws an error when used in a, say, (Int,Int) context.

Solo perché mia moglie guida una Subaru e io guido una Subaru non significa che guidiamo la stessa macchina. Solo perché ci sono 2 funzioni denominate read non significa che sia la stessa funzione. Infatti read :: String -> Int è definito nell'istanza di lettura di Int, dove read :: String (Int, Int) è definita nell'istanza di lettura di (Int, Int). Quindi, sono funzioni completamente diverse.

Questo fenomeno è comune nei linguaggi di programmazione e viene solitamente chiamato overloading .

    
risposta data 24.09.2011 - 18:37
fonte
4

Desidero davvero che il termine "polimorfismo del tipo di ritorno" non sia mai stato creato. Incoraggia un fraintendimento di ciò che sta accadendo. Basti dire che, mentre l'eliminazione del "polimorfismo del tipo di ritorno" rappresenterebbe un cambiamento di uccisione estremamente ad-hoc ed espressivo, non risolverebbe nemmeno lontanamente i problemi sollevati nella domanda.

Il tipo di ritorno non è in alcun modo speciale. Prendere in considerazione:

class Foo a where
    foo :: Maybe a -> Bool

x = foo Nothing

Questo codice causa tutti gli stessi problemi del "polimorfismo del tipo di ritorno" e dimostra lo stesso tipo di differenze rispetto a OOP. Nessuno parla però di "primo argomento, forse tipo polimorfismo".

L'idea chiave è che l'implementazione utilizza i tipi per risolvere quale istanza utilizzare. I valori (di runtime) di qualsiasi tipo non hanno nulla a che fare con esso. Effettivamente funzionerebbe anche per i tipi che non hanno valori. In particolare, i programmi Haskell non hanno significato senza i loro tipi. (Ironia della sorte, questo rende Haskell un linguaggio in stile Chiesa rispetto a un linguaggio in stile Curry. Ho un articolo sul blog in corso di elaborazione su questo.)

    
risposta data 18.01.2016 - 02:00
fonte
2

Riguardo alla tua domanda sulla trasparenza referenziale su valori polimorfici, ecco qualcosa che può aiutarti.

Considera il nome 1 . Denota spesso oggetti diversi (ma fissi):

  • 1 come in un numero intero
  • 1 come in un Real
  • 1 come in una matrice di identità quadrata
  • 1 come in una funzione di identità

Qui è importante notare che sotto ogni contesto , 1 è un valore fisso. In altre parole, ogni coppia nome-contesto denota un oggetto univoco . Senza il contesto, non possiamo sapere quale oggetto stiamo denotando. Quindi il contesto deve essere dedotto (se possibile) o esplicitamente fornito. Un buon vantaggio (oltre alla notazione conveniente) è la capacità di esprimere il codice in contesti generici.

Ma poiché questa è solo una notazione, avremmo potuto usare la seguente notazione:

  • Integer1 come in un numero intero
  • Real1 come in un Real
  • MatrixIdentity1 come in una matrice di identità quadrata
  • FunctionIdentity1 come in una funzione di identità

Qui otteniamo nomi espliciti. Questo ci consente di ricavare il contesto solo dal nome. Quindi è necessario solo il nome dell'oggetto per denotare completamente un oggetto.

Le classi di tipi Haskell hanno eletto il precedente schema di notazione. Ora ecco la luce alla fine del tunnel:

show è un nome, non un valore (non ha contesto), ma show :: String -> a è un valore (ha sia un nome che un contesto). Pertanto le funzioni show :: String -> Int e show :: String -> (Int, Int) sono funzioni letteralmente diverse. Pertanto, se non sono d'accordo sui loro input, viene mantenuta la trasparenza referenziale.

    
risposta data 28.10.2013 - 22:38
fonte

Leggi altre domande sui tag