Membaca makalah klasik ini , saya terjebak pada paramorphisms. Sayangnya bagiannya cukup tipis, dan halaman Wikipedia tidak mengatakan apa-apa.
Terjemahan Haskell saya adalah:
para :: (a -> [a] -> b -> b) -> b -> [a] -> b
para f base = h
where
h [] = base
h (x:xs) = f x xs (h xs)
Tapi saya tidak mengerti itu - saya tidak memiliki intuisi untuk tanda tangan tipe atau hasil yang diinginkan.
Apa itu paramorfisme, dan apa sajakah contoh berguna dalam tindakan?
Ya, saya pernah melihat pertanyaan - pertanyaan ini , tetapi tidak mencakup paramorfisme secara langsung dan hanya menunjuk pada sumber daya yang mungkin berguna sebagai referensi, tetapi tidak sebagai bahan pembelajaran.
haskell
recursion
functional-programming
higher-order-functions
Matt Fenwick
sumber
sumber
para f base xs = foldr (uncurry f) base $ zip xs (tail $tails xs)
, methinks.para f base xs = foldr g base (init $ tails xs) where g (x:xs) = f x xs
. Ini mengingatkan pada Common Lisp'smaplist
.Jawaban:
Ya itu
para
. Bandingkan dengan katamorfisme, ataufoldr
:Beberapa orang menyebut paramorfisme "rekursi primitif" berbeda dengan katamorfisme (
foldr
) menjadi "iterasi".Di mana
foldr
dua parameter diberi nilai yang dihitung secara rekursif untuk setiap subobjek rekursif dari data masukan (di sini, itu adalah ekor dari daftar),para
parameter mendapatkan subobjek asli dan nilai yang dihitung secara rekursif darinya.Contoh fungsi yang diekspresikan dengan baik
para
adalah kumpulan daftar yang mencukupi.yang seperti itu
Mungkin masih lebih sederhana
di mana cabang "kontra" mengabaikan argumen yang dihitung secara rekursif dan hanya mengembalikan ekornya. Dievaluasi dengan malas, komputasi rekursif tidak pernah terjadi dan tail diekstraksi dalam waktu yang konstan.
Anda dapat mendefinisikan
foldr
denganpara
cukup mudah; itu sedikit rumit untuk menentukanpara
darifoldr
, tapi itu pasti mungkin, dan semua orang harus tahu bagaimana hal itu dilakukan!Trik untuk menentukan
para
denganfoldr
adalah merekonstruksi salinan data asli, sehingga kami mendapatkan akses ke salinan ekor di setiap langkah, meskipun kami tidak memiliki akses ke aslinya. Pada akhirnya,snd
buang salinan input dan berikan nilai output saja. Ini tidak terlalu efisien, tetapi jika Anda tertarik pada ekspresifitas semata,para
memberi Anda tidak lebih darifoldr
. Jika Anda menggunakanfoldr
versi yang disandikan inipara
, makasafeTail
akan membutuhkan waktu linier, menyalin elemen ekor demi elemen.Jadi, begitulah:
para
adalah versi yang lebih nyamanfoldr
yang memberi Anda akses langsung ke ekor daftar serta nilai yang dihitung darinya.Dalam kasus umum, bekerja dengan tipe data yang dihasilkan sebagai titik tetap rekursif dari sebuah functor
kamu punya
dan sekali lagi, keduanya dapat didefinisikan satu sama lain, dengan
para
didefinisikan daricata
trik "buat salinan" yang samaSekali lagi,
para
tidak lebih ekspresif daripadacata
, tetapi lebih nyaman jika Anda membutuhkan akses mudah ke substruktur input.Edit: Saya ingat contoh bagus lainnya.
Pertimbangkan pohon pencarian biner yang diberikan oleh
Fix TreeF
tempatdan coba definisikan penyisipan untuk pohon penelusuran biner, pertama sebagai a
cata
, lalu sebagai apara
. Anda akan menemukanpara
versinya jauh lebih mudah, karena pada setiap node Anda perlu memasukkan satu subpohon tetapi mempertahankan yang lain sebagaimana adanya.sumber