perbedaan antara foldLeft dan mengurangiLeft di Scala

196

Saya telah belajar perbedaan mendasar antara foldLeftdanreduceLeft

foldLeft:

  • nilai awal harus diteruskan

kurangiLeft:

  • mengambil elemen pertama dari koleksi sebagai nilai awal
  • melempar pengecualian jika koleksi kosong

Apakah ada perbedaan lain?

Adakah alasan khusus untuk memiliki dua metode dengan fungsi serupa?

Rajesh Pitty
sumber
Rekomendasikan Anda melihat stackoverflow.com/questions/25158780/…
samthebest
Akan lebih bagus jika Anda mengedit pertanyaan menjadi "perbedaan antara lipat dan kurangi di Scala".
pedram bashiri

Jawaban:

302

Beberapa hal untuk disebutkan di sini, sebelum memberikan jawaban yang sebenarnya:

  • Pertanyaan Anda tidak ada sangkut-pautnya dengan pertanyaan left, melainkan tentang perbedaan antara mengurangi dan melipat
  • Perbedaannya bukan implementasi sama sekali, lihat saja tanda tangannya.
  • Pertanyaannya tidak ada hubungannya dengan Scala pada khususnya, ini lebih tentang dua konsep pemrograman fungsional.

Kembali ke pertanyaan Anda:

Inilah tanda tangan foldLeft(bisa juga foldRightuntuk poin yang akan saya buat):

def foldLeft [B] (z: B)(f: (B, A) => B): B

Dan di sini adalah tanda tangan reduceLeft(lagi arah tidak masalah di sini)

def reduceLeft [B >: A] (f: (B, A) => B): B

Keduanya terlihat sangat mirip dan menyebabkan kebingungan. reduceLeftadalah kasus khusus dari foldLeft(yang omong-omong berarti bahwa Anda kadang - kadang dapat mengekspresikan hal yang sama dengan menggunakan salah satu dari mereka).

Ketika Anda memanggil reduceLeftsay pada a List[Int]itu akan benar-benar mengurangi seluruh daftar bilangan bulat menjadi nilai tunggal, yang akan bertipe Int(atau supertype Int, karenanya [B >: A]).

Ketika Anda menelepon foldLeftmengatakan pada List[Int]itu akan melipat seluruh daftar (bayangkan menggulung selembar kertas) menjadi nilai tunggal, tetapi nilai ini tidak harus bahkan terkait dengan Int(karenanya [B]).

Berikut ini sebuah contoh:

def listWithSum(numbers: List[Int]) = numbers.foldLeft((List.empty[Int], 0)) {
   (resultingTuple, currentInteger) =>
      (currentInteger :: resultingTuple._1, currentInteger + resultingTuple._2)
}

Metode ini mengambil List[Int]dan mengembalikan a Tuple2[List[Int], Int]atau (List[Int], Int). Ini menghitung jumlah dan mengembalikan tupel dengan daftar bilangan bulat dan jumlahnya. Ngomong-ngomong, daftar dikembalikan ke belakang, karena kami menggunakan foldLeftalih-alih foldRight.

Tonton One Fold untuk mengatur semuanya untuk penjelasan yang lebih mendalam.

agilesteel
sumber
Bisakah Anda menjelaskan mengapa Bitu supertype A? Sepertinya Bseharusnya menjadi subtipe A, bukan supertipe. Misalnya, dengan asumsi Banana <: Fruit <: Food, jika kita memiliki daftar Fruits, tampaknya itu mungkin mengandung beberapa Bananas, tetapi jika berisi Foods, maka jenisnya akan Food, benar? Jadi dalam hal ini, jika Badalah supertype Adan ada daftar yang berisi keduanya Bdan A, daftar harus bertipe B, bukan A. Bisakah Anda menjelaskan perbedaan ini?
socom1880
Saya tidak yakin apakah saya memahami pertanyaan Anda dengan benar. Apa jawaban 5 tahun saya mengatakan tentang fungsi pengurangan adalah bahwa List[Banana]dapat direduksi menjadi satu Bananaatau satu Fruitatau satu Food. Karena Fruit :> Bananadan `Makanan:> Pisang '.
agilesteel
Ya ... itu benar-benar masuk akal terima kasih. Saya awalnya menafsirkannya sebagai "daftar tipe Bananamungkin berisi Fruit", yang tidak masuk akal. Penjelasan Anda memang masuk akal - ffungsi yang diteruskan reduce()dapat menghasilkan a Fruitatau a Food, yang berarti Bdalam tanda tangan harus berupa superclass, bukan subclass.
socom1880
193

reduceLefthanyalah metode kenyamanan. Ini setara dengan

list.tail.foldLeft(list.head)(_)
Kim Stebel
sumber
11
Baik, jawaban singkat :) Mungkin ingin mengoreksi ejaan reducelftmeskipun
Hanxue
10
Jawaban yang bagus. Ini juga menyoroti mengapa foldberfungsi pada daftar kosong sementara reducetidak.
Mansoor Siddiqui
44

foldLeftlebih umum, Anda dapat menggunakannya untuk menghasilkan sesuatu yang sama sekali berbeda dari apa yang awalnya Anda masukkan. Sedangkan reduceLefthanya dapat menghasilkan hasil akhir dari tipe yang sama atau tipe super dari tipe koleksi. Sebagai contoh:

List(1,3,5).foldLeft(0) { _ + _ }
List(1,3,5).foldLeft(List[String]()) { (a, b) => b.toString :: a }

The foldLeftakan menerapkan penutupan dengan hasil dilipat terakhir (pertama kali menggunakan nilai awal) dan nilai berikutnya.

reduceLeftdi sisi lain pertama-tama akan menggabungkan dua nilai dari daftar dan menerapkannya pada penutupan. Selanjutnya akan menggabungkan sisa nilai dengan hasil kumulatif. Lihat:

List(1,3,5).reduceLeft { (a, b) => println("a " + a + ", b " + b); a + b }

Jika daftar kosong foldLeftdapat menyajikan nilai awal sebagai hasil hukum. reduceLeftdi sisi lain tidak memiliki nilai hukum jika tidak dapat menemukan setidaknya satu nilai dalam daftar.

thoredge
sumber
5

Alasan dasar mereka berdua di perpustakaan standar Scala mungkin karena mereka berdua di perpustakaan standar Haskell (dipanggil foldldan foldl1). Jika reduceLefttidak, itu akan sering didefinisikan sebagai metode kenyamanan di berbagai proyek.

Alexey Romanov
sumber
5

Sebagai referensi, reduceLeftakan kesalahan jika diterapkan pada wadah kosong dengan kesalahan berikut.

java.lang.UnsupportedOperationException: empty.reduceLeft

Mengolah kembali kode yang akan digunakan

myList foldLeft(List[String]()) {(a,b) => a+b}

adalah salah satu opsi potensial. Lain adalah dengan menggunakan reduceLeftOptionvarian yang mengembalikan hasil Opsi dibungkus.

myList reduceLeftOption {(a,b) => a+b} match {
  case None    => // handle no result as necessary
  case Some(v) => println(v)
}
Martin Smith
sumber
2

Dari Prinsip Pemrograman Fungsional di Scala (Martin Odersky):

Fungsi reduceLeftini didefinisikan dalam hal fungsi yang lebih umum foldLeft,.

foldLeftseperti reduceLefttetapi mengambil akumulator z , sebagai parameter tambahan, yang dikembalikan ketika foldLeftdipanggil pada daftar kosong:

(List (x1, ..., xn) foldLeft z)(op) = (...(z op x1) op ...) op x

[Berbeda dengan reduceLeft, yang melempar pengecualian ketika dipanggil pada daftar kosong.]

Kursus ini (lihat kuliah 5.5) memberikan definisi abstrak dari fungsi-fungsi ini, yang menggambarkan perbedaan mereka, meskipun mereka sangat mirip dalam penggunaan pencocokan pola dan rekursi.

abstract class List[T] { ...
  def reduceLeft(op: (T,T)=>T) : T = this match{
    case Nil     => throw new Error("Nil.reduceLeft")
    case x :: xs => (xs foldLeft x)(op)
  }
  def foldLeft[U](z: U)(op: (U,T)=>U): U = this match{
    case Nil     => z
    case x :: xs => (xs foldLeft op(z, x))(op)
  }
}

Perhatikan bahwa foldLeftmengembalikan nilai tipe U, yang tidak harus tipe yang sama List[T], tetapi mengurangiLeft mengembalikan nilai dari tipe yang sama dengan daftar).

C8H10N4O2
sumber
0

Untuk benar-benar memahami apa yang Anda lakukan dengan lipatan / pengurangan, periksa ini: http://wiki.tcl.tk/17983 penjelasan yang sangat bagus. setelah Anda mendapatkan konsep flip, mengurangi akan datang bersama dengan jawaban di atas: list.tail.foldLeft (list.head) (_)

Henry H.
sumber