Daftar yang lebih tak terbatas dalam skema
Ini adalah kelanjutan dari cerita saya sebelumnya yang dapat ditemukan di sini.
Gabungan Aliran
Terakhir kali kami membuat beberapa streaming menarik menggunakan stream-add. Sekarang saya ingin memperkenalkan fungsi yang lebih serbaguna yang memungkinkan kita membuat beberapa aliran yang lebih menarik.
Fungsi ini hampir sama persis dengan stream-add, hanya saja kita dapat meneruskan operasi apa pun ke fungsi tersebut, bukan hanya +. stream-add dan (stream-combine +) setara.
Kekuatan Baru
Kami dapat membuat beberapa aliran baru yang menyenangkan dengan cara penggabungan baru ini. Kita menciptakan bilangan asli dengan menjumlahkan dua aliran, sehingga kita dapat membuat pangkat dua dengan mengalikan dua aliran.
Seperti halnya bilangan asli, mari kita asumsikan bahwa aliran pangkat dua, powsOf2 ada. Aliran ini adalah '(1 2 4 8 16 32 ...), ketika kita menggabungkan aliran ini, kalikan dengan '(2 2 2 2 2 2 ...) kita mendapatkan '(2 4 6 8 16 32 64 ...). Jadi seperti sebelumnya, ((stream-combine *) twos powsOf2)) adalah bagian akhir dari daftar kita dan kita hanya perlu memulai dengan 1.
Aliran lain yang sekarang mudah untuk dibangun adalah barisan kotak.
Dan faktorialnya
Sekali lagi perhatikan bahwa faktorial: '(1 2 6 24 120 720 …), dikalikan dengan faktorial: '(1 2 3 4 5 6), sama dengan cdr dari faktorial: '(2 6 24 120 720 5040 …). Karena kita sudah mempunyai cdr faktorialnya, kita hanya perlu memulainya secara eksplisit dengan faktorial pertama dan menggabungkan keduanya.
Jika ini masih agak membingungkan, saya sangat menganjurkan Anda untuk mempelajari proses mendasar di tempat kerja seperti yang saya tunjukkan di postingan sebelumnya.
Menuju bilangan prima
Salah satu contoh daftar tak hingga yang paling klasik dan elegan adalah menyusun daftar bilangan prima. Hal ini jelas tidak mungkin dilakukan karena satu-satunya alat kita adalah stream-combine, jadi mari kita perkenalkan satu fungsi terakhir.
stream-filter mengambil predikat dan aliran. Kemudian turun ke bawah daftar dan hanya menyimpan item yang memenuhi predikat, jika suatu item bernilai salah, item tersebut dilewati. Karena ini semua dievaluasi dengan malas, stream-filter bekerja sesuai permintaan: hanya mengeksekusi apa yang diperlukan untuk apa yang kita minta.
Penggunaan sederhana
Salah satu dari (banyak) cara menyusun bilangan ganjil adalah dengan memfilter semua bilangan genap dari bilangan asli.
Saringan Eratosthenes
Saringan Eratosthenes adalah algoritma kuno untuk menemukan bilangan prima. Intinya, Anda mengambil daftar bilangan asli yang dimulai dengan 2 (bilangan prima pertama). Kelipatan dua apa pun menurut definisinya bukan bilangan prima, jadi hapuslah keduanya dari daftar. Sekarang lanjutkan ke bilangan prima berikutnya dan hapus semua kelipatannya dari daftar dan seterusnya. Proses ini akan menghapus semua bilangan dengan faktor selain satu atau bilangan itu sendiri. (“bacaan lebih lanjut”) Biasanya proses ini memerlukan batas atas, namun kami telah menemukan cara untuk bermain dengan ketidakterbatasan. Sekali lagi evaluasi malas menghemat hari dengan hanya memfilter saat kita membutuhkannya.
Bilangan prima hingga Tak Terhingga
Fungsi saringan hanya mengimplementasikan algoritma yang dijelaskan di atas. Dibutuhkan elemen pertama dari aliran sebagai bilangan prima, menyaring semua faktornya, dan mengulangi proses untuk bilangan (prima) berikutnya. Meneruskan aliran bilangan asli yang dimulai dari 2 akan menghasilkan bilangan prima.
Sungguh menakjubkan bahwa kita dapat membuat struktur data tak terbatas secara efektif dalam ruang memori terbatas. Ini menunjukkan beberapa kekuatan dan keindahan evaluasi yang malas. Adapun kegunaan sebenarnya dari daftar ini, saya tidak akan membahasnya di sini, tetapi saya menemukan "utas stack overflow" ini memiliki beberapa poin menarik. Beberapa bahasa seperti Haskell memiliki daftar bawaan yang tak terbatas, jadi konsep ini jauh dari sekedar teori.
Tentang Penulis
Eric Breyer adalah sarjana ilmu komputer di Rice University. Anda dapat menemukannya di situs webnya, serta di GitHub dan LinkedIn.
