How to deep compare each element with other elements in a list in scala (optional fileds)

Question

I have case class that represents report, and report have expenses.

case class FakeExpense(amount: Option[Double], country: Option[String], currency: Option[String])
case class FakeReport(id: Int, expenses: List[FakeExpense])

and I want to return true/false if report is valid or not, and it is not valid if there is 2 expenses with the exact same fields...what would be the right way with scala to do something like this?

a valid report:

val report = FakeReport(1, List(FakeExpense(Some(150), Some("US"), Some("USD")),FakeExpense(Some(85), Some("DE"), Some("EUR"))))

a non valid report:

val report = FakeReport(2, List(FakeExpense(Some(150), Some("US"), Some("USD")),FakeExpense(Some(150), Some("US"), Some("USD"))))

Thanks!

Mario Galic · Accepted Answer · 2020-02-24T21:51:09.567

4

Consider List.distinct approach like so

def isValidReport(report: FakeReport): Boolean =
  report.expenses.distinct.length == report.expenses.length

The above solution makes three passes through the list. Applying Luis' comment we can reduce to two passes like so

def isValidReport(report: FakeReport): Boolean = {
  report.expenses.sizeIs == report.expenses.iterator.distinct.length
}

We shave off one pass because distinct.length collapses to a single transformation in iterator.distinct.length. sizeIs is a potential quick-savings where we might not have to go through the whole list.

Here is a single-pass tail-recursive solution based on HashSet having O(eC) lookup and insertion

def isValidReport(report: FakeReport): Boolean = {
  val set = mutable.HashSet[FakeExpense]()
  @tailrec def loop(l: List[FakeExpense]): Boolean = l match {
    case Nil => true
    case h :: t => if (set.add(h)) loop(t) else false
  }
  loop(report.expenses)
}

Also note how we might return early on first duplicate.

edited Feb 24 '20 at 21:51

answered Feb 24 '20 at 10:37

Mario Galic

47,285
6
56
98

I would use an `iterator` on the first one and `sizeIs` to reduce the number of iterations. – Luis Miguel Mejía Suárez Feb 24 '20 at 11:41
1

@LuisMiguelMejíaSuárez I could not figure out how `iterator` helps however I have updated question with single-pass solution based on `HashSet`. – Mario Galic Feb 24 '20 at 21:30
the `iterator` before the `distinct` would reduce the number of iterations from two to one. – Luis Miguel Mejía Suárez Feb 24 '20 at 21:32
@LuisMiguelMejíaSuárez Ah, do you mean because `iterator.distinct.length` becomes single transformation? – Mario Galic Feb 24 '20 at 21:39
Yeah, anyways your `HashSet` solution is better :p – Luis Miguel Mejía Suárez Feb 24 '20 at 21:45

Iva Kam · Answer 2 · 2020-02-24T16:11:08.453

If you need exactly same reports disregarding double comparison with epsilon(|a-b| < epsilon, where epsilon is small enough), you just can turn list to set as it will remove duplicate entries and then check if the size of your list changed.

fakeReport.expenses.toSet.length == fakeReport.expenses.length

It will work till everything that inside your classes you want to use with == correctly implement equals methods (primitive types, most of default classes, case classes and objects do so). What will not implement this correctly is an array and possibly certain java classes and these classes wrapped into AnyVal classes.

How to deep compare each element with other elements in a list in scala (optional fileds)

2 Answers2