Adakah yang bisa menjelaskan fungsi traverse di Haskell?

99

Saya mencoba dan gagal mendapatkan traversefungsi 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.

Konan
sumber
1
Artikel The Essence of the Iterator Pattern mungkin bisa membantu karena artikel itu membangun gagasan melintasi langkah demi langkah. Beberapa konsep lanjutan hadir meskipun
Jackie

Jawaban:

121

traversesama dengan fmap, kecuali bahwa ini juga memungkinkan Anda menjalankan efek saat Anda membangun kembali struktur data.

Lihat contoh dari Data.Traversabledokumentasi.

 data Tree a = Empty | Leaf a | Node (Tree a) a (Tree a)

The Functorcontoh Treeakan menjadi:

instance Functor Tree where
  fmap f Empty        = Empty
  fmap f (Leaf x)     = Leaf (f x)
  fmap f (Node l k r) = Node (fmap f l) (f k) (fmap f r)

Itu membangun kembali seluruh pohon, menerapkan fke setiap nilai.

instance Traversable Tree where
    traverse f Empty        = pure Empty
    traverse f (Leaf x)     = Leaf <$> f x
    traverse f (Node l k r) = Node <$> traverse f l <*> f k <*> traverse f r

The Traversablecontoh 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, Traversablekelas juga berisi versi monadik yang traversedisebut mapM. Untuk semua maksud dan tujuan mapMsama dengan traverse- itu ada sebagai metode terpisah karena Applicativehanya kemudian menjadi superclass dari Monad.

Jika Anda menerapkan ini dalam bahasa yang tidak murni, fmapakan sama dengan traverse, 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:

Node.prototype.traverse = function (f) {
  return new Node(this.l.traverse(f), f(this.k), this.r.traverse(f));
}

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.

Sjoerd Visscher
sumber
11
Apa arti istilah 'efek'?
missingfaktor
24
@missingfaktor: Artinya informasi struktural a Functor, bagian yang bukan parametrik. Nilai status masuk State, kegagalan dalam Maybedan Either, jumlah elemen dalam [], dan tentu saja efek samping eksternal sewenang-wenang di IO. Saya tidak mempedulikannya sebagai istilah umum (seperti Monoidfungsi yang menggunakan "empty" dan "append", konsepnya lebih umum daripada istilah tersebut pada awalnya) tetapi ini cukup umum dan berfungsi dengan cukup baik.
CA McCann
@ CA McCann: Mengerti. Terimakasih telah menjawab!
missingfaktor
1
"Saya cukup yakin Anda tidak seharusnya melakukan ini [...]." Jelas tidak - itu akan sama buruknya dengan membuat efek apbergantung pada hasil sebelumnya. Saya telah mengubah ucapan itu dengan tepat.
duplode
2
"Aplikatifnya hampir sama dengan monad, hanya saja efeknya tidak dapat bergantung pada hasil sebelumnya." ... banyak hal yang cocok untuk saya dengan baris ini, terima kasih!
agam
58

traversemengubah hal-hal di dalam a Traversablemenjadi Traversablesesuatu "di dalam" an Applicative, diberi fungsi yang membuat Applicatives dari benda-benda.

Mari gunakan Maybesebagai Applicativedan daftar sebagai Traversable. Pertama kita membutuhkan fungsi transformasi:

half x = if even x then Just (x `div` 2) else Nothing

Jadi jika angkanya genap, kita mendapatkan setengahnya (di dalam a Just), kalau tidak kita dapatkan Nothing. Jika semuanya berjalan "baik", akan terlihat seperti ini:

traverse half [2,4..10]
--Just [1,2,3,4,5]

Tapi...

traverse half [1..10]
-- Nothing

Alasannya adalah bahwa <*>fungsi tersebut digunakan untuk membangun hasil, dan jika salah satu argumennya adalah Nothing, kami Nothingkembali.

Contoh lain:

rep x = replicate x x

Fungsi ini menghasilkan daftar panjang xdengan konten x, misalnya rep 3= [3,3,3]. Apa hasil dari traverse rep [1..3]?

Kami mendapatkan hasil parsial [1], [2,2]dan [3,3,3]menggunakan rep. Sekarang semantik daftar sebagai Applicativesyang "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:

traverse rep [1..3]
--[[1,2,3],[1,2,3],[1,2,3],[1,2,3],[1,2,3],[1,2,3]]
Landei
sumber
1
Hasil akhir Anda mengingatkan saya akan hal ini .
hugomg
3
@missingno: Ya, mereka melewatkanfac n = length $ traverse rep [1..n]
Landei
1
Sebenarnya, itu ada di bawah "List-encoding-programmer" (tetapi menggunakan pemahaman daftar). Situs web itu lengkap :)
hugomg
1
@missingno: Hm, ini tidak persis sama ... keduanya mengandalkan perilaku produk Cartesian dari daftar monad, tetapi situs tersebut hanya menggunakan dua sekaligus, jadi lebih seperti melakukan liftA2 (,)daripada menggunakan formulir yang lebih umum traverse.
CA McCann
42

Saya pikir itu paling mudah dipahami dalam istilah sequenceA, seperti yang traversedapat didefinisikan sebagai berikut.

traverse :: (Traversable t, Applicative f) => (a -> f b) -> t a -> f (t b)
traverse f = sequenceA . fmap f

sequenceA mengurutkan elemen-elemen struktur dari kiri ke kanan, mengembalikan struktur dengan bentuk yang sama yang berisi hasil.

sequenceA :: (Traversable t, Applicative f) => t (f a) -> f (t a)
sequenceA = traverse id

Anda juga dapat menganggap sequenceAsebagai membalik urutan dua fungsi, misalnya beralih dari daftar tindakan menjadi tindakan yang mengembalikan daftar hasil.

Jadi traversemengambil beberapa struktur, dan berlaku funtuk 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 terkait traverse_.

traverse_ :: (Foldable t, Applicative f) => (a -> f b) -> t a -> f ()

Jadi, Anda dapat melihat bahwa perbedaan utama antara Foldableand Traversableis 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 IOsebagai aplikatif:

λ> import Data.Traversable
λ> let qs = ["name", "quest", "favorite color"]
λ> traverse (\thing -> putStrLn ("What is your " ++ thing ++ "?") *> getLine) qs
What is your name?
Sir Lancelot
What is your quest?
to seek the holy grail
What is your favorite color?
blue
["Sir Lancelot","to seek the holy grail","blue"]

Meskipun contoh ini agak tidak menarik, hal-hal menjadi lebih menarik ketika traversedigunakan pada jenis wadah lain, atau menggunakan aplikasi lain.

hammar
sumber
Jadi traverse hanyalah bentuk mapM yang lebih umum? Sebenarnya, sequenceA . fmapuntuk daftar itu setara dengan sequence . mapbukan?
Raskell
Apa yang Anda maksud dengan 'efek samping sekuensing'? Apa itu 'efek samping' dalam jawaban Anda - Saya hanya berpikir bahwa efek samping hanya mungkin terjadi pada monad. Salam.
Marek
1
@Marek "Saya hanya berpikir bahwa efek samping yang mungkin hanya dalam monads" - Koneksi jauh lebih longgar dari itu: (1) IO jenis dapat digunakan untuk mengungkapkan efek samping; (2) IOkebetulan 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" .
duplode
(Ngomong-ngomong, @hammar, saya memberanikan diri untuk mengubah "efek samping" menjadi "efek" dalam jawaban ini karena alasan yang diuraikan dalam komentar di atas.)
duplode
17

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 ingin fmapID pengguna ini ke nama pengguna, Anda tidak dapat menggunakan tradisional fmap, karena di dalam fungsi Anda perlu mengakses database untuk membaca nama pengguna (yang memerlukan efek - dalam hal ini, menggunakan IOmonad).

Tanda tangan dari traverse adalah:

traverse :: (Traversable t, Applicative f) => (a -> f b) -> t a -> f (t b)

Dengan traverse , Anda dapat melakukan efek, oleh karena itu, kode Anda untuk memetakan ID pengguna ke nama pengguna terlihat seperti:

mapUserIDsToUsernames :: (Num -> IO String) -> [Num] -> IO [String]
mapUserIDsToUsernames fn ids = traverse fn ids

Ada juga fungsi yang disebut mapM :

mapM :: (Traversable t, Monad m) => (a -> m b) -> t a -> m (t b)

Setiap penggunaan mapMbisa diganti dengantraverse , tapi tidak bisa sebaliknya. mapMhanya berfungsi untuk monad, sedangkan traverselebih umum.

Jika Anda hanya ingin mencapai efek dan tidak mengembalikan nilai berguna apa pun, ada traverse_dan mapM_versi fungsi ini, keduanya mengabaikan nilai pengembalian dari fungsi dan sedikit lebih cepat.

Kai Sellgren
sumber
Saya telah mengubah jawaban Anda untuk alasan yang sama yang membuat saya mengedit hammar's .
duplode
7

traverse adalah lingkarannya. Implementasinya bergantung pada struktur data yang akan dilalui. Itu mungkin daftar, pohon Maybe,,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 Traversabletipe, Anda mungkin bisa menulis algoritme Anda lebih independen dan serbaguna. Tapi pengalaman saya mengatakan, itu Traversablebiasanya 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.

comonad
sumber