Batalkan lebih awal

Apa cara terbaik untuk menghentikan lipatan lebih awal? Sebagai contoh yang disederhanakan, bayangkan saya ingin menjumlahkan angka dalam sebuah Iterable, tetapi jika saya menemukan sesuatu yang tidak saya harapkan (katakanlah angka ganjil) saya mungkin ingin menghentikannya. Ini adalah perkiraan pertama

def sumEvenNumbers(nums: Iterable[Int]): Option[Int] = {
  nums.foldLeft (Some(0): Option[Int]) {
    case (Some(s), n) if n % 2 == 0 => Some(s + n)
    case _ => None
  }
}

Namun, solusi ini cukup jelek (seperti dalam, jika saya melakukan .foreach dan pengembalian - itu akan jauh lebih bersih dan lebih jelas) dan yang terburuk dari semuanya, itu melintasi seluruh iterable bahkan jika itu menemukan nomor non-genap .

Jadi, apa cara terbaik untuk menulis lipatan seperti ini, yang berakhir lebih awal? Haruskah saya pergi dan menulis ini secara rekursif, atau adakah cara yang lebih diterima?

Pilihan pertama saya biasanya menggunakan rekursi. Ini hanya agak kurang kompak, berpotensi lebih cepat (tentu tidak lebih lambat), dan di penghentian awal dapat membuat logika lebih jelas. Dalam hal ini Anda memerlukan def bersarang yang agak canggung:

def sumEvenNumbers(nums: Iterable[Int]) = {
  def sumEven(it: Iterator[Int], n: Int): Option[Int] = {
    if (it.hasNext) {
      val x = it.next
      if ((x % 2) == 0) sumEven(it, n+x) else None
    }
    else Some(n)
  }
  sumEven(nums.iterator, 0)
}

Pilihan kedua saya adalah menggunakan return, karena itu membuat semua yang lain tetap utuh dan Anda hanya perlu membungkus lipatan defsehingga Anda memiliki sesuatu untuk dikembalikan - dalam hal ini, Anda sudah memiliki metode, jadi:

def sumEvenNumbers(nums: Iterable[Int]): Option[Int] = {
  Some(nums.foldLeft(0){ (n,x) =>
    if ((n % 2) != 0) return None
    n+x
  })
}

yang dalam kasus khusus ini jauh lebih kompak daripada rekursi (meskipun kami sangat tidak beruntung dengan rekursi karena kami harus melakukan transformasi iterable / iterator). Aliran kontrol gelisah adalah sesuatu yang harus dihindari ketika semuanya sama, tetapi di sini tidak. Tidak ada salahnya menggunakannya jika itu berharga.

Jika saya sering melakukan ini dan menginginkannya di tengah-tengah metode di suatu tempat (jadi saya tidak bisa hanya menggunakan pengembalian), saya mungkin akan menggunakan penanganan pengecualian untuk menghasilkan aliran kontrol non-lokal. Bagaimanapun, itu adalah keahliannya, dan penanganan kesalahan bukan satu-satunya saat berguna. Satu-satunya trik adalah dengan menghindari pembuatan jejak tumpukan (yang sangat lambat), dan itu mudah karena sifat NoStackTracedan sifat turunannya ControlThrowablesudah melakukannya untuk Anda. Scala sudah menggunakan ini secara internal (sebenarnya, begitulah cara mengimplementasikan pengembalian dari dalam flip!). Mari buat milik kita sendiri (tidak dapat disarangkan, meskipun seseorang dapat memperbaikinya):

import scala.util.control.ControlThrowable
case class Returned[A](value: A) extends ControlThrowable {}
def shortcut[A](a: => A) = try { a } catch { case Returned(v) => v }

def sumEvenNumbers(nums: Iterable[Int]) = shortcut{
  Option(nums.foldLeft(0){ (n,x) =>
    if ((x % 2) != 0) throw Returned(None)
    n+x
  })
}

Di sini tentu saja menggunakan returnlebih baik, tetapi perhatikan bahwa Anda bisa meletakkannya di shortcutmana saja, tidak hanya membungkus seluruh metode.

Baris berikutnya bagi saya adalah menerapkan ulang lipatan (baik saya sendiri atau untuk menemukan perpustakaan yang melakukannya) sehingga dapat menandakan penghentian lebih awal. Dua cara alami untuk melakukan ini adalah dengan tidak menyebarkan nilai tetapi Optionmengandung nilai, di mana Nonemenandakan penghentian; atau untuk menggunakan fungsi indikator kedua yang menandakan penyelesaian. Lazy fold Scalaz yang ditunjukkan oleh Kim Stebel sudah mencakup kasus pertama, jadi saya akan menunjukkan yang kedua (dengan implementasi yang bisa berubah):

def foldOrFail[A,B](it: Iterable[A])(zero: B)(fail: A => Boolean)(f: (B,A) => B): Option[B] = {
  val ii = it.iterator
  var b = zero
  while (ii.hasNext) {
    val x = ii.next
    if (fail(x)) return None
    b = f(b,x)
  }
  Some(b)
}

def sumEvenNumbers(nums: Iterable[Int]) = foldOrFail(nums)(0)(_ % 2 != 0)(_ + _)

(Apakah Anda menerapkan penghentian dengan rekursi, pengembalian, kemalasan, dll. Terserah Anda.)

Saya pikir itu mencakup varian masuk akal utama; ada beberapa opsi lain juga, tetapi saya tidak yakin mengapa seseorang akan menggunakannya dalam kasus ini. ( Iteratoritu sendiri akan bekerja dengan baik jika memiliki findOrPrevious, tetapi tidak, dan kerja ekstra yang diperlukan untuk melakukannya dengan tangan menjadikannya pilihan konyol untuk digunakan di sini.)

Skenario yang Anda gambarkan (keluar dari kondisi yang tidak diinginkan) sepertinya kasus penggunaan yang baik untuk takeWhilemetode ini. Ini pada dasarnya filter, tetapi harus berakhir setelah menemukan elemen yang tidak memenuhi syarat.

Sebagai contoh:

val list = List(2,4,6,8,6,4,2,5,3,2)
list.takeWhile(_ % 2 == 0) //result is List(2,4,6,8,6,4,2)

Ini akan bekerja dengan baik untuk Iterators /Iterable s juga. Solusi yang saya sarankan untuk "jumlah bilangan genap, tetapi putus ganjil" adalah:

list.iterator.takeWhile(_ % 2 == 0).foldLeft(...)

Dan hanya untuk membuktikan bahwa itu tidak membuang-buang waktu Anda setelah mencapai angka ganjil ...

scala> val list = List(2,4,5,6,8)
list: List[Int] = List(2, 4, 5, 6, 8)

scala> def condition(i: Int) = {
     |   println("processing " + i)
     |   i % 2 == 0
     | }
condition: (i: Int)Boolean

scala> list.iterator.takeWhile(condition _).sum
processing 2
processing 4
processing 5
res4: Int = 6

Anda dapat melakukan apa yang Anda inginkan dalam gaya fungsional menggunakan versi lazy foldRight di scalaz. Untuk penjelasan lebih mendalam, lihat posting blog ini . Meskipun solusi ini menggunakan a Stream, Anda dapat mengubah an Iterablemenjadi a secara Streamefisien dengan iterable.toStream.

import scalaz._
import Scalaz._

val str = Stream(2,1,2,2,2,2,2,2,2)
var i = 0 //only here for testing
val r = str.foldr(Some(0):Option[Int])((n,s) => {
  println(i)
  i+=1
  if (n % 2 == 0) s.map(n+) else None
})

Ini hanya mencetak

0
1

yang dengan jelas menunjukkan bahwa fungsi anonim hanya dipanggil dua kali (yaitu sampai menemukan angka ganjil). Itu karena definisi foldr, yang tanda tangannya (dalam kasus Stream) adalahdef foldr[B](b: B)(f: (Int, => B) => B)(implicit r: scalaz.Foldable[Stream]): B . Perhatikan bahwa fungsi anonim mengambil parameter by name sebagai argumen keduanya, jadi tidak perlu dievaluasi.

Btw, Anda masih dapat menulis ini dengan solusi pencocokan pola OP, tetapi saya menemukan if / else dan peta lebih elegan.

Nah, Scala mengizinkan pengembalian non lokal. Ada perbedaan pendapat tentang apakah ini gaya yang baik atau tidak.

scala> def sumEvenNumbers(nums: Iterable[Int]): Option[Int] = {
     |   nums.foldLeft (Some(0): Option[Int]) {
     |     case (None, _) => return None
     |     case (Some(s), n) if n % 2 == 0 => Some(s + n)
     |     case (Some(_), _) => None
     |   }
     | }
sumEvenNumbers: (nums: Iterable[Int])Option[Int]

scala> sumEvenNumbers(2 to 10)
res8: Option[Int] = None

scala> sumEvenNumbers(2 to 10 by 2)
res9: Option[Int] = Some(30)

EDIT:

Dalam kasus khusus ini, seperti yang disarankan @Arjan, Anda juga dapat melakukan:

def sumEvenNumbers(nums: Iterable[Int]): Option[Int] = {
  nums.foldLeft (Some(0): Option[Int]) {
    case (Some(s), n) if n % 2 == 0 => Some(s + n)
    case _ => return None
  }
}

Kucing memiliki metode yang disebut foldM yang tidak hubungan arus pendek (untuk Vector, List,Stream , ...).

Ini bekerja sebagai berikut:

def sumEvenNumbers(nums: Stream[Int]): Option[Long] = {
  import cats.implicits._
  nums.foldM(0L) {
    case (acc, c) if c % 2 == 0 => Some(acc + c)
    case _ => None
  }
}

Jika menemukan elemen genap, ia mengembalikan Nonetanpa menghitung sisanya, jika tidak ia mengembalikan jumlah entri genap.

Jika Anda ingin menghitung hingga entri genap ditemukan, Anda harus menggunakan Either[Long, Long]

Anda dapat menggunakan foldMlib dari kucing (seperti yang disarankan oleh @Didac) tetapi saya menyarankan untuk menggunakan Eitherdaripada Optionjika Anda ingin mendapatkan jumlah aktual.

bifoldMapdigunakan untuk mengekstrak hasil dari Either.

import cats.implicits._

def sumEven(nums: Stream[Int]): Either[Int, Int] = {
    nums.foldM(0) {
      case (acc, n) if n % 2 == 0 => Either.right(acc + n)
      case (acc, n) => {
        println(s"Stopping on number: $n")
        Either.left(acc)
      }
    }
  }

contoh:

println("Result: " + sumEven(Stream(2, 2, 3, 11)).bifoldMap(identity, identity))
> Stopping on number: 3
> Result: 4

println("Result: " + sumEven(Stream(2, 7, 2, 3)).bifoldMap(identity, identity))
> Stopping on number: 7
> Result: 2

@Rex Kerr jawaban Anda membantu saya, tetapi saya perlu menyesuaikannya untuk menggunakan Either

  
  def foldOrFail [A, B, C, D] (map: B => Either [D, C]) (merge: (A, C) => A) (awal: A) (it: Iterable [B]): Salah satu [D, A] = {
    val ii = it.iterator
    var b = inisial
    while (ii.hasNext) {
      val x = ii. selanjutnya
      peta (x) cocok {
        case Left (error) => return Left (error)
        case Kanan (d) => b = merge (b, d)
      }
    }
    Kanan (b)
  }

Anda dapat mencoba menggunakan var sementara dan menggunakan takeWhile. Ini adalah versinya.

  var continue = true

  // sample stream of 2's and then a stream of 3's.

  val evenSum = (Stream.fill(10)(2) ++ Stream.fill(10)(3)).takeWhile(_ => continue)
    .foldLeft(Option[Int](0)){

    case (result,i) if i%2 != 0 =>
          continue = false;
          // return whatever is appropriate either the accumulated sum or None.
          result
    case (optionSum,i) => optionSum.map( _ + i)

  }

The evenSumharus Some(20)dalam kasus ini.

Anda dapat membuat pengecualian yang dipilih dengan baik saat menemukan kriteria penghentian Anda, menanganinya dalam kode panggilan.

Solusi yang lebih bagus akan menggunakan span:

val (l, r) = numbers.span(_ % 2 == 0)
if(r.isEmpty) Some(l.sum)
else None

... tapi itu melintasi daftar dua kali jika semua angka genap

Hanya untuk alasan "akademis" (:

var headers = Source.fromFile(file).getLines().next().split(",")
var closeHeaderIdx = headers.takeWhile { s => !"Close".equals(s) }.foldLeft(0)((i, S) => i+1)

Memakan waktu dua kali maka seharusnya tetapi itu adalah satu liner yang bagus. Jika "Tutup" tidak ditemukan itu akan kembali

headers.size

Yang lainnya (lebih baik) adalah yang ini:

var headers = Source.fromFile(file).getLines().next().split(",").toList
var closeHeaderIdx = headers.indexOf("Close")