0xDEADBEEF

[RSS]
««« »»»

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

14. 4. 2019

Par­ci­ální funkce je taková, která není de­fi­no­vána pro všechny vstupy. Ve Scale je re­pre­zen­to­vá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í: ne­do­chází při po­u­žití par­ci­ál­ních funkcí v ně­kte­rých pří­pa­dech ke dvo­ji­tému vy­hod­no­co­vání? Abych to osvět­lil, 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 par­ci­ální funkce de­fi­no­vaná jen pro stringy od­po­ví­da­jící ur­či­tému regexu. Pokud je po­u­žita jako ar­gu­ment metody collect, ta nejdřív zjistí, zdali je funkce de­fi­no­vaná pro kon­krétní ele­ment (isDefinedAt) a pokud tomu tak je, je tento apli­ko­ván. Z API je patrné, že musí nejdřív volat isDefinedAt, které musí jednou vy­hod­no­tit regex a pak volat apply, které opět vy­hod­notí ten samý regex. A regexy nejsou úplně za­darmo.

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

Na­štěstí tomu tak není. Kom­pi­lá­tor pro každou par­ci­ální funkci vy­ge­ne­ruje metodu applyOrElse kom­bi­nu­jící isDefinedAtapply. Pro PartialFunction o pár od­stavců výše jde o při­bližně toho (při­bližně, pro­tože jsem to musel vy­kou­kat z by­te­kó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]] = r.unapplySeq(str)

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

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

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

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

Sa­motná metoda applyOrElse ale ne­stačí k efek­tivní im­ple­men­taci collect, pro­tože akce default se pro­vede jen pro prvky, které se ne­na­chází v doméně funkce. Ale my po­tře­bu­jeme opak – od­li­šit ty, které se v ní na­chá­zejí, tedy všechny pro které isDefinedAt vrátí true. Proto PartialFunction de­fi­nuje 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řes­nou im­ple­men­taci runWith, ale za­chy­cuje jejího ducha. MARKER je uni­kátní objekt, který in­di­kuje, že par­ci­ální funkce není pro daný vstup de­fi­no­vána.

Metoda collect in­terně po­u­žívá právě runWith:

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

A to zna­mená, že při po­u­žití par­ci­ál­ních funkcí ne­do­chází ke dvo­ji­tému vy­hod­no­co­vání a collect může být z důvodu sní­že­ných alo­kací do­čas­ných ko­lekcí efek­tiv­nější než od­po­ví­da­jící kom­bi­nace filtermap.


+1: Toto cho­vání je zdo­ku­men­to­váno ve zdro­já­cích Scaly.

píše k47 (@kaja47, k47)