lambda calcul en scala

Question

OK, donc j'essaie d'implémenter le basics of lambda calculus. Ici ça va.

Mes numéros:

def zero[Z](s: Z => Z)(z: Z): Z = z 
def one[Z](s: Z => Z)(z: Z): Z = s(z) 
def two[Z](s: Z => Z)(z: Z): Z = s(s(z)) 

partiellement (en fait, non) appliquée la version d'entre eux est lissée comme ça:

def z[Z]: (Z => Z) => (Z => Z) = zero _ 

Avant de poursuivre, je définir certains types:

type FZ[Z] = Z => Z 
type FFZ[Z] = FZ[Z] => FZ[Z] 

Fine, succ fonctionne comme (l'ordre d'application doit être exactement comme ça! Je pris la définition here):

def succ[Z](w: FFZ[Z])(y: FZ[Z])(x: Z): Z = y((w(y))(x)) 

Et la version non appliquée, il devient aussi effrayant que:

def s[Z]: FFFZ[Z] = successor _ 

Je vous demande pardon, voici les types manquants:

type FFFZ[Z] = FFZ[Z] => FFZ[Z] 
type FFFFZ[Z] = FFFZ[Z] => FFFZ[Z] 

Mais Je suis bloqué à la fonction add. Si vous conformez aux types et la définition (prise here aussi bien), il va comme

def add[Z](a: FFFFZ[Z])(b: FFZ[Z]): FFZ[Z] = 
    (a(s))(b) 

Mais je veux a d'être un numéro commun de type FFZ[Z]. Alors, comment puis-je définir l'addition?

Answer 1

Il est tout à fait possible d'implémenter des chiffres d'église à Scala. Voici une telle mise en œuvre plutôt straight-forward:

object ChurchNumerals { 

    type Succ[Z] = Z => Z 
    type ChNum[Z] = Succ[Z] => Z => Z 

    def zero[Z]: ChNum[Z] = 
    (_: Succ[Z]) => (z: Z) => z 

    def succ[Z] (num: ChNum[Z]): ChNum[Z] = 
    (s: Succ[Z]) => (z: Z) => s(num(s)(z)) 

    // a couple of church constants 
    def one[Z] : ChNum[Z] = succ(zero) 
    def two[Z] : ChNum[Z] = succ(one) 

    // the addition function 
    def add[Z] (a: ChNum[Z]) (b: ChNum[Z]) = 
    (s: Succ[Z]) => (z: Z) => a(s)(b(s)(z)) 

    def four[Z] : ChNum[Z] = add(two)(two) 

    // test 
    def church_to_int (num: ChNum[Int]): Int = 
    num((x: Int) => x + 1)(0) 

    def fourInt: Int = church_to_int(four) 

    def main(args: Array[String]): Unit = { 
    println(s"2 + 2 = ${fourInt}") 
    } 
} 

Compile et impressions:

$ scala church-numerals.scala 
2 + 2 = 4 

Si je devais expliquer les chiffres de l'Église à partir de zéro, je rajouterais plus de commentaires. Mais en tenant compte du contexte, je ne suis pas sûr de quoi commenter dans ce cas. N'hésitez pas à demander et j'ajouterai plus d'explications.

Answer 2

J'ai codé les nombres, les booléens et les paires: https://github.com/pedrofurla/church/blob/master/src/main/scala/Church.scala suivant le style de l'église. Une chose que j'ai remarquée est que l'utilisation de la syntaxe de fonction curry était beaucoup plus facile que l'utilisation de plusieurs listes d'arguments.Certains des extraits intéressants

type NUM[A] = (A => A) => A => A 
def succ [A]: NUM[A] => NUM[A] = m => n => x => n(m(n)(x)) 
def zero [A]: NUM[A] = f => x => x 
def one [A]: NUM[A] = f => x => f(x) 
def two [A]: NUM[A] = f => x => f(f(x)) 
def three [A]: NUM[A] = f => x => f(f(f(x))) 
def plus [A]: (NUM[A]) => (NUM[A]) => NUM[A] = m => n => f => x => m(f)(n(f)(x)) 

Maintenant, pour les imprimer (très similaire à la solution de Antov Trunov):

def nvalues[A] = List(zero[A], one[A], two[A], three[A]) 

val inc: Int => Int = _ + 1 
def num: (NUM[Int]) => Int = n => n(inc)(0) 
def numStr: (NUM[String]) => String = n => n("f (" + _ + ") ")("z") 

Quelques sortie:

scala> println(nvalues map num) 
List(0, 1, 2, 3) 

scala> println(nvalues map numStr) // Like this better :) 
List(z, f (z) , f (f (z)) , f (f (f (z))))