Halo, Penduduk! Banyak kesalahan pemrograman disebabkan oleh ketidakcocokan tipe data. Sistem tipe yang kuat menghindari seluruh kelas kesalahan dan memastikan integritas data di seluruh aplikasi. Dengan belajar menguasai tipe dalam praktik sehari-hari, pengembang akan membuat kode yang lebih baik dan menghemat waktu yang diperlukan untuk menemukan kesalahan data yang rumit.
Buku ini menunjukkan kepada Anda bagaimana menggunakan pengetikan untuk membuat perangkat lunak yang tidak hanya aman dan berjalan lancar, tetapi juga mudah dipelihara.
Contoh pemecahan masalah, yang ditulis dalam TypeScript, akan membantu Anda mengembangkan keterampilan Anda dalam bekerja dengan tipe, dari tipe data sederhana hingga konsep yang lebih kompleks seperti functor dan monad.
Di buku ini:
- Pembuatan struktur data berdasarkan tipe, array, dan referensi sederhana.
- Pemrograman dan tipe berorientasi objek.
- Menggunakan obat generik dan tipe orde tinggi.
Buku ini membutuhkan pengalaman dengan salah satu bahasa pemrograman utama seperti TypeScript, Java, JavaScript, C #, atau C ++.
Untuk siapa buku ini
Buku ini ditujukan untuk mempraktikkan programmer. Pembaca harus pandai menulis kode dalam salah satu bahasa pemrograman seperti Java, C #, C ++, atau JavaScript / TypeScript. Contoh kode ada di TypeScript, tetapi sebagian besar materi dapat diterapkan ke bahasa pemrograman apa pun. Faktanya, contoh tidak selalu menggunakan TypeScript biasa. Jika memungkinkan, mereka telah beradaptasi sehingga pemrogram dalam bahasa pemrograman lain dapat memahaminya. Kumpulan contoh kode dijelaskan dalam Lampiran A, dan lembar contekan TypeScript dijelaskan dalam Lampiran B.
Jika Anda terlibat dalam pengembangan kode berorientasi objek untuk pekerjaan, Anda mungkin pernah mendengar tentang tipe data aljabar (ADT), ekspresi lambda, generik, functor, monad dan ingin lebih memahami apa itu. Dan bagaimana menggunakannya dalam pekerjaan Anda .
Buku ini akan menunjukkan kepada Anda bagaimana menggunakan sistem tipe dari bahasa pemrograman untuk merancang kode yang tidak terlalu rawan kesalahan, lebih modular, dan mudah dipahami. Anda akan melihat bagaimana mengubah runtime error yang dapat merusak seluruh sistem menjadi kesalahan kompilasi dan menangkapnya sebelum mendapat masalah.
Sebagian besar literatur tentang sistem tipe sangat diformalkan. Buku ini berfokus pada aplikasi praktis dari sistem tipe; oleh karena itu hanya ada sedikit matematika di dalamnya. Namun, sebaiknya Anda memiliki pemahaman tentang konsep aljabar dasar seperti fungsi dan himpunan. Ini diperlukan untuk memperjelas beberapa konsep yang kami butuhkan.
Algoritma dan Interator Umum
Dalam bab ini
- Menggunakan operasi map (), filter (), dan reduce () tidak hanya untuk array.
- Memecahkan berbagai macam masalah menggunakan sekumpulan algoritme umum.
- Memberikan dukungan tipe data umum untuk kontrak yang diinginkan.
- Implementasi berbagai algoritme menggunakan berbagai kategori iterator.
- Penerapan algoritma adaptif.
Bab ini berfokus sepenuhnya pada algoritme generik dan dapat digunakan kembali yang sesuai untuk berbagai tipe dan struktur data.
Kita melihat satu versi dari setiap operasi map (), filter (), dan reduce () di Bab 5 ketika kita membahas fungsi tingkat tinggi. Fungsi-fungsi ini bekerja dengan array, tetapi seperti yang telah kita lihat di bab sebelumnya, iterator adalah abstraksi yang bagus untuk bekerja dengan struktur data apa pun. Kami akan mulai dengan mengimplementasikan versi generik dari tiga algoritme di atas yang bekerja dengan iterator, dan oleh karena itu dapat diterapkan untuk memproses pohon biner, daftar, larik, dan struktur data yang dapat diulang lainnya.
Operasi map (), filter () dan reduce () tidak unik. Kami akan berbicara tentang algoritme umum dan pustaka algoritme lain yang tersedia di sebagian besar bahasa pemrograman modern. Kami akan melihat mengapa lebih baik untuk mengganti sebagian besar loop dengan panggilan ke algoritma perpustakaan. Kami juga akan berbicara sedikit tentang fluid API dan antarmuka algoritme yang ramah pengguna.
Selanjutnya, kita akan membahas batasan tipe parameter; algoritme dan struktur data generik dapat menentukan kapabilitas yang harus ada dalam tipe parameternya. Spesialisasi ini mengarah pada struktur data dan algoritme yang kurang universal yang tidak dapat digunakan di mana pun.
Kami akan membahas lebih detail tentang iterator dan berbicara tentang berbagai kategori mereka. Semakin terspesialisasi sebuah iterator, semakin efisien algoritme dengan partisipasinya. Namun, tidak semua struktur data mampu mendukung iterator khusus.
Terakhir, kita akan melihat sekilas algoritma adaptif. Mereka memungkinkan implementasi yang lebih serbaguna tetapi kurang efisien untuk iterator dengan fitur yang lebih sedikit dan implementasi yang lebih efisien tetapi kurang serbaguna untuk iterator dengan lebih banyak fitur.
10.1. Peningkatan operasi map (), filter () dan reduce ()
Di Bab 5, kita berbicara tentang operasi map (), filter (), dan reduce () dan melihat salah satu kemungkinan implementasi dari masing-masing. Algoritme ini adalah fungsi tingkat tinggi karena mengambil fungsi lain sebagai argumen dan menerapkannya ke urutan data.
Operasi map () menerapkan fungsi ke setiap elemen dalam urutan dan mengembalikan hasilnya. Operasi filter () menerapkan fungsi filter ke setiap elemen dan hanya mengembalikan nilai true yang dikembalikan oleh fungsi ini. Operasi reduce () mengelompokkan semua nilai dalam urutan menggunakan fungsi dan mengembalikan satu nilai sebagai hasilnya.
Implementasi Bab 5 kami menggunakan parameter generik tipe T, dan merepresentasikan urutan sebagai array elemen tipe T.
10.1.1. Operasi peta ()
Mari kita ingat bagaimana kita mengimplementasikan operasi map (). Kami memiliki dua tipe-parameter: T dan U. Fungsi ini mengambil argumen array nilai tipe T dan fungsi yang mengubah dari T ke U sebagai argumen kedua. Ini mengembalikan larik nilai U, seperti yang ditunjukkan pada Listing 10.1.
Sekarang, dengan pengetahuan kita tentang iterator dan generator, mari kita lihat di Listing 10.2 bagaimana mengimplementasikan map () sehingga bisa bekerja dengan Iterable <T> apa pun, bukan hanya array.
Meskipun implementasi asli terbatas pada array, implementasi ini dapat bekerja dengan struktur data apa pun yang menyediakan iterator. Selain itu, kodenya menjadi jauh lebih kompak.
10.1.2. Operasi filter ()
Mari lakukan hal yang sama dengan filter () (Listing 10.3). Implementasi asli kami mengharapkan array elemen tipe T dan predikat sebagai input. Izinkan saya mengingatkan Anda bahwa predikat adalah fungsi yang mengambil satu elemen dari beberapa tipe dan mengembalikan boolean. Jika suatu fungsi mengembalikan true untuk nilai yang diteruskan padanya, maka nilai tersebut dikatakan memenuhi predikat.
Seperti pada operasi map (), kita akan menggunakan Iterable <T> sebagai ganti array dan mengimplementasikan Iterable ini sebagai generator yang menghasilkan nilai yang memenuhi predikat, seperti yang ditunjukkan pada Listing 10.4.
Sekali lagi, implementasi yang lebih singkat ternyata, mampu bekerja tidak hanya dengan array. Akhirnya, kami memodifikasi fungsi reduce ().
10.1.3. Reduce () operasi
Implementasi reduce () asli kami mengharapkan array elemen tipe T, nilai awal tipe T (jika array kosong), dan operasi op (). Operasi ini adalah fungsi yang mengambil dua nilai tipe T sebagai argumen dan mengembalikan satu nilai tipe T. Operasi reduce () menerapkan operasi ke nilai awal dan elemen pertama dari array, menyimpan hasilnya, menerapkan operasi yang sama ke hasil dan elemen berikutnya dari array, dan lain-lain (Listing 10.5)
Anda dapat menulis ulang fungsi ini untuk menggunakan Iterable <T> sebagai ganti array dan bekerja dengan urutan apa pun, seperti yang ditunjukkan pada Listing 10.6. Dalam hal ini, kita tidak membutuhkan generator. Berbeda dengan dua fungsi sebelumnya, reduce () tidak mengembalikan urutan elemen, tetapi satu nilai.
Implementasi lainnya tidak berubah.
10.1.4. Filter () / kurangi () pipa
Mari kita lihat cara menggabungkan algoritme ini ke dalam pipeline yang hanya memilih angka genap dari pohon biner dan menjumlahkannya. Mari kita gunakan kelas BinaryTreeNode <T> dari Bab 9 dengan traversal pohon yang berpusat dan gabungkan dengan filter angka genap dan fungsi reduce () yang menggunakan penambahan sebagai operasi (Listing 10.7).
Contoh ini adalah bukti nyata dari keefektifan tipe generik. Alih-alih menerapkan fungsi baru untuk melintasi pohon biner dan menjumlahkan bilangan genap, kami hanya membentuk pipeline pemrosesan khusus untuk skenario yang diinginkan.
10.1.5. Latihan
- Buat pipeline untuk menangani jenis string yang dapat diulang: penggabungan semua string yang tidak kosong.
- Buat pipa untuk memproses iterable jenis nomor: memilih semua angka ganjil dan mengkuadratkannya.
10.2. Algoritme umum
Kita membahas algoritma map (), filter (), dan reduce (), dan juga menyebutkan take () di Bab 9. Banyak algoritma lain yang sering digunakan dalam pipeline. Saya akan mendaftar beberapa di antaranya. Kita tidak akan melihat implementasi - Saya hanya akan menjelaskan argumen apa (selain Iterable) yang mereka terima dan bagaimana mereka memproses data. Selain itu, saya akan mencantumkan berbagai nama yang dapat digunakan algoritme ini:
- map () mengambil sebagai input urutan nilai tipe T dan fungsi (nilai: T) => U, dan mengembalikan urutan nilai tipe U setelah menerapkan fungsi ini ke semua nilai input urutan. Ini juga muncul di bawah nama fmap (), select ();
- filter() T (value: T) => boolean, T, , true. where();
- reduce() T T (x: T, y: T) => T. reduce() T. fold(), collect(), accumulate(), aggregate();
- any() T (value: T) => boolean. true, ;
- all() T (value: T) => boolean. true, ;
- none() T (value: T) => boolean. true, ;
- take() T n. , n . limit();
- drop() T n. , , n. skip();
- zip() T U, , T U, , .
Ada banyak algoritme lain untuk menyortir, membalik, memisahkan, dan menggabungkan urutan. Untungnya, algoritme ini sangat berguna dan dapat diterapkan di banyak area sehingga Anda tidak perlu menerapkannya sendiri. Untuk sebagian besar bahasa pemrograman, ada pustaka dengan implementasi siap pakai. JavaScript memiliki paket underscore.js dan lodash, masing-masing dengan banyak algoritme serupa. (Pada saat penulisan ini, pustaka ini tidak mendukung iterator - hanya larik JavaScript bawaan dan tipe objek.) Di Java, pustaka ini dapat ditemukan dalam paket java.util.stream. Di C #, mereka berada di namespace System.Linq. Di C ++, di file header pustaka standar <algrithm>.
10.2.1. Algoritme, bukan loop
Anda mungkin terkejut, tetapi ada aturan praktis yang baik: setiap kali Anda menulis algoritme, periksa untuk melihat apakah ada algoritme atau alur pustaka untuk tugas tersebut. Loop biasanya ditulis untuk memproses urutan - persis seperti yang dilakukan algoritme yang dibahas di atas.
Algoritme pustaka lebih disukai daripada loop khusus karena kemungkinan kesalahan lebih kecil. Algoritme pustaka terbukti dan diimplementasikan secara efisien, dan dapat digunakan untuk membuat kode lebih mudah dibaca dengan menentukan operasi secara eksplisit.
Kami telah melihat beberapa implementasi dalam buku ini untuk lebih memahami internal, tetapi Anda jarang perlu menerapkan algoritme sendiri. Jika Anda menemukan tugas yang berada di luar kekuatan algoritme yang ada, lebih baik membuat implementasi umum yang dapat digunakan kembali daripada implementasi khusus satu kali.
10.2.2. Menerapkan pipa fluida
Sebagian besar library menyediakan API fluid untuk algoritme pipelining. Fluid API adalah API berantai yang membuat kode Anda lebih mudah dibaca. Mari kita lihat perbedaan antara API fluida dan API non-fluida menggunakan pipa filter / konvolusi dari Bagian 10.1.4 (Daftar 10.8) sebagai contoh.
Dan meskipun kita pertama kali menerapkan operasi filter () dan kemudian meneruskan hasilnya ke operasi reduce (), ketika kita membaca kode dari kiri ke kanan, kita akan melihat reduce () sebelum filter (). Juga cukup sulit untuk mengetahui argumen mana yang merujuk ke fungsi tertentu dalam pipeline. Fluid API membuat kode Anda lebih mudah dibaca.
Saat ini, semua algoritme kami menggunakan objek yang dapat diulang sebagai argumen pertama dan mengembalikan sebuah iterator. Pemrograman berorientasi objek akan meningkatkan API kami. Dimungkinkan untuk mengumpulkan semua algoritme kami ke dalam kelas pembungkus yang dapat diulang. Dan kemudian panggil salah satu iterable tanpa secara eksplisit menentukannya sebagai argumen pertama, karena sekarang iterable adalah anggota kelas. Kita akan melakukan ini untuk map (), filter (), dan reduce (), mengelompokkan mereka ke dalam kelas <T> FluentIterable baru yang membungkus sebuah objek Iterable, seperti yang ditunjukkan pada Listing 10.9.
Berdasarkan Iterable <T>, kita dapat membuat FluentIterable <T>, sehingga kita dapat menulis ulang filter / pipa pengurangan agar lebih lancar. Mari buat objek <T> FluentIterable, panggil filter () di atasnya, buat objek FluentIterable <T> baru berdasarkan hasilnya, dan panggil reduce () di atasnya, seperti yang ditunjukkan pada Listing 10.10.
Sekarang filter () muncul sebelum reduce (), dan cukup jelas bahwa argumen merujuk ke fungsi ini. Satu-satunya masalah adalah kebutuhan untuk membuat FluentIterable <T> baru setelah setiap panggilan fungsi. Anda bisa meningkatkan API ini dengan menulis ulang fungsi map () dan filter () untuk mengembalikan FluentIterable <T> alih-alih IterableIterator <T>. Perhatikan bahwa Anda tidak perlu mengubah metode reduce () karena reduce () mengembalikan satu nilai tipe T, bukan iterable.
Tetapi karena kita menggunakan generator, kita tidak bisa begitu saja mengubah tipe kembalian. Alasan utama generator adalah menyediakan sintaks yang nyaman untuk fungsi, tetapi mereka selalu mengembalikan IterableIterator <T>. Sebagai gantinya, kita bisa memindahkan implementasi ke dalam dua metode privat, mapImpl () dan filterImpl (), dan mengonversi dari IterableIterator <T> ke FluentIterable <T> di metode public map () dan filter (), seperti yang ditunjukkan pada Listing 10.11.
Implementasi yang ditingkatkan ini membuat lebih mudah untuk merantai algoritme karena mereka semua sekarang mengembalikan FluentIterable di mana semua algoritme dideskripsikan sebagai metode, seperti yang ditunjukkan pada Listing 10.12.
Sekarang, dalam versi yang benar-benar berubah ini, kodenya mudah dibaca dari kiri ke kanan, dan sintaks untuk menggabungkan sejumlah algoritme yang membentuk pipeline terlihat cukup alami. Pendekatan serupa digunakan di sebagian besar pustaka algoritmik, membuatnya semudah mungkin untuk merangkai beberapa algoritme.
Bergantung pada bahasa pemrograman, salah satu kelemahan Fluent API adalah mengacaukan kelas FluentIterable dengan metode untuk semua algoritme, sehingga sulit untuk diperluas. Jika itu termasuk dalam pustaka, maka kode pemanggil tidak memiliki cara untuk menambahkan algoritma baru tanpa memodifikasi kelas. C # memiliki apa yang disebut metode ekstensi yang memungkinkan Anda menambahkan metode ke kelas atau antarmuka tanpa harus mengubah kodenya. Namun, tidak semua bahasa memiliki fitur seperti itu. Namun demikian, dalam banyak kasus, lebih baik menggunakan pustaka algoritme yang ada daripada menerapkan yang baru dari awal.
10.2.3. Latihan
- Perluas kelas FluentIterable untuk menyertakan algoritme take () yang mengembalikan n elemen pertama dari iterator.
- Perluas kelas FluentIterable untuk menyertakan algoritma drop () yang melewatkan n elemen pertama dari iterator dan mengembalikan sisanya.
10.3. Membatasi tipe parameter
Kita telah melihat bagaimana struktur data generik mendefinisikan bentuk data yang tidak bergantung pada parameter tipe tertentu T. Kita juga melihat sekumpulan algoritma yang menggunakan iterator untuk memproses urutan nilai tipe T, terlepas dari jenisnya. ini. Sekarang, dalam Listing 10.13, pertimbangkan skenario di mana tipe data tertentu penting: fungsi generik renderAll () yang menggunakan Iterable <T> sebagai argumen dan memanggil render () pada setiap elemen yang dikembalikan oleh iterator.
Mencoba mengompilasi fungsi ini berakhir dengan pesan kesalahan berikut: Properti 'render' tidak ada pada tipe 'T' (tipe 'T' tidak memiliki properti 'render').
Kami mencoba memanggil metode render () dari tipe umum T, yang mungkin tidak memiliki metode seperti itu. Dalam skenario seperti itu, Anda perlu membatasi tipe T hanya untuk inkarnasi spesifik yang berisi metode render ().
Batasan jenis parameter
Batasan memberi tahu kompiler tentang kapabilitas yang harus dimiliki oleh tipe argumen. Tanpa batasan, tipe argumen bisa apa saja. Ketika tipe data generik diharuskan memiliki anggota kelas tertentu, dengan bantuan batasan kami mengurangi himpunan tipe yang diizinkan menjadi tipe yang memiliki anggota yang diperlukan ini.
Dalam kasus kami, kami dapat mendefinisikan antarmuka IRenderable, yang mendeklarasikan metode render (), seperti yang ditunjukkan pada Listing 10.14. Anda kemudian dapat menambahkan batasan pada tipe T menggunakan kata kunci extends untuk memberi tahu compiler bahwa hanya tipe argumen yang menyertakan IRenderable yang diperbolehkan.
10.3.1. Struktur Data Umum yang Dibatasi
Kebanyakan struktur data generik tidak memerlukan batasan tipe parameter. Jenis nilai apa pun dapat disimpan dalam daftar tertaut, pohon, dan larik. Namun, ada beberapa pengecualian, khususnya kumpulan hash.
Struktur data himpunan memodelkan himpunan dalam pengertian matematis, sehingga nilai unik disimpan di dalamnya dan duplikatnya dibuang. Struktur data kumpulan biasanya menyertakan metode untuk menggabungkan, memotong, dan mengurangi dari kumpulan lain, dan juga memungkinkan Anda untuk memeriksa apakah nilai yang diberikan disertakan dalam kumpulan. Untuk melakukan pemeriksaan ini, Anda dapat membandingkan nilai ini dengan masing-masing elemen himpunan, meskipun ini bukan pendekatan yang sangat efisien. Dalam kasus terburuk, perbandingan dengan setiap elemen dari himpunan membutuhkan traverse dari seluruh himpunan. Traversal seperti itu dilakukan dalam waktu linier, O (n). Anda dapat memoles notasi ini di sidebar "Notasi O Besar", di bawah.
Implementasi yang paling efisien adalah melakukan hash semua nilai dan menyimpannya dalam struktur data nilai kunci seperti peta hash atau kamus. Struktur seperti ini lebih efisien, mereka dapat mengambil nilai dalam waktu yang konstan , O (1). Himpunan hash membungkus peta hash, memberikan pemeriksaan yang efisien untuk penyertaan elemen. Tapi itu memiliki batasan: tipe T harus menyediakan fungsi hash yang mengambil nilai tipe T dan mengembalikan nilai hash dari tipe number.
Dalam beberapa bahasa pemrograman, hashing untuk semua nilai dimungkinkan dengan mendeskripsikan metode hashing dalam tipe yang lebih tinggi. Misalnya, tipe Objek Java yang lebih tinggi menyertakan metode hashCode (), dan tipe Objek C # yang lebih tinggi menyertakan metode GetHashCode (). Tetapi jika bahasa tidak menyediakan kemungkinan seperti itu, maka batasan tipe diperlukan sehingga hanya tipe yang dapat di-hash yang dapat disimpan dalam struktur data kami. Misalnya, kita dapat mendefinisikan antarmuka IHashable dan menggunakannya sebagai batasan tipe pada tipe kunci dari hashmap atau kamus generik kita.
tentang Penulis
Vlad Rishkutsia adalah spesialis pengembangan perangkat lunak di Microsoft dengan pengalaman lebih dari sepuluh tahun. Selama waktu ini, dia mengelola beberapa proyek perangkat lunak besar dan melatih banyak profesional muda.
Rincian lebih lanjut tentang buku dapat ditemukan di situs web penerbit
» Daftar Isi
» Kutipan
Untuk Habitants diskon 25% untuk kupon - TypeScript
Setelah pembayaran untuk versi kertas buku, e-book dikirim melalui e- surat.