49

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?)

2
  • Use find method of Seq
    – Kakaji
    Sep 28, 2017 at 10:50
  • 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 (scala-lang.org/api/2.11.x/#scala.Function$). -- More info here: stackoverflow.com/questions/1908295/… Nov 22, 2018 at 8:57

8 Answers 8

37

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)
3
  • I did provide full working example. Guy is asking how generally find the first element in a sequence.
    – vitalii
    Jun 2, 2013 at 14:25
  • here you go, the one with dates
    – vitalii
    Jun 2, 2013 at 14:32
  • 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 2, 2013 at 14:47
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.

1
  • 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 7, 2016 at 15:27
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.

5

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)
3

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 }
}
2
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!

2

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!

0

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))

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.