Existe um cálculo de SKI digitado?

Muitos de nós sabemos a correspondência entre lógica combinatória e cálculo lambda . Mas nunca vi (talvez não tenha examinado o suficiente) o equivalente a "combinadores digitados", correspondendo ao cálculo lambda simplesmente digitado. Existe algo assim? Onde alguém poderia encontrar informações sobre isso?

reference-request logic lambda-calculus type-theory combinatory-logic Hugo Sereno Ferreira
fonte

Você pode estar interessado em The Reader Monad e Abstraction Elimination in The Monad.Reader, Edição 17 . A mônada do Reader (ou mais precisamente seu função aplicador) está intimamente relacionada ao SKI digitado.

Petr Pudlák

Respostas:

A completividade expressiva dos combinadores digitados em comparação com o cálculo lambda simplesmente digitado foi demonstrada . Para cada combinador não digitado, é necessário uma família inteira de combinadores digitados. Por exemplo, um tem

$\mathbf{I}_{\alpha\to\alpha}$
$\mathbf{K}_{\alpha\to(\beta\to\alpha)}$
$\mathbf{S}_{\alpha\to(\beta\to\gamma)\to(\alpha\to\beta\to(\alpha\to\gamma))}$

para todas as combinações de tipos simples e . $\alpha,\beta$ $\gamma$

Em alternativa, basta pensar nos tipos como regimes de tipo (ou tipos polimórficos) e inseri-los em Haskell e voila: combinadores .

Dave Clarke
fonte

Nunca pensei no combinador

agindo sobre uma mônada! É assim mesmo?

S

$\mathbf{S}$

Hugo Sereno Ferreira

Na verdade, eu tenho sido apontado que

corresponde ao operador de Applicative Functores, e o

S

$\mathbf{S}$ <*>pure

K

$\mathbf{K}$

Hugo Sereno Ferreira

é bastante fundamental, portanto poderia corresponder a muitas coisas.

tem o mesmo tipo que a função mônade

para functor

S

$\mathbf{S}$

S

$\mathbf{S}$

a p

$ap$

Λ X . α \to X

$\Lambda X.\alpha\to X$

Dave Clarke