Odejmowanie Kościoła

Rachunek Lambda zawsze był moją fascynacją, a pojawiające się zachowania polegające na przekazywaniu sobie funkcji są zachwycająco złożone. Liczby kościelne są reprezentacjami liczb naturalnych skonstruowanych w wyniku wielokrotnego zastosowania funkcji (zwykle jednoargumentowego dodania stałej). Na przykład liczba zero zwraca x i „ignoruje” funkcję wejściową, jedna to f(x)dwie, druga f(f(x))itd.:

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

Z tego możemy łatwo zobaczyć, że dodawanie odbywa się poprzez zastosowanie pierwszej funkcji do x, a następnie zastosowanie drugiej funkcji do x:

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

Dodawanie jest stosunkowo łatwe do zrozumienia. Jednak dla nowoprzybyłego może być nie do pomyślenia, jak wygląda odejmowanie w systemie liczbowym zakodowanym w Kościele. Co może oznaczać cofnięcie zastosowania funkcji?

Wyzwanie

Zaimplementuj funkcję odejmowania w zakodowanym w kościele systemie liczbowym. Gdzie odejmowanie wykonuje operację monus i nie stosuje funkcji nrazy, jeśli w przeciwnym razie wynik będzie większy niż zero lub zero. To jest golf golfowy, więc wygrywa najkrótszy kod.

Wejście

Dwie cyfry kościelne zakodowane w wybranym przez ciebie języku. Wejście może być pozycyjne lub curry. Aby udowodnić te są prawdziwe cyfry kościelne będą musieli podjąć w dowolnej funkcji i zastosować je wielokrotnie ( add1podano w przykładach, ale to może być add25, mult7lub jakakolwiek inna funkcja jednoskładnikowa).

Wynik

Cyfra kościelna. Należy zauważyć, że jeśli m < nwtedy m - njest zawsze taki sam jak funkcja tożsamości.

Przykłady:

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

dopuszczalne również:

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

Kredyt:

Ten github ma za zadanie zaimplementować w języku Python numerację kościelną.

Haskell , 35 bajtów

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

Wypróbuj online!

Powiedz to ri ssą kodowanie kościelne mi n. Chcemy r%szastosować f m-nczasy do pewnej wartości początkowej x. Najpierw generujemy nieskończoną listę

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

następnie użyj, s(x:)aby wstawić nkopie x, to znaczy przesunąć wszystkie nindeksy wartości w prawo:

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

Następnie obliczamy mbezpośrednio jako r(+1)0i bierzemy ten melement tej listy jako !!r(+1)0. Zamiast tego mogłoby to zrobić rozwiązanie bez indeksowania head$r tail$..., tzn. Upuszczenie pierwszego elementu mrazy, a następnie pobranie pierwszego elementu, ale składnia indeksowania jest znacznie krótsza.

Zauważ, że klasyczne rozwiązanie nie działa w Haskell bez rozszerzeń, ponieważ jego mocne pisanie nie może reprezentować poprzedniej operacji.

Python 2 , 82 80 bajtów

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

Wypróbuj online!

2 bajki dzięki Nickowi Kennedy'emu, zwracając uwagę na niepotrzebną parę parenów.

Anonimowa funkcja, która implementuje minus.

Przeważnie jest to tylko kompresja definicji znalezionej na stronie Wikipedii; nie tak, że naprawdę rozumiem jeszcze kod. Ale ciekawe!

Python 2 , 77 bajtów

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

Wypróbuj online!

Dokonujemy dekrementacji Kościoła, śledząc poprzednią wartość dla każdej iteracji i wyprowadzając ją na końcu. 39% długości kodu to "lambda"...

C ++ (clang) , 112 bajtów

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

Wypróbuj online!

To zdecydowanie najbardziej niezrozumiały kod C ++, jaki kiedykolwiek napisałem. To powiedziawszy, myślę, że odkrycie tego kodu tylko pogorszy sprawę.

Niedociążenie , 37 bajtów

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

Wypróbuj online!

Wewnętrzna (((!())~):*^(~!:(:)~*(*)*)~^^!)to predfunkcja zaimplementowana parami:

(               ( 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 bajtów

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

Wypróbuj online!

Port R odpowiedzi w Pythonie na @ ChasBrown, więc pamiętaj, aby głosować również na tę jedną.

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

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

Wypróbuj online! Nie zdobędę żadnych nagród, ale pomyślałem, że spróbuję innego podejścia.

a=>[h,a]jest etapem, który ma zastosowanie h, podczas gdy a=>[x=>x,a]jest etapem, który nie ma zastosowania h. Stosujemy fczasy pierwszej funkcji i czasy drugiej funkcji g. Następnie stosujemy odwrotne ([f,[g,a]])=>[g(x),a] fczasy funkcji . To pomija gdrugie etapy i wykonuje f-gpierwsze etapy według potrzeb. Następnie pozostaje wyodrębnić ostateczną wartość.

Krotki można oczywiście przekonwertować na funkcje lambda, co daje następujące wyrażenie:

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 bajtów

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

Wypróbuj online!

Uwaga: -3 bajty wyłączone dla licznika TIOm=.

Funkcje wyższego rzędu w J uzyskuje się za pomocą przysłówków i spójników. Cyfra kościelna to tutaj forma gerunda przysłówka utworzona przez połączenie koniunkcji „moc” (która wielokrotnie stosuje czasownik) i liczby całkowitej. Poniższy czasownik c(dla „create”) używa reprezentacji atomowej J do przekształcenia liczby całkowitej w taki gerund:

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

Nasz operator „minus” (który jest koniunkcją) odejmuje prawą cyfrę kościoła gerund od lewej. Nie zakłada jednak żadnej konkretnej realizacji liczb kościelnych, w tym tej z naszego cczasownika. Zamiast tego, to opiera się na ogólnej definicji i zamienia każdą Gerund kościół liczebnik powrotem do przysłówek przez odwrócenie go 5!:0, a następnie zastosowanie tego przysłówka do czasownika przyrost >:, a następnie zastosowanie , że na 0.

Następnie odejmuje i przyjmuje maksimum z 0, i stosuje się cdo uzyskania końcowego wyniku: nowej cyfry kościoła w Gerund.

Wolfram Language (Mathematica) , 55 48 47 39 bajtów (33 znaków)

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

Wypróbuj online!

Symbolem 0x jest 0xF4A1, specjalny punkt kodu Mathematica, który oznacza strzałkę w prawo dla \[Function]. Zobacz więcej wyjaśnień. Oto jak wygląda kod w interfejsie Mathematica:

Możemy to zrobić w 40 bajtach / 32 znakach , które mogą być krótsze w zależności od schematu pomiarowego:#2[n⟼f⟼x⟼n[g⟼#@g@f&][x&][#&]]@#&

Wersja bez golfa jest dosłownym tłumaczeniem klasycznej definicji 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]

który wygląda tak w interfejsie Mathematica:

Ta funkcja odejmowania działa z cyframi Kościoła zdefiniowanymi za pomocą

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

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

więc mamy

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

i

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