CODEWITHSUNDEEP
scalacollections
Michael
Michael

Reputation: 42050

How to find two elements satisfying two predicates in one pass with Scala?

Suppose there is a List[A] and two predicates p1: A => Boolean and p2: A => Boolean.
I need to find two elements in the list: the first element a1 satisfying p1 and the first element a2 satisfying p2 (in my case a1 != a2)

Obviously, I can run find twice but I would like to do it in one pass. How would you do it in one pass in Scala ?

Upvotes: 2

Views: 203

Answers (3)

The Archetypal Paul
The Archetypal Paul

Reputation: 41749

So, here's an attempt. It's fairly straightforward to generalise it to take a list of predicates (and return a list of elements found) 

def find2[A](xs: List[A], p1: A => Boolean, p2: A => Boolean): (Option[A], Option[A]) = {
  def find2helper(xs: List[A], p1: A => Boolean, p2: A => Boolean, soFar: (Option[A], Option[A])): (Option[A], Option[A]) = {
    if (xs == Nil) soFar
    else {
      val a1 = if (soFar._1.isDefined) soFar._1 else if (p1(xs.head)) Some(xs.head) else None
      val a2 = if (soFar._2.isDefined) soFar._2 else if (p2(xs.head)) Some(xs.head) else None
      if (a1.isDefined && a2.isDefined) (a1, a2) else find2helper(xs.tail, p1, p2, (a1, a2))
    }
  }
  find2helper(xs, p1, p2, (None, None))

 } //> find2: [A](xs: List[A], p1: A => Boolean, p2: A => Boolean)(Option[A], Option[A])

  val foo = List(1, 2, 3, 4, 5) //> foo  : List[Int] = List(1, 2, 3, 4, 5)

  find2[Int](foo, { x: Int => x > 2 }, { x: Int => x % 2 == 0 })
  //> res0: (Option[Int], Option[Int]) = (Some(3),Some(2))
  find2[Int](foo, { x: Int => x > 2 }, { x: Int => x % 7 == 0 })
  //> res1: (Option[Int], Option[Int]) = (Some(3),None)
  find2[Int](foo, { x: Int => x > 7 }, { x: Int => x % 2 == 0 })
  //> res2: (Option[Int], Option[Int]) = (None,Some(2))
  find2[Int](foo, { x: Int => x > 7 }, { x: Int => x % 7 == 0 })
  //> res3: (Option[Int], Option[Int]) = (None,None)

Generalised version (which is actually slightly clearer, I think) 

def findN[A](xs: List[A], ps: List[A => Boolean]): List[Option[A]] = {
  def findNhelper(xs: List[A], ps: List[A => Boolean], soFar: List[Option[A]]): List[Option[A]] = {
    if (xs == Nil) soFar
    else {
      val as = ps.zip(soFar).map {
          case (p, e) => if (e.isDefined) e else if (p(xs.head)) Some(xs.head) else None
      }
      if (as.forall(_.isDefined)) as else findNhelper(xs.tail, ps, as)
    }
  }
  findNhelper(xs, ps, List.fill(ps.length)(None))

} //> findN: [A](xs: List[A], ps: List[A => Boolean])List[Option[A]]

val foo = List(1, 2, 3, 4, 5) //> foo  : List[Int] = List(1, 2, 3, 4, 5)

findN[Int](foo, List({ x: Int => x > 2 }, { x: Int => x % 2 == 0 }))
//> res0: List[Option[Int]] = List(Some(3), Some(2))
findN[Int](foo, List({ x: Int => x > 2 }, { x: Int => x % 7 == 0 }))
//> res1: List[Option[Int]] = List(Some(3), None)
findN[Int](foo, List({ x: Int => x > 7 }, { x: Int => x % 2 == 0 }))
//> res2: List[Option[Int]] = List(None, Some(2))
findN[Int](foo, List({ x: Int => x > 7 }, { x: Int => x % 7 == 0 }))
//> res3: List[Option[Int]] = List(None, None)

Upvotes: 1

Electric Coffee
Electric Coffee

Reputation: 12104

Does this work for you?

def predFilter[A](lst: List[A], p1: A => Boolean, p2: A => Boolean): List[A] =
  lst.filter(x => p1(x) || p2(x)) // or p1(x) && p2(x) depending on your need

This will return you a new list that matches either of the predicates.

val a = List(1,2,3,4,5)
val b = predFilter[Int](a, _ % 2 == 0, _ % 3 == 0) // b is now List(2, 3, 4)

Upvotes: 1

Ashalynd
Ashalynd

Reputation: 12563

scala> val l = List(1,2,3)
l: List[Int] = List(1, 2, 3)

scala> val p1 = {x:Int =>  x % 2 == 0}
p1: Int => Boolean = <function1>

scala> val p2 = {x:Int =>  x % 3 == 0}
p2: Int => Boolean = <function1>

scala> val pp = {x:Int => p1(x) || p2(x) }
pp: Int => Boolean = <function1>

scala> l.find(pp)
res2: Option[Int] = Some(2)

scala> l.filter(pp)
res3: List[Int] = List(2, 3)

Upvotes: 1

Related Questions