Soustraction d'église

Le calcul lambda a toujours été une fascination pour moi et les comportements émergents de passage de fonctions les uns dans les autres sont délicieusement complexes. Les chiffres d'église sont des représentations de nombres naturels obtenus à partir de l'application répétée d'une fonction (normalement l'addition unaire d'une constante). Par exemple, le nombre zéro renvoie x et "ignore" la fonction d'entrée, un est f(x), deux est f(f(x))et ainsi de suite:

ident = lambda x: x
zero = lambda f: ident
succ = lambda n: lambda f: lambda x: f(n(f)(x))
one = succ(zero)
add1 = lambda x: x + 1
to_int = lambda f: f(add1)(0)
print(to_int(one))
>>> 1

De cela, nous pouvons facilement voir que l'addition est accomplie en appliquant la première fonction à x puis en appliquant la deuxième fonction à x:

add = lambda m: lambda n: lambda f: lambda x: n(f)(m(f)(x))
print(to_int(add(one)(two)))
>>> 3

L'addition est relativement facile à comprendre. Cependant, pour un nouveau venu, il pourrait être inconcevable de penser à quoi ressemble la soustraction dans un système numérique codé par l'Église. Qu'est-ce que cela pourrait signifier de ne pas appliquer une fonction?

Défi

Implémentez la fonction de soustraction dans un système numérique encodé par Church. Où la soustraction effectue l' opération monus et désapplique une fonction nfois si le résultat sera supérieur à zéro ou zéro sinon. C'est le code-golf donc le code le plus court gagne.

Contribution

Deux chiffres d'église qui ont été encodés dans votre choix de langue. L'entrée peut être positionnelle ou curry. Pour prouver ces éléments sont vrais chiffres de l' Église , ils doivent prendre en toute fonction et les appliquer à plusieurs reprises ( add1est donné dans les exemples , mais il pourrait être add25, mult7ou toute autre fonction unaire.)

Production

Un chiffre d'église. Il convient de noter que si m < nalors m - nest toujours la même que la fonction d'identité.

Exemples:

minus(two)(one) = one
minus(one)(two) = zero
...

également acceptable:

minus(two, one) = one
minus(one, two) = zero

Crédit:

Ce github est essentiel pour m'avoir donné une implémentation en python des chiffres de l'église.

Haskell , 35 octets

(r%s)f x=s(x:)(iterate f x)!!r(+1)0

Essayez-le en ligne!

Dites cela ret ce ssont les encodages d'église de met n. Nous voulons r%sappliquer des f m-ntemps à une valeur initiale x. Nous générons d'abord la liste infinie

iterate f x = [x, f x, f (f x), f (f (f x)), ...]

puis utilisez s(x:)pour ajouter des ncopies de x, c'est-à-dire déplacer chaque nindice de valeur vers la droite:

s(x:)(iterate f x) = [x, x, x, ...,  x, f x, f (f x), f (f (f x)), ...]

Nous calculons ensuite mdirectement en tant que r(+1)0, et prenons le m'e élément de cette liste comme !!r(+1)0. Une solution sans indexation pourrait le faire head$r tail$..., c'est-à-dire supprimer les premiers mtemps d' élément et ensuite prendre le premier élément, mais la syntaxe d'indexation est beaucoup plus courte.

Notez que la solution classique ne fonctionne pas dans Haskell sans extensions car son typage fort ne peut pas représenter l'opération précédente.

Python 2 , 82 80 octets

eval('!u:!v:v(!n:!f:!x:n(!g:!h:h(g(f)))(!u:x)(!u:u))(u)'.replace('!','lambda '))

Essayez-le en ligne!

Merci à Nick Kennedy de noter une paire de parens inutiles.

Fonction anonyme qui implémente moins.

Généralement, cela ne fait que compresser la définition trouvée sur la page Wikipedia; pas comme si je comprenais vraiment encore le code. Mais intéressant!

Python 2 , 77 octets

lambda r,s:s(lambda r:lambda f:lambda x:r(lambda(_,x):(x,f(x)))((x,x))[0])(r)

Essayez-le en ligne!

Nous décrémentons l'Église en suivant la valeur précédente pour chaque itération et en la sortant à la fin. 39% de la longueur du code est "lambda"...

C ++ (clang) , 112 octets

#define L(x,y)[&](auto x){return y;}
auto m=L(u,L(v,v(L(n,L(f,L(x,n(L(g,L(h,h(g(f)))))(L(u,x))(L(u,u))))))(u)));

Essayez-le en ligne!

C'est de loin le code C ++ le plus incompréhensible que j'aie jamais écrit. Cela dit, je pense que le non-golf de ce code ne fera qu'empirer les choses.

Sous-charge , 37 octets

(~(((!())~):*^(~!:(:)~*(*)*)~^^!)~^^)

Essayez-le en ligne!

L'intérieur (((!())~):*^(~!:(:)~*(*)*)~^^!)est la predfonction, implémentée via des paires:

(               ( start pred function )!
  (
    (!())~      ( push zero below argument )!
  ):*^          ( do that twice )!

  (             ( start pair-increasing function )!
    ~!          ( remove second argument)!
    :           ( duplicate first argument )!
    (:)~*(*)*   ( increment first return value )!
  )
  ~^^           ( run pair-increasing function n times )
  !             ( remove first in returned pair )!
)

R , 86 octets

eval(parse(t=gsub("!(.)","function(\\1)","!u!vv(!n!f!xn(!g!hh(g(f)))(!ux)(!uu))(u)")))

Essayez-le en ligne!

Port R de la réponse Python de @ ChasBrown, alors assurez-vous de voter aussi.

JavaScript (Node.js) , 87 85 81 76 74 octets

f=>g=>h=>x=>f(([x,[g,a]])=>[g(x),a])([x,g(a=>[x=>x,a])(f(a=>[h,a])())])[0]

Essayez-le en ligne! Je ne gagnerai aucun prix, mais j'ai pensé que j'essaierais une approche différente.

a=>[h,a]est une étape qui s'applique h, tandis que a=>[x=>x,a]est une étape qui ne s'applique pas h. Nous appliquons les premiers ftemps de fonction et les seconds gtemps de fonction . Nous appliquons ensuite les ([f,[g,a]])=>[g(x),a] ftemps de fonction inverses . Cela saute les gdeuxièmes étapes et exécute les f-gpremières étapes comme souhaité. Il reste alors à extraire la valeur finale.

Les tuples peuvent bien sûr être convertis en fonctions lambda, ce qui donne l'expression suivante:

f=>g=>h=>x=>f(e=>e(x=>d=>d(g=>a=>e=>e(g(x))(a))))(e=>e(x)(g(a=>e=>e(x=>x)(a))(f(a=>e=>e(h)(a))())))(x=>a=>x)

J , 56 octets

c=:3 :0
t=.^:y
5!:1<'t'
)
m=.2 :'c 0>.(>:u 5!:0->:v 5!:0)0'

Essayez-le en ligne!

Remarque: -3 octets sur le compte TIO pourm=.

Les fonctions d'ordre supérieur dans J sont obtenues à l'aide d'adverbes et de conjonctions. Ici, un chiffre d'église est la forme gérondive de l'adverbe formé en combinant la conjonction «puissance de» (qui applique à plusieurs reprises un verbe) et un entier. Le verbe suivant c(pour "créer") utilise la représentation atomique de J pour transformer un entier en un tel gérondif:

c=:3 :0
t=.^:y
5!:1<'t'
)

Notre opérateur «moins» (qui est une conjonction) soustrait le chiffre de l'église gérondine droite de la gauche. Il ne suppose cependant aucune implémentation particulière des chiffres de l'église, y compris celle de notre cverbe. Au lieu de cela, il s'appuie sur la définition générale et transforme chaque chiffre d'église gerond en un adverbe en l'inversant avec 5!:0, puis en appliquant cet adverbe au verbe d'incrémentation >:, puis en appliquant cela à 0.

Il soustrait ensuite et prend le maximum avec 0, et s'applique cpour obtenir le résultat final: un nouveau chiffre d'église gérondif.

Wolfram Language (Mathematica) , 55 48 47 39 octets (33 caractères)

#2[(fx#[g#@g@f&][x&][#&])&]@#&

Essayez-le en ligne!

Le symbole  est 0xF4A1, un point de code Mathematica spécial qui désigne une flèche vers la droite pour \[Function]. Voir ici pour plus d'explications. Voici à quoi ressemble le code dans le frontal de Mathematica:

Nous pouvons le faire en 40 octets / 32 caractères , ce qui peut être plus court selon le schéma de mesure:#2[n⟼f⟼x⟼n[g⟼#@g@f&][x&][#&]]@#&

La version non-golfée est une traduction littérale de la définition classique de pred :

pred = n \[Function] f \[Function] x \[Function] n[g \[Function] h \[Function] h[g[f]]][u \[Function] x][u \[Function] u];
subtract[m_, n_] := n[pred][m]

qui ressemble à ceci dans le frontal de Mathematica:

Cette fonction de soustraction fonctionne avec les chiffres de l'Église définis avec

c@0=#& &;c@n_=#@*c[n-1][#]&

(non golfed: c[0] = Identity &; c[n_] = Function[a, a@*c[n-1][a]])

pour que nous ayons

Table[c[n][f][x], {n, 0, 6}]
(*    {x, f[x], f[f[x]], f[f[f[x]]], f[f[f[f[x]]]], f[f[f[f[f[x]]]]], f[f[f[f[f[f[x]]]]]]}    *)

et

subtract[c[7],c[5]][f][x]
(*    f[f[x]]    *)