CODEWITHSUNDEEP
scalacollections
Michael
Michael

Reputation: 42110

How to replace or append an item in/to a list?

Suppose I've got a list of case class A(id: Int, str: String) and an instance of A. I need to either replace an item from the list with the new instance or append the new instance to the list.

case class A(id: Int, str: String)
def replaceOrAppend(as: List[A], a: A): List[A] = ???

val as = List(A(1, "a1"), A(2, "a2"), A(3, "a3"))
replaceOrAppend(as, A(2, "xyz")) // List(A(1, "a1"), A(2, "xyz"), A(3, "a3"))
replaceOrAppend(as, A(5, "xyz")) // List(A(1, "a1"), A(2, "a2"), A(3, "a3"), A(5, "xyz"))

I can write replaceOrAppend like this:

def replaceOrAppend(as: List[A], a: A): List[A] =
  if (as.exists(_.id == a.id)) as.map(x => if (x.id == a.id) a else x) else as :+ a

This implementation is a bit clumsy and obviously suboptimal since it passes the input list twice. How to implement replaceOrAppend to pass the input list just once ?

Upvotes: 1

Views: 146

Answers (4)

pme
pme

Reputation: 14813

If the order is not essential I would go with:

def replaceOrAppend(as: List[A], a: A): List[A] =
  a::as.filterNot(_.id == a.id)

This would also work if the order is related to id or str:

def replaceOrAppend(as: List[A], a: A): List[A] =
  (a::as.filterNot(_.id == a.id)).sortBy(_.id)

And if the order must be kept (as Micheal suggested - I couldn't find anything better):

 def replaceOrAppend(as: List[A], a: A): List[A] =
  as.span(_.id != a.id) match { case (xs, ys) => xs ++ (a :: ys.drop(1)) }

Upvotes: 2

Luis Miguel Mejía Suárez
Luis Miguel Mejía Suárez

Reputation: 22895

I do not understand why people forgets that the best way to handle a functional list is through pattern matching + tail-recursion.
IMHO, this looks cleaner and tries to be as efficient as possible.

final case class A(id: Int, str: String)

def replaceOrAppend(as: List[A], a: A): List[A] = {
  @annotation.tailrec
  def loop(remaining: List[A], acc: List[A]): List[A] =
    remaining match {
      case x :: xs if (x.id == a.id) =>
        acc reverse_::: (a :: xs)

      case x :: xs =>
        loop(remaining = xs, acc = x :: acc)

      case Nil =>
        (a :: acc).reverse
    }

  loop(remaining = as, acc = List.empty)
}

technically speaking, this traverse the list twice on the worst case.
But, it is always better to build a list by prepending from the head and reverse at the end, than to do many appends.

Upvotes: 1

rics
rics

Reputation: 5596

What about this? Still clumsy but only uses one iteration.

  def replaceOrAppend(as: List[A], a: A): List[A] = {
    val (updatedList,itemToAppend) = as.foldLeft((List[A](),Option(a))) {
      case ((acc, Some(item)), l) =>
        if (item.id == l.id) (acc :+ item, None)
        else (acc :+ l, Some(item))
      case ((acc, None), l) => (acc :+ l, None)
    }
    itemToAppend match {
      case Some(item) => updatedList :+ item
      case None => updatedList
    }
  }

Upvotes: 1

Catalina Chircu
Catalina Chircu

Reputation: 1574

Here is another one:

def replaceOrAppend(as: List[A], a: A): List[A] = {
  as.find(_.id==a.id).map(op => {
    as.map(el => el match  {
      case e if e.id==a.id => e.copy(str=a.str)
      case _ => el
    })
  }).getOrElse((a::as.reverse).reverse)
}

Upvotes: 1

Related Questions