Parciální funkce ve Scale a dvojité vyhodnocování

14. 4. 2019 #Scala #regex

Parciální funkce je taková, která není definována pro všechny vstupy. Ve Scale je reprezentována typem PartialFunction.

trait PartialFunction[-A, +B] extends (A => B) {
  def apply(x: A): B
  def isDefinedAt(x: A): Boolean
}

Dlouho jsem dumal nad jednou věcí: nedochází při použití parciálních funkcí v některých případech ke dvojitému vyhodnocování? Abych to osvětlil, uvedu příklad:

val regex = """(\d+)-(\d+)-(\d+)""".r

val f: PartialFunction[String, Int] = {
  case regex(y, m, d) => y.toInt*10000 + m.toInt*100 + d.toInt
}

val strings: Seq[String] = ???

strings.collect(f)  // chová se stejně strings.filter(f.isDefinedAt).map(f)

f je parciální funkce definovaná jen pro stringy odpovídající určitému regexu. Pokud je použita jako argument metody collect, ta nejdřív zjistí, zdali je funkce definovaná pro konkrétní element (isDefinedAt) a pokud tomu tak je, je tento aplikován. Z API je patrné, že musí nejdřív volat isDefinedAt, které musí jednou vyhodnotit regex a pak volat apply, které opět vyhodnotí ten samý regex. A regexy nejsou úplně zadarmo.

Tohle byla otázka, která mi ležela v hlavě.

Naštěstí tomu tak není. Kompilátor pro každou parciální funkci vygeneruje metodu applyOrElse kombinující isDefinedAt a apply. Pro PartialFunction o pár odstavců výše jde o přibližně toho (přibližně, protože jsem to musel vykoukat z bytekódu):

def applyOrElse(str: String, default: String => Int): Int = {
  // tady se provede regex, pokud je úspěšný unapplySeq vrátí Some
  val opt: Option[Seq[String]] = regex.unapplySeq(str)

  if (opt.isEmpty || opt.get == null) {
    return default(str)
  }

  val seq = opt.get.asInstanceOf[scala.collection.LinearSeqOptimized]

  if (seq.lengthCompare(3) != 0) {
    return default(str)
  }

  // tělo parciální funkce
  seq(0).toInt*10000 + seq(1).toInt*100 + seq(2).toInt
}

Samotná metoda applyOrElse ale nestačí k efektivní implementaci collect, protože akce default se provede jen pro prvky, které se nenachází v doméně funkce. Ale my potřebujeme opak – odlišit ty, které se v ní nacházejí, tedy všechny pro které isDefinedAt vrátí true. Proto PartialFunction definuje ještě metodu runWith, která na applyOrElse staví.

def runWith[U](action: B => U): A => Boolean = { x =>
  val z = applyOrElse(x, _ => MARKER)
  if (z ne MARKER) { action(z); true } else false
}

Nejde o přesnou implementaci runWith, ale zachycuje jejího ducha. MARKER je unikátní objekt, který indikuje, že parciální funkce není pro daný vstup definována.

Metoda collect interně používá právě runWith:

def collect[B](f: PartialFunction[A, B]): Seq[B] = {
  val b = newBuilder
  foreach(f.runWith(b += _))
  b.result
}

A to znamená, že při použití parciálních funkcí nedochází ke dvojitému vyhodnocování a collect může být z důvodu snížených alokací dočasných kolekcí efektivnější než odpovídající kombinace filter a map.

+1: Toto chování je zdokumentováno ve zdrojácích Scaly.

0xDEADBEEF

Parciální funkce ve Scale a dvojité vyhodnocování