Pengurangan Gereja

Kalkulus Lambda selalu menjadi daya tarik saya dan perilaku yang muncul dari fungsi saling melintas sangat menyenangkan. Angka Gereja adalah representasi dari bilangan asli yang dibangun dari penerapan fungsi berulang (biasanya penambahan konstanta unary). Sebagai contoh, angka nol mengembalikan x dan "mengabaikan" fungsi input, satu adalah f(x), dua adalah f(f(x))dan seterusnya:

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

Dari sini kita dapat dengan mudah melihat bahwa penambahan dilakukan dengan menerapkan fungsi pertama ke x kemudian menerapkan fungsi kedua ke x:

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

Selain itu relatif mudah dimengerti. Namun, bagi pendatang baru, mungkin tidak masuk akal untuk memikirkan seperti apa pengurangan dalam sistem angka Gereja yang dikodekan. Apa yang mungkin berarti membatalkan penerapan suatu fungsi?

Tantangan

Menerapkan fungsi pengurangan dalam sistem angka Gereja yang dikodekan. Di mana pengurangan melakukan operasi monus dan membatalkan penerapan fungsi nkali jika hasilnya akan lebih besar dari nol atau nol sebaliknya. Ini adalah kode-golf sehingga kode terpendek menang.

Memasukkan

Dua angka Gereja yang telah dikodekan dalam pilihan bahasa Anda. Input dapat berupa posisi atau kari. Untuk membuktikan ini angka Gereja yang benar mereka akan harus mengambil di setiap fungsi dan menerapkannya berulang kali ( add1diberikan dalam contoh tapi bisa add25, mult7, atau fungsi unary lainnya.)

Keluaran

Angka Gereja. Perlu dicatat bahwa jika m < ndemikian m - nselalu sama dengan fungsi identitas.

Contoh:

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

juga dapat diterima:

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

Kredit:

Intisari github ini untuk memberi saya implementasi python Angka Gereja.

Haskell , 35 byte

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

Cobalah online!

Katakan itu rdan smerupakan penyandian gereja dari mdan n. Kami ingin r%smenerapkan f m-nwaktu pada beberapa nilai awal x. Kami pertama-tama menghasilkan daftar tanpa batas

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

lalu gunakan s(x:)untuk menambahkan nsalinan x, yaitu, menggeser setiap nindeks nilai dengan benar:

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

Kami kemudian menghitung msecara langsung sebagai r(+1)0, dan mengambil melemen ke-10 dari daftar itu sebagai !!r(+1)0. Sebaliknya head$r tail$..., solusi pengindeksan bisa dilakukan , yaitu menjatuhkan elemen mkali pertama dan kemudian mengambil elemen pertama, tetapi sintaks pengindeksan jauh lebih pendek.

Perhatikan bahwa solusi klasik tidak berfungsi di Haskell tanpa ekstensi karena pengetikan yang kuat tidak dapat mewakili operasi pendahulunya.

Python 2 , 82 80 byte

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

Cobalah online!

2 byte thx untuk Nick Kennedy mencatat sepasang orangtua yang tidak dibutuhkan.

Fungsi anonim yang mengimplementasikan minus.

Sebagian besar ini hanya mengompresi definisi yang ditemukan di halaman Wikipedia; tidak seperti saya benar-benar mengerti kodenya. Tapi menarik!

Python 2 , 77 byte

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

Cobalah online!

Kami melakukan pengurangan Gereja dengan melacak nilai sebelumnya untuk setiap iterasi dan menghasilkan yang pada akhirnya. 39% dari panjang kode adalah "lambda"...

C ++ (dentang) , 112 byte

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

Cobalah online!

Sejauh ini ini adalah kode C ++ yang paling tidak bisa dipahami yang pernah saya tulis. Yang mengatakan, saya pikir bahwa melanggar kode ini hanya akan membuatnya lebih buruk.

Underload , 37 byte

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

Cobalah online!

Batin (((!())~):*^(~!:(:)~*(*)*)~^^!)adalah predfungsi, diimplementasikan melalui pasangan:

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

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

Cobalah online!

Port R dari jawaban Python @ ChasBrown jadi pastikan untuk mengunggahnya juga.

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

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

Cobalah online! Tidak akan memenangkan penghargaan apa pun, tetapi saya pikir saya akan mencoba pendekatan yang berbeda.

a=>[h,a]adalah tahap yang berlaku h, sementara itu a=>[x=>x,a]adalah tahap yang tidak berlaku h. Kami menerapkan waktu fungsi pertama fdan waktu fungsi kedua g. Kami kemudian menerapkan waktu fungsi terbalik ([f,[g,a]])=>[g(x),a] f. Ini melompati gtahap kedua dan melakukan f-gtahap pertama seperti yang diinginkan. Kemudian tetap mengekstraksi nilai akhir.

Tupel tentu saja dapat dikonversi ke fungsi lambda yang menghasilkan ekspresi berikut:

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 byte

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

Cobalah online!

Catatan: -3 byte dari hitungan TIO untukm=.

Fungsi tingkat tinggi dalam J dicapai menggunakan kata keterangan dan kata sambung. Di sini angka gereja adalah bentuk gerund dari kata keterangan yang dibentuk dengan menggabungkan "kekuatan" konjungsi (yang berulang kali menggunakan kata kerja) dan bilangan bulat. Kata kerja berikut c(untuk "buat") menggunakan Representasi Atom J untuk mengubah bilangan bulat menjadi gerund seperti itu:

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

Operator "minus" kami (yang merupakan gabungan) mengurangi angka gereja gerund kanan dari kiri. Namun, itu tidak mengasumsikan implementasi tertentu dari angka gereja, termasuk yang dari ckata kerja kami . Sebaliknya, hal itu bergantung pada definisi umum dan ternyata setiap gereja gerund angka kembali ke kata keterangan dengan membalik dengan 5!:0, dan kemudian menerapkan keterangan bahwa untuk kata kerja kenaikan >:, dan kemudian menerapkan bahwa untuk 0.

Itu kemudian mengurangi dan mengambil maksimum dengan 0, dan berlaku cuntuk mendapatkan hasil akhir: angka gereja gerund baru.

Bahasa Wolfram (Mathematica) , 55 48 47 39 byte (33 karakter)

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

Cobalah online!

Simbol  adalah 0xF4A1, titik kode Mathematica khusus yang menunjukkan panah kanan untuk \[Function]. Lihat di sini untuk penjelasan lebih lanjut. Seperti apa kode ini di front end Mathematica:

Kita dapat melakukannya dalam 40 byte / 32 karakter , yang mungkin lebih pendek tergantung pada skema pengukuran:#2[n⟼f⟼x⟼n[g⟼#@g@f&][x&][#&]]@#&

Versi un-golfed adalah terjemahan literal dari definisi klasik dari 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]

yang terlihat seperti ini di bagian depan Mathematica:

Fungsi pengurangan ini berfungsi dengan angka-angka Gereja yang ditentukan dengan

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

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

sehingga kita miliki

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

dan

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