CODEWITHSUNDEEP
scalascala-collections
ForeverLearner
ForeverLearner

Reputation: 2103

How can I preserve both matching and non-matching parts using immutable collection in O(n) time

I have to operate on tmp list based on some condition. false does a bulk db insert and true does an update

val tmp = List(1,2,3, 15)
val bool = List(true, true, true, false)

I am using the below approach to create 2 lists , one matching and one non-matching.

val result = tmp.zip(bool).partition {
case tuple if tuple._2 => true
case tuple if !tuple._2 => false
}

I get 2 lists , so I can run insertAll(result._2) and updateAll(result._1)

Since partition uses scala.collection.mutable.Builder, I was trying to find an approach that solves the problem using immutable collections.

Upvotes: 0

Views: 70

Answers (2)

Tim
Tim

Reputation: 27356

This is a recursive partition function using immutable data

def part[T](list: List[T])(f: T => Boolean): (List[T], List[T]) = {
  @annotation.tailrec
  def loop(rem: List[T], res1: List[T], res2: List[T]): (List[T], List[T]) =
    rem match {
      case Nil =>
        (res1.reverse, res2.reverse)
      case hd :: tail =>
        if (f(hd)) {
          loop(tail, hd +: res1, res2)
        } else {
          loop(tail, res1, hd +: res2)
        }
    }

  loop(list, Nil, Nil)
}

This solution is built in reverse to keep the algorithm O(n)

Upvotes: 1

stefanobaghino
stefanobaghino

Reputation: 12804

I came up with two solutions. I don't find either fully satisfactory but hopefully they can help you achieve your goal.

The first one is tail recursive but reverses the original input. It may be enough for your use case if you don't care about the order, but if you do you have to reverse the resulting lists before returning them, which involves a second pass through the list (O(n)):

def zipAndPartition[A, B](as: List[A], bs: List[B])(p: ((A, B)) => Boolean): (List[(A, B)], List[(A, B)]) = {
  @annotation.tailrec
  def loop(left: List[A], right: List[B], acc: (List[(A, B)], List[(A, B)])): (List[(A, B)], List[(A, B)]) =
    (left, right) match {
      case (Nil, _) | (_, Nil) => acc
      case (lhead :: ltail, rhead :: rtail) if p((lhead, rhead)) => loop(ltail, rtail, ((lhead, rhead) :: acc._1, acc._2))
      case (lhead :: ltail, rhead :: rtail) => loop(ltail, rtail, (acc._1, (lhead, rhead) :: acc._2))
    }

  val (left, right) = loop(as, bs, (Nil, Nil))
  (left.reverse, right.reverse)
}

The second doesn't require reversing the outputs before returning them but relies on mutually recursive functions and thus cannot be annotated with @annotation.tailrec:

def zap[A, B](as: List[A], bs: List[B])(p: ((A, B)) => Boolean): (List[(A, B)], List[(A, B)]) = {
  def loop(left: List[A], right: List[B], acc: (List[(A, B)], List[(A, B)])): (List[(A, B)], List[(A, B)]) =
    (left, right) match {
      case (Nil, _) | (_, Nil) => acc
      case (lhead :: ltail, rhead :: rtail) if p((lhead, rhead)) =>
        val tail = zap(ltail, rtail)(p)
        ((lhead, rhead) :: tail._1, tail._2)
      case (lhead :: ltail, rhead :: rtail) =>
        val tail = zap(ltail, rtail)(p)
        (tail._1, (lhead, rhead) :: tail._2)
    }

  loop(as, bs, (Nil, Nil))
}

You can play around with this code here on Scastie.

Edit

A third solution, which retains the shortcomings of the first but is probably more readable, splits the problem in two and uses function composition:

val tmp = List(1, 2, 3, 15)
val bool = List(true, true, true, false)

def zip[A, B](as: List[A], bs: List[B]): List[(A, B)] = {
  @annotation.tailrec
  def loop(left: List[A], right: List[B], acc: List[(A, B)]): List[(A, B)] =
    (left, right) match {
      case (Nil, _) | (_, Nil) => acc
      case (lhead :: ltail, rhead :: rtail) => loop(ltail, rtail, (lhead, rhead) :: acc)
    }
  loop(as, bs, Nil)
}

def partition[A](as: List[A])(p: A => Boolean): (List[A], List[A]) = {
  @annotation.tailrec
  def loop(list: List[A], acc: (List[A], List[A])): (List[A], List[A]) =
    list match {
      case Nil => acc
      case head :: tail if p(head) => loop(tail, (head :: acc._1, acc._2))
      case head :: tail => loop(tail, (acc._1, head:: acc._2))
    }
  loop(as, (Nil, Nil))
}

def zap[A, B] = (zip[A, B] _).tupled.andThen(partition[(A, B)] _)

zap(tmp, bool)(_._2)

This solution is available on Scastie as well.

Upvotes: 1

Related Questions