KAL
Menu

Idiom pengolahan list

Pembangunan list secara terbalik, biaya operator ++, dan list comprehension.

Daftar isi

Topik ini menuntaskan idiom yang membedakan kode list Erlang yang efisien dan yang hanya berfungsi: cara membangun list baru dengan akumulator terbalik, alasan operator ++ mahal pada posisi tertentu, dan list comprehension sebagai notasi ringkas pengolahan list. Semua contoh dieksekusi nyata pada OTP 29.

Membangun list dari depan#

Menambahkan satu elemen ke depan list adalah operasi murah: [X | Acc] membuat satu cons cell baru tanpa menyentuh Acc. Sebaliknya, menambahkan ke belakang tidak murah. Karena list bertaut, sambungan di akhir hanya bisa dicapai dengan menyusuri seluruh list terlebih dahulu. Konsekuensinya, idiom pembangunan list selalu bergerak dari depan: hasil sementara ditumpuk pada akumulator, lalu urutannya dipulihkan di akhir. Modul berikut menggandakan setiap elemen dengan pola tersebut:

erlang gandakan.erl 
-module(gandakan).
-export([dua/1]).

dua(L) -> dua_acc(L, []).

dua_acc([], Acc) -> lists:reverse(Acc);
dua_acc([K | S], Acc) -> dua_acc(S, [K * 2 | Acc]).

Fungsi helper menumpuk hasil di depan akumulator sambil berjalan sebagai tail call, dan klausa dasar menutup pekerjaan dengan lists:reverse/1. Hasil akhirnya tetap berurutan sama dengan masukannya:

erlang Pembangunan terbalik lalu pembalikan 
Erlang/OTP 29 [erts-17.1.1] [source] [64-bit] [smp:2:2] [ds:2:2:10] [async-threads:1] [jit:ns]

Eshell V17.1.1 (press Ctrl+G to abort, type help(). for help)
1> c(gandakan).
{ok,gandakan}
2> gandakan:dua([1, 2, 3]).
[2,4,6]

Pola tiga langkahnya baku: tumpuk di depan, jalan sebagai tail call, balikkan di klausa dasar. Pembalikan yang menyapu seluruh list sekali di akhir jauh lebih murah daripada menyambung di belakang pada setiap langkah.

Biaya operator ++#

Operator ++ menyambungkan dua list dengan menyalin sisi kirinya sampai habis, lalu mengaitkan ekornya ke sisi kanan. Sisi kanan tidak disalin sama sekali, hanya dirujuk. Akibatnya, H ++ T pada kasus dasar rekursi tubuh, yaitu pola [K | hasil(S)], tetap aman karena sisi kiri hanya satu elemen. Yang berbahaya adalah pola menambah di belakang: hasil(S) ++ [K] menyalin seluruh hasil sementara pada setiap langkah, sehingga biayanya bertumbuh kuadrat terhadap panjang list. Aturan praktisnya sederhana: ++ untuk sisi kiri yang pendek dan tetap, sementara pembangunan berulang memakai pola akumulator terbalik yang dijelaskan di atas.

Angkanya bisa dihitung untuk list dengan panjang n. Pola menambah di depan dengan [K | Acc] menyalin nol elemen per langkah, lalu lists:reverse/1 menyapu list sekali, sehingga totalnya sebanding n. Pola hasil(S) ++ [K] menyalin hasil sementara pada setiap langkah: satu elemen pada langkah pertama, dua pada langkah kedua, dan seterusnya, sehingga totalnya sebanding 1 + 2 + … + n atau n(n+1)/2. Untuk list sepuluh ribu elemen, pola kedua mengerjakan sekitar lima puluh juta penyalinan dibanding sepuluh ribu pada pola pertama, dan selisih itu tumbuh seiring data.

List comprehension#

Notasi [Ekspresi || Generator] memampatkan pola map, filter, dan gabungannya ke dalam satu ekspresi yang terbaca sebagai matematika himpunan. Generator X <- List mengambil setiap elemen, kondisi opsional menyaring, dan ekspresi di depan membentuk hasilnya. Cara membacanya dari kiri ke kanan: untuk setiap elemen dari generator, bila semua kondisi lolos, hasilkan ekspresi tersebut. Hasil akhirnya selalu list, termasuk list kosong bila tidak ada elemen yang lolos, sehingga bentuk ini aman dirangkai dengan fungsi list lain tanpa pemeriksaan tambahan:

erlang Generator, kondisi, dan penyaringan bertipe 
3> [X * 2 || X <- [1, 2, 3]].
[2,4,6]
4> [X || X <- lists:seq(1, 10), X rem 2 =:= 0].
[2,4,6,8,10]
5> [X + Y || X <- [1, 2], Y <- [10, 20]].
[11,21,12,22]
6> [N || {suhu, N} <- [{suhu, 25}, {halo, 1}, {suhu, 30}]].
[25,30]

Generator ganda pada ekspresi kelima menghasilkan semua pasangan, dengan kombinasi 11, 21, 12, dan 22 sesuai urutan generatornya. Ekspresi keenam menunjukkan kekuatan pencocokan pola pada generator: elemen {halo, 1} tidak cocok dengan pola {suhu, N} dan otomatis dilewati, sehingga penyaringan bentuk dan pengambilan isi terjadi dalam satu langkah. Di balik notasi ringkas ini, compiler membangun rekursi dengan pola pembangunan terbalik yang sama dengan yang ditulis manual sebelumnya, sehingga tidak ada penalti kinerja.

Kondisi pada comprehension juga boleh lebih dari satu dan ditulis berurutan seperti guard. Contoh berikut mengambil suhu dari data bertanda sekaligus menyaring nilainya:

erlang Kondisi penyaring pada generator 
1> [X || {suhu, X} <- [{suhu, 25}, {suhu, 19}, {suhu, 30}], X >= 25].
[25,30]

Tiga tahap pemrosesan, yaitu mengekstrak isi, membuang elemen yang tidak cocok, dan menyaring nilai, masing-masing selesai dalam satu ekspresi tanpa variabel perantara. Bentuk ini menjadi alternatif paling ringkas untuk gabungan map dan filter, sementara fungsi orde tinggi pada topik fungsi orde tinggi memberikan bentuk yang sama dengan fungsi eksplisit sebagai argumen.

Ringkasan#

  • Menambahkan elemen di depan list murah karena hanya membuat satu cons cell, sedangkan menambah di belakang menyusuri seluruh list.
  • Idiom baku pembangunan list: tumpuk hasil di akumulator dari depan, jalankan sebagai tail call, lalu lists:reverse di klausa dasar.
  • Operator ++ menyalin sisi kirinya. Pola yang menambah di belakang pada setiap langkah membuat pekerjaan bertumbuh kuadrat.
  • List comprehension menyatukan map dan filter, mendukung generator ganda, dan menyaring bentuk data lewat pola pada generatornya.

Kesalahan umum#

  • Menambah elemen ke belakang list di dalam perulangan. Pola Acc ++ [K] menyalin seluruh akumulator pada setiap langkah sehingga pekerjaan bertumbuh kuadrat, sementara [K | Acc] hanya membuat satu cons cell. Simpan pembalikan untuk akhir pekerjaan.
  • Melupakan lists:reverse/1 pada akhir pembangunan terbalik. Tanpa pembalikan, hasilnya berurutan terbalik, dan kesalahan ini sering lolos pada data yang kebetulan simetris.
  • Menganggap ++ bekerja pada nilai tunggal. Operator itu menuntut list di kedua sisinya, sehingga elemen tunggal ditulis [K] ++ L atau lebih murah L ++ [K] bila posisinya memang di belakang.

Referensi#