Saya sadar bahwa lipatan-kiri menghasilkan pohon-pohon miring ke kiri dan lipatan-kanan menghasilkan pohon-pohon miring ke kanan, tetapi ketika saya meraih lipatan, terkadang saya terjebak dalam pikiran yang memicu sakit kepala mencoba menentukan jenis lipatan yang mana sesuai. Saya biasanya akhirnya melepas seluruh masalah dan melangkah melalui implementasi fungsi lipatan yang berlaku untuk masalah saya.
Jadi yang ingin saya ketahui adalah:
- Apa sajakah aturan praktis untuk menentukan apakah akan melipat ke kiri atau ke kanan?
- Bagaimana saya bisa dengan cepat memutuskan jenis lipatan yang akan digunakan mengingat masalah yang saya hadapi?
Ada contoh di Scala by Example (PDF) yang menggunakan lipatan untuk menulis fungsi yang disebut flatten yang menggabungkan daftar daftar elemen ke dalam satu daftar. Dalam hal ini, lipatan kanan adalah pilihan yang tepat (mengingat cara daftar tersebut digabungkan), tetapi saya harus memikirkannya sedikit untuk sampai pada kesimpulan itu.
Karena melipat adalah tindakan umum dalam pemrograman (fungsional), saya ingin dapat membuat keputusan semacam ini dengan cepat dan percaya diri. Jadi ... ada tips?
Jawaban:
Anda dapat mentransfer lipatan menjadi notasi operator infix (tulisan di antaranya):
Contoh lipat ini menggunakan fungsi akumulator
x
dengan demikian sama
Sekarang Anda hanya perlu memikirkan tentang asosiasi operator Anda (dengan memberi tanda kurung!).
Jika Anda memiliki operator asosiatif kiri , Anda akan menyetel tanda kurung seperti ini
Di sini, Anda menggunakan lipatan kiri . Contoh (pseudocode gaya haskell)
Jika operator Anda adalah asosiatif kanan ( lipatan kanan ), tanda kurung akan disetel seperti ini:
Contoh: Kontra Operator
Secara umum, operator aritmatika (kebanyakan operator) bersifat asosiatif kiri, jadi
foldl
lebih tersebar luas. Tetapi dalam kasus lain, notasi infiks + tanda kurung cukup berguna.sumber
foldl1
danfoldr1
di Haskell (foldl
danfoldr
mengambil nilai awal eksternal), dan "kontra" Haskell disebut(:)
tidak(::)
, tetapi sebaliknya ini benar. Anda mungkin ingin menambahkan bahwa Haskell juga menyediakanfoldl'
/foldl1'
yang merupakan varian ketat darifoldl
/foldl1
, karena lazy arithmetic tidak selalu diinginkan.Olin Shivers membedakan mereka dengan mengatakan "foldl adalah iterator daftar fundamental" dan "foldr adalah operator rekursi daftar fundamental." Jika Anda melihat cara kerja foldl:
Anda dapat melihat akumulator (seperti pada iterasi rekursif-ekor) yang sedang dibangun. Sebaliknya, hasil lipatan:
di mana Anda dapat melihat traversal ke kasus dasar 4 dan membangun hasil dari sana.
Jadi saya menempatkan aturan praktis: jika itu terlihat seperti iterasi daftar, yang akan mudah ditulis dalam bentuk rekursif-ekor, foldl adalah cara yang tepat.
Tapi sebenarnya ini mungkin paling terbukti dari asosiasi operator yang Anda gunakan. Jika mereka adalah kiri-asosiatif, gunakan foldl. Jika mereka benar-asosiatif, gunakan foldr.
sumber
Poster lain telah memberikan jawaban yang bagus dan saya tidak akan mengulangi apa yang telah mereka katakan. Karena Anda telah memberikan contoh Scala dalam pertanyaan Anda, saya akan memberikan contoh spesifik Scala. Seperti yang telah dikatakan oleh Trik ,
foldRight
kebutuhan untuk mempertahankann-1
bingkai tumpukan, di manan
panjang daftar Anda dan ini dapat dengan mudah menyebabkan luapan tumpukan - dan bahkan rekursi ekor tidak dapat menyelamatkan Anda dari ini.A
List(1,2,3).foldRight(0)(_ + _)
akan dikurangi menjadi:sementara
List(1,2,3).foldLeft(0)(_ + _)
akan dikurangi menjadi:yang dapat dihitung secara iteratif, seperti yang dilakukan dalam implementasi
List
.Dalam bahasa yang dievaluasi secara ketat sebagai Scala, a
foldRight
dapat dengan mudah meledakkan tumpukan untuk daftar besar, sementara afoldLeft
tidak mau.Contoh:
Oleh karena itu, aturan praktis saya adalah - untuk operator yang tidak memiliki asosiasi tertentu, selalu gunakan
foldLeft
, setidaknya di Scala. Jika tidak, ikuti saran lain yang diberikan dalam jawaban;).sumber
Ini juga perlu diperhatikan (dan saya menyadari ini menyatakan sedikit yang jelas), dalam kasus operator komutatif, keduanya hampir sama. Dalam situasi ini, lipatan mungkin menjadi pilihan yang lebih baik:
foldl:
(((1 + 2) + 3) + 4)
dapat menghitung setiap operasi dan meneruskan nilai yang terakumulasi ke depanfoldr:
(1 + (2 + (3 + 4)))
membutuhkan bingkai tumpukan untuk dibuka1 + ?
dan2 + ?
sebelum menghitung3 + 4
, kemudian perlu kembali dan melakukan penghitungan untuk masing-masing.Saya tidak cukup ahli dalam bahasa fungsional atau pengoptimalan kompiler untuk mengatakan apakah ini benar-benar akan membuat perbedaan, tetapi tampaknya lebih bersih untuk menggunakan foldl dengan operator komutatif.
sumber
foldr
bisa menjadi lebih efisien daripadafoldl
, dan tidak akan memerlukan bingkai tumpukan tambahan.