Saya mencoba dan gagal mendapatkan traverse
fungsi dari Data.Traversable
. Saya tidak dapat memahami maksudnya. Karena saya berasal dari latar belakang imperatif, dapatkah seseorang menjelaskannya kepada saya dalam istilah loop imperatif? Pseudo-code akan sangat dihargai. Terima kasih.
99
Jawaban:
traverse
sama denganfmap
, kecuali bahwa ini juga memungkinkan Anda menjalankan efek saat Anda membangun kembali struktur data.Lihat contoh dari
Data.Traversable
dokumentasi.The
Functor
contohTree
akan menjadi:Itu membangun kembali seluruh pohon, menerapkan
f
ke setiap nilai.The
Traversable
contoh hampir sama, kecuali konstruktor disebut dalam gaya aplikatif. Ini berarti bahwa kita dapat memiliki efek (samping) saat membangun kembali pohon tersebut. Aplikatif hampir sama dengan monad, hanya saja efeknya tidak dapat bergantung pada hasil sebelumnya. Dalam contoh ini berarti Anda tidak dapat melakukan sesuatu yang berbeda ke cabang kanan dari sebuah node tergantung pada hasil dari membangun kembali cabang kiri misalnya.Untuk alasan sejarah,
Traversable
kelas juga berisi versi monadik yangtraverse
disebutmapM
. Untuk semua maksud dan tujuanmapM
sama dengantraverse
- itu ada sebagai metode terpisah karenaApplicative
hanya kemudian menjadi superclass dariMonad
.Jika Anda menerapkan ini dalam bahasa yang tidak murni,
fmap
akan sama dengantraverse
, karena tidak ada cara untuk mencegah efek samping. Anda tidak dapat mengimplementasikannya sebagai loop, karena Anda harus melintasi struktur data Anda secara rekursif. Berikut adalah contoh kecil bagaimana saya melakukannya di Javascript:Menerapkannya seperti ini membatasi Anda pada efek yang dimungkinkan oleh bahasa. Jika Anda menginginkan non-determinisme (yang merupakan contoh daftar model Aplikatif) dan bahasa Anda tidak memiliki bawaan, Anda kurang beruntung.
sumber
Functor
, bagian yang bukan parametrik. Nilai status masukState
, kegagalan dalamMaybe
danEither
, jumlah elemen dalam[]
, dan tentu saja efek samping eksternal sewenang-wenang diIO
. Saya tidak mempedulikannya sebagai istilah umum (sepertiMonoid
fungsi yang menggunakan "empty" dan "append", konsepnya lebih umum daripada istilah tersebut pada awalnya) tetapi ini cukup umum dan berfungsi dengan cukup baik.ap
bergantung pada hasil sebelumnya. Saya telah mengubah ucapan itu dengan tepat.traverse
mengubah hal-hal di dalam aTraversable
menjadiTraversable
sesuatu "di dalam" anApplicative
, diberi fungsi yang membuatApplicative
s dari benda-benda.Mari gunakan
Maybe
sebagaiApplicative
dan daftar sebagaiTraversable
. Pertama kita membutuhkan fungsi transformasi:Jadi jika angkanya genap, kita mendapatkan setengahnya (di dalam a
Just
), kalau tidak kita dapatkanNothing
. Jika semuanya berjalan "baik", akan terlihat seperti ini:Tapi...
Alasannya adalah bahwa
<*>
fungsi tersebut digunakan untuk membangun hasil, dan jika salah satu argumennya adalahNothing
, kamiNothing
kembali.Contoh lain:
Fungsi ini menghasilkan daftar panjang
x
dengan kontenx
, misalnyarep 3
=[3,3,3]
. Apa hasil daritraverse rep [1..3]
?Kami mendapatkan hasil parsial
[1]
,[2,2]
dan[3,3,3]
menggunakanrep
. Sekarang semantik daftar sebagaiApplicatives
yang "mengambil semua kombinasi", misalnya(+) <$> [10,20] <*> [3,4]
adalah[13,14,23,24]
."Semua kombinasi"
[1]
dan[2,2]
dua kali[1,2]
. Semua kombinasi dua kali[1,2]
dan[3,3,3]
enam kali[1,2,3]
. Jadi kita punya:sumber
fac n = length $ traverse rep [1..n]
liftA2 (,)
daripada menggunakan formulir yang lebih umumtraverse
.Saya pikir itu paling mudah dipahami dalam istilah
sequenceA
, seperti yangtraverse
dapat didefinisikan sebagai berikut.sequenceA
mengurutkan elemen-elemen struktur dari kiri ke kanan, mengembalikan struktur dengan bentuk yang sama yang berisi hasil.Anda juga dapat menganggap
sequenceA
sebagai membalik urutan dua fungsi, misalnya beralih dari daftar tindakan menjadi tindakan yang mengembalikan daftar hasil.Jadi
traverse
mengambil beberapa struktur, dan berlakuf
untuk mengubah setiap elemen dalam struktur menjadi beberapa aplikatif, kemudian mengurutkan efek dari aplikasi tersebut dari kiri ke kanan, mengembalikan struktur dengan bentuk yang sama berisi hasil.Anda juga dapat membandingkannya dengan
Foldable
, yang mendefinisikan fungsi terkaittraverse_
.Jadi, Anda dapat melihat bahwa perbedaan utama antara
Foldable
andTraversable
is memungkinkan Anda untuk mempertahankan bentuk struktur, sedangkan yang pertama mengharuskan Anda melipat hasilnya menjadi nilai lain.Contoh sederhana penggunaannya adalah menggunakan list sebagai struktur yang dapat dilalui, dan
IO
sebagai aplikatif:Meskipun contoh ini agak tidak menarik, hal-hal menjadi lebih menarik ketika
traverse
digunakan pada jenis wadah lain, atau menggunakan aplikasi lain.sumber
sequenceA . fmap
untuk daftar itu setara dengansequence . map
bukan?IO
jenis dapat digunakan untuk mengungkapkan efek samping; (2)IO
kebetulan adalah monad, yang ternyata sangat nyaman. Monad pada dasarnya tidak terkait dengan efek samping. Perlu juga dicatat bahwa ada arti dari "efek" yang lebih luas dari "efek samping" dalam pengertian biasanya - yang mencakup perhitungan murni. Pada poin terakhir ini, lihat juga Apa sebenarnya arti "efektif" .Ini seperti
fmap
, kecuali Anda dapat menjalankan efek di dalam fungsi mapper, yang juga mengubah jenis hasil.Bayangkan daftar bilangan bulat yang mewakili ID pengguna dalam database:
[1, 2, 3]
. Jika Anda inginfmap
ID pengguna ini ke nama pengguna, Anda tidak dapat menggunakan tradisionalfmap
, karena di dalam fungsi Anda perlu mengakses database untuk membaca nama pengguna (yang memerlukan efek - dalam hal ini, menggunakanIO
monad).Tanda tangan dari
traverse
adalah:Dengan
traverse
, Anda dapat melakukan efek, oleh karena itu, kode Anda untuk memetakan ID pengguna ke nama pengguna terlihat seperti:Ada juga fungsi yang disebut
mapM
:Setiap penggunaan
mapM
bisa diganti dengantraverse
, tapi tidak bisa sebaliknya.mapM
hanya berfungsi untuk monad, sedangkantraverse
lebih umum.Jika Anda hanya ingin mencapai efek dan tidak mengembalikan nilai berguna apa pun, ada
traverse_
danmapM_
versi fungsi ini, keduanya mengabaikan nilai pengembalian dari fungsi dan sedikit lebih cepat.sumber
traverse
adalah lingkarannya. Implementasinya bergantung pada struktur data yang akan dilalui. Itu mungkin daftar, pohonMaybe
,,Seq
(pengaruh), atau apapun yang memiliki cara generik yang dilalui melalui sesuatu seperti untuk loop atau fungsi rekursif. Sebuah array akan memiliki for-loop, list a while-loop, sebuah pohon entah sesuatu yang rekursif atau kombinasi tumpukan dengan while-loop; tetapi dalam bahasa fungsional Anda tidak memerlukan perintah perulangan yang rumit ini: Anda menggabungkan bagian dalam perulangan (dalam bentuk fungsi) dengan struktur data secara lebih langsung dan lebih sedikit.Dengan kelas
Traversable
tipe, Anda mungkin bisa menulis algoritme Anda lebih independen dan serbaguna. Tapi pengalaman saya mengatakan, ituTraversable
biasanya hanya digunakan untuk sekadar merekatkan algoritme ke struktur data yang ada. Cukup menyenangkan untuk tidak perlu menulis fungsi serupa untuk tipe data berbeda yang memenuhi syarat juga.sumber