Kirche Subtraktion

Lambda-Kalkül war schon immer eine Faszination von mir und das aufkommende Verhalten, Funktionen ineinander zu übertragen, ist erstaunlich komplex. Kirchenzahlen sind Darstellungen natürlicher Zahlen, die aus der wiederholten Anwendung einer Funktion (normalerweise der unären Addition einer Konstanten) gebildet werden. Zum Beispiel gibt die Zahl Null x zurück und "ignoriert" die Eingabefunktion, eins ist f(x), zwei ist f(f(x))und so weiter:

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

Daraus können wir leicht erkennen, dass die Addition erreicht wird, indem die erste Funktion auf x und dann die zweite Funktion auf x angewendet werden:

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

Das Hinzufügen ist relativ einfach zu verstehen. Für einen Neuling könnte es jedoch unvorstellbar sein, darüber nachzudenken, wie Subtraktion in einem in der Kirche verschlüsselten Zahlensystem aussieht. Was könnte es möglicherweise bedeuten, eine Funktion aufzuheben?

Herausforderung

Implementieren Sie die Subtraktionsfunktion in einem in der Kirche kodierten Zahlensystem. Wobei die Subtraktion die Monus-Operation ausführt und eine Funktion auslöst,n wenn das Ergebnis größer als Null ist oder andernfalls Null. Das ist Code-Golf, also gewinnt der kürzeste Code.

Eingang

Zwei Kirchenzahlen, die in der von Ihnen gewählten Sprache codiert wurden. Die Eingabe kann positions- oder currystrukturiert sein. Um zu beweisen , diese sind wahre Kirche Zahlen sie müssen in irgendeiner Funktion zu übernehmen und anwenden sie wiederholt ( add1wird in den Beispielen gegeben , aber es könnte sein add25, mult7oder jede andere einstellige Funktion.)

Ausgabe

Eine Kirchenzahl. Es ist zu beachten, dass wenn m < ndann m - nimmer die gleiche Identitätsfunktion vorliegt.

Beispiele:

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

auch akzeptabel:

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

Anerkennung:

Dieser Github ist dafür gedacht , mir eine Python-Implementierung von Church Numerals zu geben.

Haskell , 35 Bytes

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

Probieren Sie es online!

Sagen Sie das rund ssind die kirchlichen Kodierungen von mund n. Wir wollen mal auf einen Anfangswert r%sanwenden . Wir erzeugen zuerst die unendliche Listef m-nx

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

Verwenden Sie dann, s(x:)um nKopien von voranzustellen, dh x, um die einzelnen nWertindizes nach rechts zu verschieben:

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

Wir berechnen dann mdirekt als r(+1)0und nehmen das m'te Element dieser Liste als !!r(+1)0. Eine indizierungsfreie Lösung könnte stattdessen head$r tail$...das erste Element mmal löschen und dann das erste Element übernehmen, aber die Indizierungssyntax ist viel kürzer.

Beachten Sie, dass die klassische Lösung in Haskell ohne Erweiterungen nicht funktioniert, da die starke Typisierung nicht die Vorgängeroperation darstellen kann.

Python 2 , 82-80 Bytes

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

Probieren Sie es online!

2 Bytes danke an Nick Kennedy , der ein nicht benötigtes Paar Parens bemerkt.

Anonyme Funktion, die Minus implementiert.

Meist wird nur die Definition auf der Wikipedia-Seite komprimiert. Ich verstehe den Code noch nicht wirklich. Aber interessant!

Python 2 , 77 Bytes

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

Probieren Sie es online!

Wir dekrementieren die Kirche, indem wir den vorherigen Wert für jede Iteration verfolgen und diesen am Ende ausgeben. 39% der Codelänge ist "lambda"'s ...

C ++ (clang) , 112 Bytes

#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)));

Probieren Sie es online!

Dies ist mit Abstand der unverständlichste C ++ - Code, den ich je geschrieben habe. Das heißt, ich denke, dass das Entgolfen dieses Codes es nur noch schlimmer machen wird.

Unterlast , 37 Bytes

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

Probieren Sie es online!

Das Innere (((!())~):*^(~!:(:)~*(*)*)~^^!)ist die predüber Paare implementierte Funktion:

(               ( 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 Bytes

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

Probieren Sie es online!

R port von @ ChasBrowns Python-Antwort .

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

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

Probieren Sie es online! Ich werde keine Preise gewinnen, aber ich dachte, ich würde einen anderen Ansatz ausprobieren.

a=>[h,a]Dies ist eine Phase, die zutrifft h, während dies a=>[x=>x,a]eine Phase ist, die nicht zutrifft h. Wir wenden die ersten Funktionszeiten fund die zweiten Funktionszeiten gan. Wir wenden dann die inversen Funktionszeiten ([f,[g,a]])=>[g(x),a] fan. Dadurch werden die gzweiten Stufen übersprungen und die f-gersten Stufen wie gewünscht ausgeführt. Es bleibt dann der endgültige Wert zu extrahieren.

Die Tupel können natürlich in Lambda-Funktionen konvertiert werden, was den folgenden Ausdruck ergibt:

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 Bytes

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

Probieren Sie es online!

Hinweis: -3 Bytes weniger TIO zählen fürm=.

Funktionen höherer Ordnung in J werden unter Verwendung von Adverbien und Konjunktionen erreicht. Hier ist eine Kirchenzahl die gerundete Form des Adverbs, das durch Kombinieren der "Potenz" der Konjunktion (die wiederholt ein Verb anwendet) und einer ganzen Zahl gebildet wird. Das folgende Verb c(für "create") verwendet Js Atomic Representation, um eine Ganzzahl in ein solches Gerund zu transformieren:

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

Unser "Minus" -Operator (eine Konjunktion) subtrahiert die rechte gerundete Kirchenzahl von der linken. Es wird jedoch keine bestimmte Implementierung von Kirchenzahlen vorausgesetzt, einschließlich der aus unserem cVerb. Stattdessen stützt sie sich auf die allgemeine Definition und dreht sich jede gerund Kirche Ziffer zurück in ein Adverb indem sie sie mit Invertierung 5!:0, und dann diese Adverb dem Inkrement Verb Anwendung >:, und dann die Anwendung , dass auf 0.

Es subtrahiert und nimmt dann das Maximum mit 0 und gilt c, um das Endergebnis zu erhalten: eine neue gerundische Kirchenzahl.

Wolfram Language (Mathematica) , 55 48 47 39 Bytes (33 Zeichen)

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

Probieren Sie es online!

Das Symbol  ist 0xF4A1, ein spezieller Mathematica-Codepunkt, der einen Rechtspfeil für kennzeichnet \[Function]. Sehen Sie hier für weitere Erklärungen. So sieht der Code im Mathematica-Frontend aus:

Wir können dies in 40 Bytes / 32 Zeichen tun , die je nach Messschema kürzer sein können:#2[n⟼f⟼x⟼n[g⟼#@g@f&][x&][#&]]@#&

Die Version ohne Golf ist eine wörtliche Übersetzung der klassischen Definition von 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]

was im Mathematica-Frontend so aussieht:

Diese Subtraktionsfunktion arbeitet mit den mit definierten Kirchenzahlen

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

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

damit wir haben

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]]]]]]}    *)

und

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