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 n
razy, 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 ( add1
podano w przykładach, ale to może być add25
, mult7
lub jakakolwiek inna funkcja jednoskładnikowa).
Wynik
Cyfra kościelna. Należy zauważyć, że jeśli m < n
wtedy m - n
jest 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ą.
źródło
exp(m, n)
obliczam^n
oczywiście.)lambda m,n,f:apply f m-n times
(a nawetlambda m,n,f,x:apply f m-n times to x
) zamiastlambda m,n:lambda f:...
? Czy to dotyczy tylko dwóch wejśćm
in
?m
in
w drugiej kolejności? Pomoże to w curry.Odpowiedzi:
Haskell , 35 bajtów
Wypróbuj online!
Powiedz to
r
is
są kodowanie kościelnem
in
. Chcemyr%s
zastosowaćf
m-n
czasy do pewnej wartości początkowejx
. Najpierw generujemy nieskończoną listęnastępnie użyj,
s(x:)
aby wstawićn
kopiex
, to znaczy przesunąć wszystkien
indeksy wartości w prawo:Następnie obliczamy
m
bezpośrednio jakor(+1)0
i bierzemy tenm
element tej listy jako!!r(+1)0
. Zamiast tego mogłoby to zrobić rozwiązanie bez indeksowaniahead$r tail$...
, tzn. Upuszczenie pierwszego elementum
razy, 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.
źródło
Python 2 ,
8280 bajtówWypró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!
źródło
!u:!v:v(!n:!f:!x:n(!g:!h:h(g(f)))(!y:x)(!x:x))(u)
wydaje się , że zapisuje 2 bajty, ale tak naprawdę nie rozumiem kodu!Python 2 , 77 bajtów
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"
...źródło
C ++ (clang) , 112 bajtów
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ę.
źródło
Niedociążenie , 37 bajtów
Wypróbuj online!
Wewnętrzna
(((!())~):*^(~!:(:)~*(*)*)~^^!)
topred
funkcja zaimplementowana parami:źródło
R , 86 bajtów
Wypróbuj online!
Port R odpowiedzi w Pythonie na @ ChasBrown, więc pamiętaj, aby głosować również na tę jedną.
źródło
JavaScript (Node.js) ,
8785817674 bajtyWypró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 zastosowanieh
, podczas gdya=>[x=>x,a]
jest etapem, który nie ma zastosowaniah
. Stosujemyf
czasy pierwszej funkcji i czasy drugiej funkcjig
. Następnie stosujemy odwrotne([f,[g,a]])=>[g(x),a]
f
czasy funkcji . To pomijag
drugie etapy i wykonujef-g
pierwsze 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:
źródło
J , 56 bajtów
Wypróbuj online!
Uwaga: -3 bajty wyłączone dla licznika TIO
m=.
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: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
c
czasownika. Zamiast tego, to opiera się na ogólnej definicji i zamienia każdą Gerund kościół liczebnik powrotem do przysłówek przez odwrócenie go5!: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ę
c
do uzyskania końcowego wyniku: nowej cyfry kościoła w Gerund.źródło
Wolfram Language (Mathematica) ,
55484739 bajtów (33 znaków)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 :
który wygląda tak w interfejsie Mathematica:
Ta funkcja odejmowania działa z cyframi Kościoła zdefiniowanymi za pomocą
(un-golfed:
c[0] = Identity &; c[n_] = Function[a, a@*c[n-1][a]]
)więc mamy
i
źródło