How does this Scala partial function work?

Related searches
// First using normal dictionary lookup
def findElement(e: String, dict: Map[String, Any]): Option[Any] = dict.get(e)
;

// Second using Partial function
def findElement(e: String, dict: Map[String, Any]): Option[Any] = dict.find { case (k, v) => k == e } map (_._2)


They both give the same answer but, how does the second function work?

What is the BigO for the partial function which uses the case keyword? Does it iterate over all the elements of the map to find the right key?

Scala Standard Library 2.13.3, For example, a function that returns the Square root of the input number will not work if the input number is negative. val squareRoot:� In this tutorial, we will be looking at partial functions in Scala. A partial function is a function applicable to a subset of the data it has been defined for. For example, we could define a function on the Int domain that only works on odd numbers. 2.

dict.get(e) = O(1) or up to O(N) depends on how Map treats collisions or how hashcodes are distributed dict.find { case (k, v) => k == e } map (_._2) = O(N) due to .find implementation. If we go deeper to method find implementation we will see:

override /*TraversableLike*/ def find(p: A => Boolean): Option[A] =
    iterator.find(p)

then deeper:

  def find(p: A => Boolean): Option[A] = {
    while (hasNext) {
      val a = next()
      if (p(a)) return Some(a)
    }
    None
  }

and here we can see while loop iterating over all elements in Iterator until passed function p: A => Boolean returns true. So we have max N iterations here.

I wasn't so lazy and wrote a benchmark using sbt-jmh:

import java.util.concurrent.TimeUnit
import org.openjdk.jmh.annotations.{Benchmark, OutputTimeUnit, Scope, State}

@State(Scope.Benchmark)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
class FindElementBenchmark {

  val dict: Map[String, Any] =
    (0 to 100).foldLeft(Map.empty[String, Any])((m, i) => m + (s"key$i" ->s"value$i"))

  val e: String = "key99"

  // First using normal dictionary lookup
  @Benchmark
  def findElementDict: Option[Any] =
    dict.get(e)

  // Second using Partial function
  @Benchmark
  def findElementPF: Option[Any] =
    dict
      .find { case (k, v) => k == e }
      .map(_._2)
}

run it:

$ sbt
$ sbt:benchmarks> jmh:run -i 20 -wi 10 -f1 -t1

and got results:

[info] Running (fork) org.openjdk.jmh.Main -i 20 -wi 10 -f1 -t1
[info] # JMH version: 1.21
[info] # VM version: JDK 1.8.0_161, Java HotSpot(TM) 64-Bit Server VM, 25.161-b12
[info] # VM invoker: /Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/bin/java
[info] # VM options: <none>
[info] # Warmup: 10 iterations, 10 s each
[info] # Measurement: 20 iterations, 10 s each
[info] # Timeout: 10 min per iteration
[info] # Threads: 1 thread, will synchronize iterations
[info] # Benchmark mode: Throughput, ops/time
[info] # Benchmark: bmks.FindElementBenchmark.findElementDict
[info] # Run progress: 0.00% complete, ETA 00:10:00
[info] # Fork: 1 of 1
[info] # Warmup Iteration   1: 48223.037 ops/ms
[info] # Warmup Iteration   2: 48570.873 ops/ms
[info] # Warmup Iteration   3: 48730.899 ops/ms
[info] # Warmup Iteration   4: 45050.838 ops/ms
[info] # Warmup Iteration   5: 48191.539 ops/ms
[info] # Warmup Iteration   6: 48464.603 ops/ms
[info] # Warmup Iteration   7: 48690.140 ops/ms
[info] # Warmup Iteration   8: 46432.571 ops/ms
[info] # Warmup Iteration   9: 46772.835 ops/ms
[info] # Warmup Iteration  10: 47214.496 ops/ms
[info] Iteration   1: 49149.297 ops/ms
[info] Iteration   2: 48476.424 ops/ms
[info] Iteration   3: 48590.436 ops/ms
[info] Iteration   4: 48214.015 ops/ms
[info] Iteration   5: 48698.636 ops/ms
[info] Iteration   6: 48686.357 ops/ms
[info] Iteration   7: 48948.054 ops/ms
[info] Iteration   8: 48917.577 ops/ms
[info] Iteration   9: 48872.980 ops/ms
[info] Iteration  10: 48970.421 ops/ms
[info] Iteration  11: 46269.031 ops/ms
[info] Iteration  12: 44934.335 ops/ms
[info] Iteration  13: 46279.314 ops/ms
[info] Iteration  14: 47721.223 ops/ms
[info] Iteration  15: 46238.490 ops/ms
[info] Iteration  16: 47453.282 ops/ms
[info] Iteration  17: 47886.762 ops/ms
[info] Iteration  18: 48032.580 ops/ms
[info] Iteration  19: 48142.064 ops/ms
[info] Iteration  20: 48460.665 ops/ms
[info] Result "bmks.FindElementBenchmark.findElementDict":
[info]   47947.097 ±(99.9%) 1003.440 ops/ms [Average]
[info]   (min, avg, max) = (44934.335, 47947.097, 49149.297), stdev = 1155.563
[info]   CI (99.9%): [46943.657, 48950.537] (assumes normal distribution)
[info] # JMH version: 1.21
[info] # VM version: JDK 1.8.0_161, Java HotSpot(TM) 64-Bit Server VM, 25.161-b12
[info] # VM invoker: /Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/bin/java
[info] # VM options: <none>
[info] # Warmup: 10 iterations, 10 s each
[info] # Measurement: 20 iterations, 10 s each
[info] # Timeout: 10 min per iteration
[info] # Threads: 1 thread, will synchronize iterations
[info] # Benchmark mode: Throughput, ops/time
[info] # Benchmark: bmks.FindElementBenchmark.findElementPF
[info] # Run progress: 50.00% complete, ETA 00:05:00
[info] # Fork: 1 of 1
[info] # Warmup Iteration   1: 7261.136 ops/ms
[info] # Warmup Iteration   2: 7548.525 ops/ms
[info] # Warmup Iteration   3: 7517.692 ops/ms
[info] # Warmup Iteration   4: 7126.543 ops/ms
[info] # Warmup Iteration   5: 7732.285 ops/ms
[info] # Warmup Iteration   6: 7525.456 ops/ms
[info] # Warmup Iteration   7: 7739.055 ops/ms
[info] # Warmup Iteration   8: 7555.671 ops/ms
[info] # Warmup Iteration   9: 7624.464 ops/ms
[info] # Warmup Iteration  10: 7527.114 ops/ms
[info] Iteration   1: 7631.426 ops/ms
[info] Iteration   2: 7607.643 ops/ms
[info] Iteration   3: 7636.029 ops/ms
[info] Iteration   4: 7413.881 ops/ms
[info] Iteration   5: 7726.417 ops/ms
[info] Iteration   6: 7410.291 ops/ms
[info] Iteration   7: 7452.339 ops/ms
[info] Iteration   8: 7825.050 ops/ms
[info] Iteration   9: 7801.677 ops/ms
[info] Iteration  10: 7783.978 ops/ms
[info] Iteration  11: 7788.909 ops/ms
[info] Iteration  12: 7778.982 ops/ms
[info] Iteration  13: 7784.158 ops/ms
[info] Iteration  14: 7771.173 ops/ms
[info] Iteration  15: 7750.280 ops/ms
[info] Iteration  16: 7813.570 ops/ms
[info] Iteration  17: 7845.550 ops/ms
[info] Iteration  18: 7841.003 ops/ms
[info] Iteration  19: 7808.576 ops/ms
[info] Iteration  20: 7847.100 ops/ms
[info] Result "bmks.FindElementBenchmark.findElementPF":
[info]   7715.902 ±(99.9%) 124.303 ops/ms [Average]
[info]   (min, avg, max) = (7410.291, 7715.902, 7847.100), stdev = 143.148
[info]   CI (99.9%): [7591.598, 7840.205] (assumes normal distribution)
[info] # Run complete. Total time: 00:10:01
[info] REMEMBER: The numbers below are just data. To gain reusable insights, you need to follow up on
[info] why the numbers are the way they are. Use profilers (see -prof, -lprof), design factorial
[info] experiments, perform baseline and negative tests that provide experimental control, make sure
[info] the benchmarking environment is safe on JVM/OS/HW level, ask for reviews from the domain experts.
[info] Do not assume the numbers tell you what you want them to tell.
[info] Benchmark                              Mode  Cnt      Score      Error   Units
[info] FindElementBenchmark.findElementDict  thrpt   20  47947.097 ± 1003.440  ops/ms
[info] FindElementBenchmark.findElementPF    thrpt   20   7715.902 ±  124.303  ops/ms
[success] Total time: 603 s, completed Apr 30, 2019 7:33:10 PM

As we can see findElementPF has 7 times worse score. I have just proofed theoretically algorithm complexity evaluation.

Partial & Partially Applied Functions in Scala, Using Else, orElse. A terrific feature of Scala partial function is that you can chain them together. For Example – one method may only work with odd numbers and � A partial function is a function that is valid for only a subset of values of those types you might pass in to it. For example: val root: PartialFunction[Double,Double] = { case d if (d >= 0) => math.sqrt(d) } scala> root.isDefinedAt(-1) res0: Boolean = false scala> root(3) res1: Double = 1.7320508075688772.

EDIT: OP has edited their question to remove the references to "Partially Applied Functions" so the sections are no longer relevant. I'm leaving them here though since it might be good value to someone else mixing them up.

That isn't a Partially Applied Function, but instead a PartialFunction (https://www.scala-lang.org/api/current/scala/PartialFunction.html).

A Partially Applied function is a function with multiple parameters that you've supplied only part of, and you can hand that partially applied function to someone else to supply the rest.

A Partial Function is defined in the docs as:

A partial function of type PartialFunction[A, B] is a unary function where the domain does not necessarily include all values of type A. The function isDefinedAt allows to test dynamically if a value is in the domain of the function.

The case you've supplied should cover all cases since your domain is all Tuple2s as you're not guarding against particular values, but it's not forced upon you to cover all the cases in a PartialFunction.

Scala Partial Function, A partial function caters to only a subset of possible data for which it has been defined. In order to assist developers, if the partial function is� A partial function caters to only a subset of possible data for which it has been defined. In order to assist developers, if the partial function is defined for a given input, Scala's

Partial Functions in Scala, Introduction: When a function is not able to produce a return for every single variable input data given to it then that function is termed as Partial� a partial function with the domain of other partial function narrowed by this partial function, which maps arguments x to this(k(x)). def compose [ A ] ( g: ( A ) => A ) : ( A ) => B Composes two instances of Function1 in a new Function1, with this function applied last.

Partial Functions in Scala, Functions in Scala are first class citizensand as such you can composethem. Let's go ahead and use the orElse()function which is inherited from the PartialFunction trait and create another PartialFunction named donutTaste. println(" Step 5: How to compose PartialFunction using orElse")

Pattern Matching in Scala can be extended to create Partialfunctions, a unary function that does not support every possible value that meets the input type. Partial functions are defined only for

Comments
  • It'd be too long to explain every syntax used here and I'm sure there are some you can already understand. Can you precise which part of the function you don't understand? For instance, find or { case (k, v) => k == e } or map (_._2).
  • I am trying to understand the use of case keyword in the context of a parameter
  • Thank you Mateusz. What is the BigO for the partial function which uses the case keyword? Does it iterate over all the elements of the map to find the right key?
  • @RHT yes it does, as such it is O(N) (on the worst case). You can confirm that by check the scaladoc of Map, you can see that find is not overridden by Map and that it inherits the one from TrasversableLike which (as you can check on the source) just calls find on the internal iterator.