calcul lambda non récursif fonction factorielle

de toute façon, écrivons factoriel

fact := λn. zero? n one (mult n (fact (dec n)))

maintenant, nous ne nous soucions pas particulièrement zero? , mult , dec , ou même one en cet exemple; vous pouvez mettre en œuvre ceux sur votre propre – nous voulons juste supprimer le bolded, by-name récursion,

... fact (dec n)

la façon la plus facile de faire cela est d'appliquer une lambda à lui-même-répondre à la U combinator

U := λf. f f

maintenant, nous pouvons envelopper notre expression originale dans une lambda, et appliquer U

fact := U (λf. λn. zero? n one (mult n (??? (dec n))))

mais qu'est-ce qu'on met à la place de fact ??? – Rappeler que f est une référence à la lambda externe elle-même, donc pour que ce soit le même cas dans la prochaine "itération", nous devons appliquer f à lui-même, tout comme U fait-en fait, vous pouvez penser à U comme une sorte de miroir, et votre fonction peut réfléchir en arrière dans ce miroir afin de revenir; seulement cette fois, sans utiliser un nom ^ _ ^

fact := U (λf. λn. zero? n one (mult n (f f (dec n))))

Oui, Oui, mais le plus astucieux remarquera que vous peut utiliser le miroir ( U ) directement à l'intérieur de la lambda ,aussi

fact := U (λf. λn. zero? n one (mult n (U f (dec n))))

élargi sans U

nous savons comment étendre l'intérieur – nous l'avons écrit de cette façon la première fois

fact := U (λf. λn. zero? n one (mult n (f f (dec n))))

élargissez maintenant L'extérieur U

fact := (λf. λn. zero? n one (mult n (f f (dec n)))) (λf. λn. zero? n one (mult n (f f (dec n))))

ça marche?

tous les chiffres d'Église représentés par #n

fact := U λf. λn. zero? n #1 (mult n (U f (dec n)))

fact #4

U (λf. λn. zero? n #1 (mult n (U f (dec n))) #4

(λf. f f) (λf. λn. zero? n #1 (mult n (U f (dec n))) #4

(λf. λn. zero? n #1 (mult n (U f (dec n))) (λf. λn. zero? n #1 (mult n (U f (dec n))) #4

(λn. zero? n #1 (mult n (U (λf. λn. zero? n #1 (mult n (U f (dec n))) (dec n))) #4

zero? #4 #1 (mult #4 (U (λf. λn. zero? n #1 (mult n (U f (dec n))) (dec #4)))

zero? #4 #1 (mult #4 (U (λf. λn. zero? n #1 (mult n (U f (dec n))) (dec #4)))

// (zero? #4); false; returns second argument
(mult #4 (U (λf. λn. zero? n #1 (mult n (U f (dec n))) (dec #4)))

// which is #4 * ...
(U (λf. λn. zero? n #1 (mult n (U f (dec n))) (dec #4))

// which is ...
(U (λf. λn. zero? n #1 (mult n (U f (dec n))) #3)

// which is equivalent to...
fact #3

// so ...
(mult #4 (fact #3))

// repeating this pattern ...
(mult #4 (mult #3 (fact #2))
(mult #4 (mult #3 (mult #2 (fact #1)))
(mult #4 (mult #3 (mult #2 (mult #1 (fact #0))))
(mult #4 (mult #3 (mult #2 (mult #1 #1))))
(mult #4 (mult #3 (mult #2 #1)))
(mult #4 (mult #3 #2))
(mult #4 #6)
#24

démonstration en javascript

allez-y et regardez la puissance du combinateur U avec vos propres yeux !

const U =
  f => f (f)
  
const fact =
  U (f => n =>
    n === 0 ? 1 : n * U (f) (n - 1))
    
console.log (fact (4)) // 24

et de nouveau comme une expression pure lambda

console.log (
  (f => n => n === 0 ? 1 : n * f (f) (n - 1))
    (f => n => n === 0 ? 1 : n * f (f) (n - 1))
      (4)
) // 24

mutuelle récursion

l'extrait ci-dessus démontre une propriété très importante de ce processus récursif: c'est mutuellement récursif . Comme vous pouvez le voir, il y a en fait deux (bien que les mêmes) fonctions de commande de la récursion; A appelle B, B appelle A-cependant dans le cas du combinateur U, il n'y a que un fonction qui s'applique à lui-même, ainsi il fait dans fait activer récursion directe – la lambda ne s'appelle en utilisant son paramètre , pas son nom (lambdas n'ont pas de nom à appeler)

Y ?

parce que je l'ai dit

le combinateur U est un peu encombrant parce qu'il attend de l'utilisateur de "refléter" la fonction afin de – et si nous pouvions fournir à la lambda externe une fonction qui est le miroir lui-même ?

U := λf. f f
Y := λg. U (λf. g (U f))

je vais vous montrer la même définition encore une fois, mais sur deux lignes juste pour que vous puissiez voir les "miroirs" et leurs positions

          / g, user's function
         /
        /  / outer reflection
       /  /
Y := λg. U (λf.   ...   )
                g (U f)
                 \
                  \ call g with inner reflection

ainsi maintenant, chaque fois que vous appliquez Y à n'importe quelle lambda ( g ), son paramètre devient la fonction pour calculer la lambda elle-même-changeant fact à

fact := Y (λf. λn. zero? n one (mult n (f (dec n))))

expansion Y

Y := λg. U (λf. g (U f))             // expand inner U
Y := λg. U (λf. g (f f))             // expand outer U
Y := λg. (λf. g (f f)) (λf. g (f f))

qui est la définition que vous voyez là dans wikipedia; juste alpha-rebaptisé

je viens d'avoir une profonde découverte

dérivé de Y de U ci-dessus, j'ai vu quelque chose que je n'ai jamais vu avant - a caché B

Y := λg. U (λf. g (U f))

B := λf. λg. λx. f (g x)

Y' := λg. U (B g U)

L'une des plus belles choses que j'ai jamais vu – et il fonctionne trop ; non pas que nous devrions avoir n'importe quelle raison de penser qu'il ne serait pas...

#lang lazy

(define B (λ (f)
            (λ (g)
              (λ (x)
                (f (g x))))))

(define U (λ (f)
            (f f)))

(define Y (λ (g)
            (U ((B g) U))))

(define fact (Y (λ (f)
                  (λ (n)
                    (if (= n 0)
                        1
                        (* n (f (sub1 n))))))))

(fact 4) ;; 24

Haskellers

avez-vous déjà vu Y s'exprimer comme?

Y = U . (. U)
  where U f = f f