Implikasi foldr vs. foldl (atau foldl ')

Pertama, Real World Haskell , yang saya baca, mengatakan untuk tidak pernah menggunakan foldldan sebaliknya menggunakannya foldl'. Jadi saya percaya itu.

Tapi aku kabur pada saat menggunakan foldrvs foldl'. Meskipun saya dapat melihat struktur bagaimana mereka bekerja secara berbeda diletakkan di depan saya, saya terlalu bodoh untuk mengerti kapan "mana yang lebih baik." Saya kira menurut saya seharusnya tidak masalah yang digunakan, karena mereka berdua menghasilkan jawaban yang sama (bukan?). Sebenarnya, pengalaman saya sebelumnya dengan konstruksi ini adalah dari versi Ruby injectdan Clojure reduce, yang sepertinya tidak memiliki versi "kiri" dan "kanan". (Pertanyaan sampingan: versi apa yang mereka gunakan?)

Wawasan apa pun yang dapat membantu orang yang memiliki kecerdasan seperti saya akan sangat dihargai!

Rekursi di foldr f x ysmana ys = [y1,y2,...,yk]terlihat seperti

f y1 (f y2 (... (f yk x) ...))

sedangkan rekursi untuk foldl f x ysterlihat seperti

f (... (f (f x y1) y2) ...) yk

Perbedaan penting di sini adalah bahwa jika hasil f x ydapat dihitung hanya dengan menggunakan nilai x, maka foldrtidak perlu memeriksa seluruh daftar. Sebagai contoh

foldr (&&) False (repeat False)

mengembalikan Falsesedangkan

foldl (&&) False (repeat False)

tidak pernah berakhir. (Catatan: repeat Falsemembuat daftar tak terbatas di mana setiap elemen berada False.)

Di sisi lain, foldl'ekornya rekursif dan ketat. Jika Anda tahu bahwa Anda harus melintasi seluruh daftar tidak peduli apa (misalnya, menjumlahkan angka-angka dalam daftar), maka foldl'lebih banyak ruang- (dan mungkin waktu-) lebih efisien daripada foldr.

foldr terlihat seperti ini:

foldl terlihat seperti ini:

Konteks: Lipat di wiki Haskell

Semantik mereka berbeda sehingga Anda tidak bisa hanya bertukar foldldan foldr. Yang satu melipat elemen dari kiri, yang lain dari kanan. Dengan begitu, operator diterapkan dalam urutan yang berbeda. Ini penting untuk semua operasi non-asosiatif, seperti pengurangan.

Haskell.org memiliki artikel yang menarik tentang masalah ini.

Singkatnya, foldrlebih baik ketika fungsi akumulator malas pada argumen keduanya. Baca lebih lanjut di Stack Overflow Haskell wiki (pun intended).

Alasannya foldl'lebih disukai foldluntuk 99% dari semua penggunaan adalah dapat digunakan dalam ruang konstan untuk sebagian besar penggunaan.

Ambil fungsinya sum = foldl['] (+) 0. Ketika foldl'digunakan, jumlahnya langsung dihitung, jadi menerapkan sumke daftar tak terbatas hanya akan berjalan selamanya, dan kemungkinan besar di ruang konstan (jika Anda menggunakan hal-hal seperti Ints, Doubles, Floats. IntegerS akan menggunakan lebih dari ruang konstan jika nomor menjadi lebih besar dari maxBound :: Int).

Dengan foldl, thunk dibangun (seperti resep bagaimana mendapatkan jawabannya, yang dapat dievaluasi nanti, daripada menyimpan jawabannya). Pemukul ini bisa menghabiskan banyak ruang, dan dalam hal ini, jauh lebih baik untuk mengevaluasi ekspresi daripada menyimpan pemogokan (mengarah ke tumpukan meluap ... dan membawa Anda ke ... oh tidak apa-apa)

Semoga itu bisa membantu.

By the way, Ruby injectdan Clojure ini reduceadalah foldl(atau foldl1, tergantung pada versi yang Anda gunakan). Biasanya, ketika hanya ada satu bentuk dalam bahasa, itu adalah lipatan kiri, termasuk Python reduce, Perl List::Util::reduce, C ++ accumulate, C # Aggregate, Smalltalk inject:into:, PHP array_reduce, Mathematica Fold, dll. Standar umum Lisp reduceuntuk lipatan kiri tetapi ada opsi untuk lipatan kanan.

Seperti yang ditunjukkan Konrad , semantik mereka berbeda. Mereka bahkan tidak memiliki tipe yang sama:

ghci> :t foldr
foldr :: (a -> b -> b) -> b -> [a] -> b
ghci> :t foldl
foldl :: (a -> b -> a) -> a -> [b] -> a
ghci> 

Sebagai contoh, daftar append operator (++) dapat diimplementasikan dengan foldras

(++) = flip (foldr (:))

sementara

(++) = flip (foldl (:))

akan memberi Anda kesalahan ketik.