Tantangan
Temukan ekspresi, paling panjang 100 byte, dengan tipe tanda tangan terpanjang.
Aturan
- Setiap bahasa yang diketik secara statis dengan inferensi tipe diperbolehkan
- Jenisnya harus non-ambigu, tetapi selain itu dapat menyertakan jenis tanpa instans yang ditentukan. Misalnya
Num [a]
danEq [a]
diizinkan, bahkan tanpa instance yang ditentukan - Tidak ada impor selain dari minimum yang diperlukan untuk mengkompilasi program dengan STDIN / STDOUT
- Jenis yang tidak terbatas tidak diperbolehkan
- Jika jawaban memiliki lebih dari satu ekspresi, hanya satu yang dapat berkontribusi pada skor. Misalnya, meskipun jenis tanda tangan komposisi adalah
(.) :: (b -> c) -> (a -> b) -> a -> c
, memiliki skor 20, jawaban dengan 25 salinan(.)\n
akan memiliki skor 20, bukan 500 - Ekspresi paling banyak harus 100 byte
- Skor adalah jumlah karakter dalam tipe tanda tangan, tidak termasuk nama fungsi dan spasi putih apa pun. Misalnya,
f :: (a -> b) -> a -> b
akan memiliki skor 12 - Skor tertinggi menang!
Contohnya
Meskipun bahasa lain diperbolehkan, contoh-contoh berikut ada di Haskell:
Score: 112
map.map.map.map.map.map.map.map.map.map.map.map.map.map.map.map.map.map.map.map.map.map.map.map.map
f :: (a -> b)
-> [[[[[[[[[[[[[[[[[[[[[[[[[a]]]]]]]]]]]]]]]]]]]]]]]]]
-> [[[[[[[[[[[[[[[[[[[[[[[[[b]]]]]]]]]]]]]]]]]]]]]]]]]
Score: 240
(.).(.).(.).(.).(.).(.).(.).(.).(.).(.).(.).(.).(.).(.).(.).(.).(.).(.).(.).(.).(.).(.).(.).(.).(.)
f :: (b->c)->(a->a1->a2->a3->a4->a5->a6->a7->a8->a9->a10->a11->a12->a13->a14->a15->a16->a17->a18->a19->a20->a21->a22->a23->a24->b)->a1->a2->a3->a4->a5->a6->a7->a8->a9->a10->a11->a12->a13->a14->a15->a16->a17->a18->a19->a20->a21->a22->a23->a24->c
Score: 313
foldl$foldl$foldl$foldl$foldl$foldl$foldl$foldl$foldl$foldl$foldl$foldl$foldl$foldl$foldl$foldl(.)
f :: (Foldable t, Foldable t1, Foldable t2, Foldable t3, Foldable t4,
Foldable t5, Foldable t6, Foldable t7, Foldable t8, Foldable t9,
Foldable t10, Foldable t11, Foldable t12, Foldable t13,
Foldable t14, Foldable t15) =>
(b -> c)
-> t (t1 (t2 (t3 (t4 (t5 (t6 (t7 (t8 (t9 (t10 (t11 (t12 (t13 (t14 (t15 (b
-> b))))))))))))))))
-> b
-> c
Score: 538
lex.show.foldl1.mapM.traverse.sum.mapM.sum.traverse.(.).mapM.scanl.zipWith3((.traverse).(.traverse))
(Num
(a -> ([[c]] -> t3 [[a1 -> f b]]) -> [[c]] -> t3 [[a1 -> f b]]),
Num
(([[c]] -> t3 [[a1 -> f b]])
-> t1 (t2 ([[c]] -> t3 [[a1 -> f b]]))
-> [[c]]
-> t3 [[a1 -> f b]]),
Show
(t (t1 (t2 ([[c]] -> t3 [[a1 -> f b]])))
-> t1 (t2 ([[c]] -> t3 [[a1 -> f b]]))),
Applicative f, Foldable t,
Foldable ((->) (t1 (t2 ([[c]] -> t3 [[a1 -> f b]])) -> a)),
Foldable
((->) (([[c]] -> t3 [[a1 -> f b]]) -> a -> t3 [a1 -> f b])),
Traversable t1, Traversable t2, Traversable t3, Traversable t4,
Traversable t5,
Traversable ((->) (t1 (t2 ([[c]] -> t3 [[a1 -> f b]])))),
Traversable ((->) ([[c]] -> t3 [[a1 -> f b]]))) =>
[(t5 (t4 a1) -> f (t5 (t4 b))) -> c -> a1 -> f b]
-> [(String, String)]
code-challenge
busy-beaver
functional-programming
Michael Klein
sumber
sumber
Jawaban:
Haskell, ~ 2 ^ (2 ^ 18)
Setiap aplikasi secara
f
kasar menggandakan tanda tangan jenis dengan mentransformasikan tanda tangan tipeT
menjadi(T,T)
. Misalnya, komposisi empat kali lipatf.f.f.f$0
memiliki tipeSetiap baris melipatgandakan jumlah aplikasi
f
, memberi4^9 = 2^18
di akhir. Jadi, tipe tanda tangan memiliki ukuran urutan2^(2^18)
.sumber
f x=(x,x,x)
dengan mengorbankan satun.
di baris terakhir memberikan skor optimal untuk struktur keseluruhan ini.n.
akan menjadi lebih besar.2^18
vs3 * (2^16)
kecuali saya membuat kesalahan menghitung eksponensial asli:2^(4^9)
vs3^((4^8)*3)
(,)
(atau(,,)
) dapat digunakan untuk menyimpan beberapa byte dan meningkatkan skor dengan menggunakan lebih banyakn
s.Jawa, skor 17301488
Membutuhkan metode
<T>java.util.Map<T,T>f(T t){return null;}
, yang telah dihitung menuju batas 100 byte.f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(1)))))))))))))))))))
Jenis tanda tangan waktu kompilasi harus cocok dengan ini.
sumber
Haskell dengan ekstensi,⋙A(A(A(A(220,0),0),0),0)
Cobalah online!
Membutuhkan
-XDataKinds
,-XPolyKinds
,-XTypeOperators
,-XUndecidableInstances
, dan-XTypeFamilies
.Terima kasih banyak kepada Ørjan Johansen, yang menyadari bahwa membuat bilangan alami pembangun infiks dan membangun argumen sedikit berbeda menghemat dua byte, membuat cukup ruang untuk pengulangan lain
#
.Jelas, pemeriksa tipe akan menyerah mencoba memeriksa program ini. Untuk mendapatkan gambaran umum tentang bagaimana tanda tangan itu akan terlihat (jika cukup kecil untuk muat di alam semesta yang dapat diamati), cobalah yang lebih kecil
Penjelasan
KeluargaSEBUAH , tetapi
#
tipe terkait erat dengan fungsi Ackermann-Péter , umumnya ditulis#
tumbuh jauh lebih cepat. Fungsi Ackermann – Péter didefinisikan#
, di sisi lain, kita dapat memanggilHanya kasus kedua yang berbeda. Bukti terminasi identik dengan standar untukA , dan harus jelas bahwa B(m,n)≥A(m,n) untuk semua m dan n .
Di sini kita menghitung representasi unary dari
Dengan perhitungan langsung,B(B(B(B(0,0),0),0),0)=220 , jadi
Perhatikan bahwaA ( A ( A ( A ( 0 , 0 ) , 0 ) , 0 ) , 0 ) hanya 5 , jadi kami telah memulai beberapa hal yang baik untuk memulai). Saya tidak memiliki kepekaan yang jelas tentang seberapa cepat B tumbuh lebih cepat daripada SEBUAH , tetapi mengingat bagaimana kalkulasinya berlangsung, sepertinya akan tumbuh jauh lebih cepat.
Jumlah digit bahkan dalamA ( 6 , 0 ) terlalu besar untuk diekspresikan secara praktis dalam desimal, jadi ini ... agak besar.
Definisi bilangan asli,,
(?)
agak tidak standar. Untuk menghemat ruang, kami menggunakan(?)
keduanya sebagai tipe bilangan alami (pada level tipe) dan tipe proxy (pada level term).Saya percaya bahwa salah satu
TypeFamilies
atau (lebih secara verbal dan tidak jelas)FunctionalDependencies
diperlukan untuk mendapatkan perhitungan tipe-tingkat yang diperlukan untuk mencapai tipe yang benar-benar besar.UndecidableInstances
diperlukan untuk bekerja di sekitar pengecekan terminasi Haskell yang sangat primitif. Ekstensi lain hanya diperlukan untuk memampatkan kode ke dalam ruang kecil yang tersedia.sumber
#Z
Z
di depan lebih baik daripada memulainyaS(S Z)#S Z
, atau sama?#Z
di akhir disambut.?
menyimpan yang lain, meninggalkan ruang untuk ekstra#Z
.A(m,1)
tidak pernah lebih besar dariA(A(m,0),0)
, dan akan berkomentar tentang itu, tapi kemudian Anda hanya dioptimalkan ke titik di mana opsi-opsi sama. (Jugam+1
tidak pernah lebih besar dariA(m,0)
.)Haskell, 9 · 2 663552 - 3 (≈ 1.02 · 10 199750 )
Peningkatan kecil ("kecil") di atas xnor's 5⋅2 262144 + 5 . Ini adalah 99 byte.
Bagaimana itu bekerja
Kita punya
dan seterusnya, dengan panjang kira-kira dua kali lipat untuk masing-masing
(:)
. Ungkapan yang diberikano.o.o
berhasil(:).(:).(:).….(:)
dengan 2 · 4 6 · 3 4 = 663552 salinan(:)
.Haskell dengan
FlexibleContexts
danNoMonomorphismRestriction
, (200 · 4 331776 + 75 · 331776 + 16) / 9 ≈ 2,53 · 10 199750Sebuah perbaikan kecil dibandingkan Bubbler's 12 · 2 663552 + 9 · 663552 - 4 ≈ 1,36 · 10 199750 , yang juga bergantung pada ekstensi ini. Kata-kata dari jenis tantangan menyarankan mungkin bergantung pada mereka ("Sebagai contoh
Num [a]
danEq [a]
diizinkan, bahkan tanpa contoh yang ditentukan"); Saya tidak yakin. Ini adalah 100 byte.Bagaimana itu bekerja
Kita punya
dan seterusnya, dengan panjang kira-kira empat kali lipat untuk masing-masing
(/).(:)
. Ungkapan yang diberikan-o.o.o
berhasil-(/).(:).(/).(:).….(/).(:)
dengan 4 6 · 3 4 = 331776 salinan(/).(:)
.sumber
Haskell, 12 · 2 663552 + 9 · 663552 - 4
Namun peningkatan kecil lainnya atas jawaban Anders Kaseorg .
Bagaimana itu bekerja
Hanya mengubah komposisi fungsi
(.)
menjadi pembagian fraksional(/)
. BagianFractional x
dalam tanda tangan fungsi meledak bersama dengan bagian utama, memberikan pengali konstan sedikit lebih tinggi.sumber
C, 979
f
memiliki tanda tangan:sumber
C ++ 11, tidak bersaing
Saya hampir tidak bisa mendapatkan ini di bawah 100 byte, tetapi begitu dekat saya pikir saya mungkin mempostingnya, dengan harapan seseorang melihat optimasi.
Ini adalah prolog, dengan biaya 93 byte:
Dan ungkapannya, 9 byte:
Menggambarkan:
Menggandakan secara kasar setiap kali jumlahnya meningkat.
sumber
class
alih-alihtypename
. Saya bertanya-tanya apakah ada kompiler di luar sana yang masih mendukung ungkapan itu untuk kompatibilitas?C #, 363
Ekspresi:
Jenis tanda tangan:
Cobalah online!
sumber
Go 1.0 tanpa
reflect
, 98Tipe Go 1.x didefinisikan secara statis. Ini adalah percobaan pertama saya:
Arena bermain On the Go :
Go 1.9 menggunakan alias type, 2389
Arena bermain On the Go :
Hasil:
Go 1 using
reflect
, 65532Ada batas dalam paket
reflect
pada panjang nama jenis:len(name) <= 1<<16-1
Sejauh ini saya telah mencapai nama jenis 65532 byte dengan blok ini:
Kode lengkap di taman bermain Go :
Catatan:
x:=
tidak pernah dihitung.sumber
reflect
impor harus dihitungIdris,> hiper (hiper (hiper (hiper (999999999, 99, 99), 99,99), 99,99), 99,99)
Penjelasan:
Kami mendefinisikan fungsi f, menghitung tipe f (0) hanya tipe unit, sementara f (S (n)) menghitung tipe kesetaraan yang diterapkan pada argumen fungsi "hypered" dengan sendirinya dan ke f diterapkan ke n . Baris terakhir pada dasarnya adalah fungsi yang mengharapkan nilai tipe seperti (27 = (4 = (2 = (1 = () =))))) (untuk n = 4).
Contoh sederhana
sumber
:Type
?hyper
; bisakah kamu menjelaskan?hyper
diperkuat lebih dari yang lain, saya pikir Anda ingin semua / sebagian besar99
menjadi9
s. (3) Dengan asumsi$
karya Idris seperti karya Haskell, tanda kurung luar setelahnyaf$
adalah mubazir. (4) Bisakah Anda menyingkathyper
atau apakah itu membutuhkan tanda tangan jenis itu sendiri?Haskell, 782
Ekspresi:
Jenis tanda tangan:
sumber
sum
adalah(Num a, Foldable t) => t a -> a
Ceylon, 38843546786070481 (~ 4 · 10 16 )
Ini adalah 49 tupel bersarang, dengan tuple kosong paling dalam. Nama pendek jenis ini sebenarnya sama dengan nilai dalam kasus ini, tetapi nama yang diperluas sepenuhnya jauh lebih lama.
Kompiler Ceylon berfungsi selamanya ketika mencoba mengkompilasi ini (Kompilator masih berjalan setelah 180 menit) - Saya harus mencoba menghitung panjang jenis teoritis.
Masalahnya di sini adalah bahwa tipe satu elemen-tuple
[X]
sebenarnya diwakili dalam sistem tipe Ceylon karenaTuple<X, X, []>
(parameter pertama adalah supertipe untuk semua jenis elemen, kedua adalah tipe elemen pertama, dan ketiga tipe semua kecuali elemen pertama) , yang di sini adalah tuple kosong (empty
objek, contoh tunggal yang memuaskan antarmukaEmpty
)).Begitu
[]
jugaempty
,[[]]
adalahTuple<[], [], []>
=Tuple<empty, empty, empty>
,[[[]]]
adalahTuple<[[]], [[]], []>
=Tuple<Tuple<[], [], []>, Tuple<[], [], []>, []>
. Dan nama lengkap termasuk nama paket, jadi sebenarnya sudahceylon.language::Tuple<ceylon.language::Tuple<ceylon.language::empty, ceylon.language::empty, ceylon.language::empty>, ceylon.language::Tuple<ceylon.language::empty, ceylon.language::empty, ceylon.language::empty>, ceylon.language::empty>
hanya tiga level. Dan kami ingin pergi ke 50.As
ceylon.language::empty
sepanjang 22 karakter, dan masing-masingceylon.language::Tuple<?,?,ceylon.language::empty>
menambahkan 47 hingga dua kali hasil dari langkah sebelumnya, kita dapatkanf(1) = 22
, danf(n) = 2 · f(n-1) + 47
. Ini menyederhanakanf(n) = 69 · 2^(n - 1) - 47
, dan memasuki 50 memberi kita 38843546786070481. Tentu saja, ini jauh lebih besar daripada apa yang akan muat dalam memori komputer saya (8 · 10 9 byte).Tentu saja, kompiler dapat menjadi pintar dan tidak mencoba untuk memiliki seluruh nama tipe dalam memori sampai namanya diminta.
Ini adalah program lengkap yang mencoba mencetak jenis:
sumber
C # (Visual C # Interactive Compiler) , 99 byte, Skor 841
Cobalah online!
Keluaran
sumber