Find the first element that satisfies condition X in a Seq

Question

Generally, how to find the first element satisfying certain condition in a Seq?

For example, I have a list of possible date format, and I want to find the parsed result of first one format can parse my date string.

val str = "1903 January"
val formats = List("MMM yyyy", "yyyy MMM", "MM yyyy", "MM, yyyy")
  .map(new SimpleDateFormat(_))
formats.flatMap(f => {try {
  Some(f.parse(str))
}catch {
  case e: Throwable => None
}}).head

Not bad. But 1. it's a little ugly. 2. it did some unnecessary work(tried "MM yyyy" and "MM, yyyy" formats). Perhaps there is more elegant and idiomatic way? (using Iterator?)

Not the same, bu related: if you already have a `X => Option[R]` function (which decides the applicability of the function + does return the actual application/mapping), you can easily convert that function to a `PartialFunction`, thus then being able to use it for your sequence in `collectFirst`. See: `Function.unlift` (https://www.scala-lang.org/api/2.11.x/#scala.Function$). -- More info here: https://stackoverflow.com/questions/1908295/how-to-convert-x-optionr-to-partialfunctionx-r — juanmirocks, Nov 22 '18 at 08:57

vitalii · Answer 1 · 2013-06-02T15:03:49.053

You should use find method on sequences. Generally you should prefer built-in methods, because they might be optimised for a specific sequence.

Console println List(1,2,3,4,5).find( _ == 5)
res: Some(5)

That is, to return first SimpleDateFormat that match:

 val str = "1903 January"
 val formats = List("MMM yyyy", "yyyy MMM", "MM yyyy", "MM, yyyy")
   .map(new SimpleDateFormat(_))
 formats.find { sdf => 
      sdf.parse(str, new ParsePosition(0)) != null
 }

 res: Some(java.text.SimpleDateFormat@ef736ccd)

To return first date that has being processed:

val str = "1903 January"
val formats = List("MMM yyyy", "yyyy MMM", "MM yyyy", "MM, yyyy").map(new SimpleDateFormat(_))
val result = formats.collectFirst { 
  case sdf if sdf.parse(str, new ParsePosition(0)) != null => sdf.parse(str)
}

or use lazy collection:

val str = "1903 January"
val formats = List("MMM yyyy", "yyyy MMM", "MM yyyy", "MM, yyyy").map(new SimpleDateFormat(_))
formats.toStream.flatMap { sdf =>
   Option(sdf.parse(str, new ParsePosition(0)))
}.headOption

res: Some(Thu Jan 01 00:00:00 EET 1903)

I did provide full working example. Guy is asking how generally find the first element in a sequence. — vitalii, Jun 02 '13 at 14:25
That is not what the OP asked for; instead of returning the first successful parse result, you are returning the first `SimpleDateFormat` which parsed it. — Ben James, Jun 02 '13 at 14:47

score 25 · Accepted Answer · edited Oct 03 '16 at 23:37

25

If you're confident at least one will format will succeed:

formats.view.map{format => Try(format.parse(str)).toOption}.filter(_.isDefined).head

If you want to be a bit safer:

formats.view.map{format => Try(format.parse(str)).toOption}.find(_.isDefined)

Try was introduced in Scala 2.10.

A view is a type of collection that computes values lazily. It will apply the code within the Try to only as many items in the collection as is necessary to find the first one that is defined. If the first format applies to the string, then it won't try to apply the remaining formats to the string.

edited Oct 03 '16 at 23:37

Cory Klein

51,188
43
183
243

answered Jun 02 '13 at 14:48

Infinity

3,431
3
25
46

10

This answer has two anti patterns: i) unexpected exceptions thrown in the Try will be lost, causing it to hide bugs and return incorrect answers (for example, what if the list if a view of a database?) ii) filter construct a temporary list and also requires that ALL elements are visited even if only the first is required. Its unnecessarily expensive in time, but particularly also in memory. – user48956 Sep 07 '16 at 15:27

score 10 · Answer 3 · answered Jun 03 '13 at 04:29

10

This prevents the unnecessary evaluations.

formats.collectFirst{ case format if Try(format.parse(str)).isSuccess => format.parse(str) }

The number of evaluations of the parse method is number of tries + 1.

answered Jun 03 '13 at 04:29

tiran

2,389
1
16
28

score 5 · Answer 4 · answered Aug 03 '18 at 08:08

Just use find method as it returns an Option of the first element matching predicate if any :

formats.find(str => Try(format.parse(str)).isSuccess)

Moreover, execution stops at the first match, so that you don't try parsing every element of your set before picking the first one. Here is an example :

def isSuccess(t: Int) = {
  println(s"Testing $t")
  Math.floorMod(t, 3) == 0
}
isSuccess: isSuccess[](val t: Int) => Boolean

List(10, 20, 30, 40, 50, 60, 70, 80, 90).filter(isSuccess).headOption
Testing 10
Testing 20
Testing 30
Testing 40
Testing 50
Testing 60
Testing 70
Testing 80
Testing 90
res1: Option[Int] = Some(30)

Stream(10, 20, 30, 40, 50, 60, 70, 80, 90).filter(isSuccess).headOption
Testing 10
Testing 20
Testing 30
res2: Option[Int] = Some(30)

List(10, 20, 30, 40, 50, 60, 70, 80, 90).find(isSuccess)
Testing 10
Testing 20
Testing 30
res0: Option[Int] = Some(30)

Note that for Stream it doesn't really matter. Also if you are using IntelliJ for example it will suggest you :

Replace filter and headOption with find.
Before:

seq.filter(p).headOption

After:

seq.find(p)

score 3 · Answer 5 · answered Apr 28 '17 at 09:21

Same version with Scala Extractor and lazyness:

case class ParseSpec(dateString: String, formatter:DateTimeFormatter)


object Parsed {
  def unapply(parsableDate: ParseSpec): Option[LocalDate] = Try(
    LocalDate.parse(parsableDate.dateString, parsableDate.formatter)
  ).toOption
}


private def parseDate(dateString: String): Option[LocalDate] = {
  formats.view.
    map(ParseSpec(dateString, _)).
     collectFirst  { case Parsed(date: LocalDate) => date }
}

Ben James · Answer 6 · 2013-06-02T21:50:44.523

scala> def parseOpt(fmt: SimpleDateFormat)(str: String): Option[Date] =
     |   Option(fmt.parse(str, new ParsePosition(0)))
tryParse: (str: String, fmt: java.text.SimpleDateFormat)Option[java.util.Date]

scala> formats.view.flatMap(parseOpt(fmt)).headOption
res0: Option[java.util.Date] = Some(Thu Jan 01 00:00:00 GMT 1903)

By the way, since SimpleDateFormat is non-thread-safe, that means the above code is not thread-safe either!

score 2 · Answer 7 · answered Apr 03 '18 at 07:32

I think using tail recursion is much better and by far the most efficient solution offered here so far:

implicit class ExtendedIterable[T](iterable: Iterable[T]) {
  def findFirst(predicate: (T) => Boolean): Option[T] = {
    @tailrec
    def findFirstInternal(remainingItems: Iterable[T]): Option[T] = {
      if (remainingItems.nonEmpty)
        if (predicate(remainingItems.head))
          Some(remainingItems.head)
        else
          findFirstInternal(remainingItems.tail)
      else
        None
    }
    findFirstInternal(iterable)
  }
}

It would allow you upon importing the above class to simply do the something like the following wherever you need to:

formats.findFirst(format => Try(format.parse(str)).isSuccess)

Best of luck!

bcoromina · Answer 8 · 2020-02-20T09:19:22.130

Using org.joda.time:

Definition:

def getBaseLocalFromFormats[T <: BaseLocal](
                        value: String, 
                        validPatterns: Seq[String], 
                        parse: (String, String)  => T) : Option[T] = {
    validPatterns.view.map(p => Try{ parse(value, p) }).find(_.isSuccess).map(_.get)
  }

Usage:

getBaseLocalFromFormats( 
                "01/10/1980 16:08:22",
                List("dd/MM/yyyy HH:mm:ss"),
                (v,p) => DateTimeFormat.forPattern(p).parseLocalDateTime(v))

getBaseLocalFromFormats( 
                "01/10/1980",
                List("dd/MM/yyyy",  "dd-MM-yyyy", "yyyy-MM-dd"),
                (v,p) => DateTimeFormat.forPattern(p).parseLocalDate(v))

Find the first element that satisfies condition X in a Seq

8 Answers8

Linked

Related