[RISOLTO] Indicare il tipo per un linguaggio con un sistema di tipi basato su inferenza e polimorfismo

[mike.961]

Indicare il tipo di $F$, $G$ e $H$ per un linguaggio con sistema di tipi basato su inferenza e polimorfismo.

fun F(f, x) {
    return f(f(x));
}

fun G(g, x, y) {
    if (g(x)) {
        return x;
    } else {
        return y;
    }
}

fun H(x, y) {
    return x;
}

Personalmente non ho mai fatto questo tipo di esercizio, e non so dove trovare qualche esempio su come si risolva.
Quel che ho capito che devo fare è capire il tipo dei parametri formali e il tipo di ritorno per ogni funzione. Quindi suppongo sia così:
Per la funzione $F$, sia $f$ che $x$ possono avere un qualsiasi tipo, e la funzione può ritornare un qualsiasi tipo.
Per la funzione $G$, il parametro $g$ deve essere booleano, mentre $x$ e $y$ possono essere qualsiasi tipo. La funzione può ritornare un tipo qualsiasi.
Per la funzione $H$, sia $x$ che $y$ possono avere un qualsiasi tipo, e la funzione può ritornare un qualsiasi tipo.

Sbaglio nel pensare si risolva così? Grazie a chiunque mi aiuti.

[apatriarca]

Non è corretto. Questo genere di linguaggio si trovano principalmente quando si studiano linguaggi funzionali, che sono spesso caratterizzati dalle due caratteristiche che hai elencato. In realtà comunque alcune risposte potrebbero dipendere dai tipi supportati dal linguaggio. Nel seguito il tipo di una funzione sarà rappresentato con una freccia, ad esempio (A, bool) -> bool sarà una funzione con un argomento di tipo generico A e un valore booleano e che restituisce un valore booleano.

Partiamo dal primo caso. Per prima cosa abbiamo che F è una funzione con due argomenti. Siccome non abbiamo ancora detto nulla di questi tipi supponiamo che il tipo sia (A, B) -> C dove A è il tipo di f, B è il tipo di x e C è il tipo del valore di ritorno. Se ora guardiamo il corpo della funzione osserviamo che f è una funzione (o comunque un tipo che può essere usato come funzione) con tipo dell'unico argomento e del valore di ritorno uguali a quello di x. Il valore di ritorno di f(x) viene infatti passato nuovamente a f. Quindi f avrà tipo A = B -> B. Siccome il valore di ritorno di f viene restituito dalla funzione allora abbiamo che F avrà tipo ((B -> B), B) -> B.

Nel secondo caso g sarà una funzione che restituisce un booleano e prende in ingresso il tipo di x. x e y avranno inoltre lo stesso tipo che è anche uguale al valore di ritorno di G. Per cui abbiamo ((A -> bool), A, A) -> A.

Nel terzo caso x e y possono avere qualsiasi tipo, ma il valore di ritorno non è qualsiasi, ma uguale a quello di x. Abbiamo quindi (A, B) -> A.

[mike.961]

Innanzitutto grazie per la risposta. Sei stato molto chiaro, ma non riesco a capire una cosa, qui:

"apatriarca":Nel secondo caso g sarà una funzione che restituisce un booleano e prende in ingresso il tipo di x. x e y avranno inoltre lo stesso tipo che è anche uguale al valore di ritorno di G. Per cui abbiamo ((A -> bool), A, A) -> A.

Per quale motivo $x$ e $y$ dovrebbero avere lo stesso tipo? Per quanto ho capito la vedo in questo modo:
$((A -> "bool"), A, B) -> (A, B)$

[apatriarca]

La funzione G restituisce in un caso x e nell'altro y. Per cui devono avere lo stesso tipo. Il tipo sarebbe quello che hai scritto solo se la funzione restituisse entrambi i valori insieme.

[mike.961]

Ops, che sbadato. Se non ho capito male è perché il tipo di ritorno è unico, giusto?

Grazie mille per l'aiuto!

[apatriarca]

Sì, è perché il valore di ritorno è unico.