Is there an Option *cousin* of find

Question
1

Given a function f which of type A=>Option[B] and an object domain of type List[A],
Is there already a function which is a cousin of find but rather than returning the element of domain for which f returns true, instead I want to find the first return value of f which is not None. Important is the hope that f be called as few times as possible, as in my application f is an expensive operation.

Of course it would be great if it wasn’t limited to List. I can write the function which works for List, but not sure what its most general useful form might be.

Here is my implementation. I’m happy to see an improved implementation.

      def findOption[A,B](domain:List[A], f:A=>Option[B]):Option[B] = {
        domain match {
          case Nil => None
          case d::tail => {
            f(d) match {
              case None => findOption(tail,f)
              case found => found
            }
          }
        }
      }
1 Like
2

Hmm. List.collectFirst() is pretty close to what you’re looking for, if not quite exact – it takes a PartialFunction, so I think it would be something like (NB: I haven’t tried compiling this yet):

val myList: List[A] = ...
val myFunc: A => Option[B] = ...

val result: Option[B] = myList.collectFirst(Function.unlift(myFunc))

I think that does what you want, but can’t swear to it offhand…

2 Likes
3

You can use collectFirst:

val b: Option[B] = domain.collectFirst(Function.unlift(f))

Note that depending on how you create f, you may be able to define it as a PartialFunction directly (unlift converts a function to Option to a PartialFunction)

edit: @jducoeur was faster :slight_smile:

4

When I look at the comment on unlift it says

   *  '''Important note''': this transformation implies the original function
   *  may be called 2 or more times on each logical invocation, because the
   *  only way to supply an implementation of `isDefinedAt` is to call the
   *  function and examine the return value.

Do I interpret this correctly, that it will call my function f twice for each element of the domain? If so, perhaps I should stick with my own implementation?

5

This depends on how you want to use the unlifted function. In case of passing it to collectFirst on standard library collections, this is not a problem, as they use applyOrElse, which combines the isDefinedAt and apply calls. Function.unlift implements this correctly to have only one call to the function.

If you write custom code accepting a partial function, you should check if it can be implemented via applyOrElse instead of manually checking isDefinedAt.

1 Like
6

Don’t assume. Benchmark!

[info] Benchmark                                           Mode  Cnt       Score       Error  Units
[info] CollectFirstBenchmarks.benchmarkExpensiveJducoeur  thrpt    3      30.048 ±     4.739  ops/s
[info] CollectFirstBenchmarks.benchmarkExpensiveJimka     thrpt    3      33.164 ±     4.042  ops/s
[info] CollectFirstBenchmarks.benchmarkTrivialJducoeur    thrpt    3  398059.516 ±  1846.454  ops/s
[info] CollectFirstBenchmarks.benchmarkTrivialJimka       thrpt    3  414243.844 ± 22601.452  ops/s

@jimka your version is a little faster. If you really want that 4-10% speed increase, go for it. I’d probably stick with the simple one unless it became a bottleneck.

7

It looks like in practice f is only called once per element for collectFirst, but if it’s a hard requirement ya, maybe it’s safest to not use it.

scala> def p(i: Int): Option[String] = {
  println("called")
  None
}

List(1,2).collectFirst(Function.unlift(p))
     |      |      | p: (i: Int)Option[String]

scala> called
called
res1: Option[String] = None