Bagaimana Anda tahu kapan harus menggunakan lipat-kiri dan kapan harus menggunakan lipat-kanan?

99

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?

Jeff
sumber
1
terlihat mirip dengan stackoverflow.com/questions/384797/…
Steven Huwig
1
Pertanyaan ini lebih umum dari itu, khususnya tentang Haskell. Kemalasan membuat perbedaan besar dalam menjawab pertanyaan itu.
Chris Conway
Oh. Aneh, entah bagaimana saya pikir saya melihat tag Haskell pada pertanyaan ini, tapi saya rasa tidak ...
ephemient

Jawaban:

105

Anda dapat mentransfer lipatan menjadi notasi operator infix (tulisan di antaranya):

Contoh lipat ini menggunakan fungsi akumulator x

fold x [A, B, C, D]

dengan demikian sama

A x B x C x D

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

((A x B) x C) x D

Di sini, Anda menggunakan lipatan kiri . Contoh (pseudocode gaya haskell)

foldl (-) [1, 2, 3] == (1 - 2) - 3 == 1 - 2 - 3 // - is left-associative

Jika operator Anda adalah asosiatif kanan ( lipatan kanan ), tanda kurung akan disetel seperti ini:

A x (B x (C x D))

Contoh: Kontra Operator

foldr (:) [] [1, 2, 3] == 1 : (2 : (3 : [])) == 1 : 2 : 3 : [] == [1, 2, 3]

Secara umum, operator aritmatika (kebanyakan operator) bersifat asosiatif kiri, jadi foldllebih tersebar luas. Tetapi dalam kasus lain, notasi infiks + tanda kurung cukup berguna.

Dario
sumber
6
Nah, apa yang Anda jelaskan sebenarnya foldl1dan foldr1di Haskell ( foldldan foldrmengambil nilai awal eksternal), dan "kontra" Haskell disebut (:)tidak (::), tetapi sebaliknya ini benar. Anda mungkin ingin menambahkan bahwa Haskell juga menyediakan foldl'/ foldl1'yang merupakan varian ketat dari foldl/ foldl1, karena lazy arithmetic tidak selalu diinginkan.
singkat
Maaf, saya pikir saya melihat tag "Haskell" pada pertanyaan ini, tapi tidak ada. Komentar saya tidak terlalu masuk akal jika bukan Haskell ...
ephemient
@ephemient Anda melihatnya. Ini adalah "pseudocode gaya haskell". :)
laughing_man
Jawaban terbaik yang pernah saya lihat terkait dengan perbedaan antara lipatan.
AleXoundOS
60

Olin Shivers membedakan mereka dengan mengatakan "foldl adalah iterator daftar fundamental" dan "foldr adalah operator rekursi daftar fundamental." Jika Anda melihat cara kerja foldl:

((1 + 2) + 3) + 4

Anda dapat melihat akumulator (seperti pada iterasi rekursif-ekor) yang sedang dibangun. Sebaliknya, hasil lipatan:

1 + (2 + (3 + 4))

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.

Steven Huwig
sumber
29

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 , foldRightkebutuhan untuk mempertahankan n-1bingkai tumpukan, di mana npanjang 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:

1 + List(2,3).foldRight(0)(_ + _)        // first stack frame
    2 + List(3).foldRight(0)(_ + _)      // second stack frame
        3 + 0                            // third stack frame 
// (I don't remember if the JVM allocates space 
// on the stack for the third frame as well)

sementara List(1,2,3).foldLeft(0)(_ + _)akan dikurangi menjadi:

(((0 + 1) + 2) + 3)

yang dapat dihitung secara iteratif, seperti yang dilakukan dalam implementasiList .

Dalam bahasa yang dievaluasi secara ketat sebagai Scala, a foldRightdapat dengan mudah meledakkan tumpukan untuk daftar besar, sementara a foldLefttidak mau.

Contoh:

scala> List.range(1, 10000).foldLeft(0)(_ + _)
res1: Int = 49995000

scala> List.range(1, 10000).foldRight(0)(_ + _)
java.lang.StackOverflowError
        at scala.List.foldRight(List.scala:1081)
        at scala.List.foldRight(List.scala:1081)
        at scala.List.foldRight(List.scala:1081)
        at scala.List.foldRight(List.scala:1081)
        at scala.List.foldRight(List.scala:1081)
        at scala.List.foldRight(List.scala:1081)
        at scala.List.foldRight(List.scala:1081)
        at scala.List.foldRight(List.scala:1081)
        at scala.List.foldRig...

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;).

Flaviu Cipcigan
sumber
13
Ini benar sebelumnya, tetapi dalam versi Scala saat ini, foldRight telah diubah untuk menerapkan foldLeft pada salinan daftar yang dibalik. Misalnya, di 2.10.3, github.com/scala/scala/blob/v2.10.3/src/library/scala/… . Sepertinya perubahan ini dilakukan pada awal 2013 - github.com/scala/scala/commit/… .
Dhruv Kapoor
4

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 depan

foldr: (1 + (2 + (3 + 4)))membutuhkan bingkai tumpukan untuk dibuka 1 + ?dan 2 + ?sebelum menghitung 3 + 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
1
Bingkai tumpukan ekstra pasti akan membuat perbedaan untuk daftar besar. Jika tumpukan frame Anda melebihi ukuran cache prosesor, maka cache-miss Anda akan memengaruhi kinerja. Kecuali jika daftar tersebut ditautkan ganda, agak sulit untuk membuat foldr menjadi fungsi rekursif ekor, jadi Anda harus menggunakan foldl kecuali ada alasan untuk tidak melakukannya.
A. Levy
4
Sifat malas Haskell mengacaukan analisis ini. Jika fungsi yang dilipat tidak ketat pada parameter kedua, maka foldrbisa menjadi lebih efisien daripada foldl, dan tidak akan memerlukan bingkai tumpukan tambahan.
singkat
2
Maaf, saya pikir saya melihat tag "Haskell" pada pertanyaan ini, tapi tidak ada. Komentar saya tidak terlalu masuk akal jika bukan Haskell ...
ephemient