remove elements from a List of case class structure efficiently and elegantly

Question

I have a nested case classes structure in a List

for simplicity will use following as an example -

case class Address(street: String, city: String, state: String, zipCode: Int)
case class Person(firstName: String, lastName: String, addresses: List[Address])
case class Department(people: List[Person])

say there is List[Department] ; now if I wan to create a new List[Department] by filtering Address for each Person which doesn't have a specific zipCode value ; traditionally we can do following

def filterPersonsByAddress(dlist: List[Department]): List[Department] = {
  dlist.map { d =>
    val people = d.people.map { p => 
      p.copy(addresses = p.addresses.filterNot(_.zipCode == 38978))}
      d.copy(people=people)
    }
 }

This approach is not performant as depending on the nesting level it can be Big O(n^2) or Big O(n^3) ;

I am trying to learn Lenses via Monocle. So far what I have learned is Lenses is useful when you have to "modify" a deeply nested case class structure but haven't yet found a way to "chop off" certain part of nested structure based on a condition and return a new structure. Is this possible for via Monocle? Also I am not sure if Lenses will be able to help in achieving better Big O time as well?

Answer 1

The following is essentially equivalent to your implementation in terms of performance, but it's arguable clearer:

import monocle.Traversal, monocle.macros.GenLens
import monocle.function.all._, monocle.std.list._

val deptAddresses: Traversal[Department, List[Address]] =
  GenLens[Department](_.people)
    .composeTraversal(each)
    .composeLens(GenLens[Person](_.addresses))

val filterAddresses: Department => Department =
  deptAddresses.modify(_.filterNot(_.zipCode == 38978))

This just builds a traversal to navigate to each person's list of addresses so that you can modify it based on the predicate. I'm not sure there's a better way to perform the filtering (since zip codes don't serve as unique indices), but maybe Julien will weigh in with one.