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?

Given in order to determine if a departmentshould be in the new dept you have to look at all addresses of all people, then I don't see how it can be anything but O(#d * #p * #a). — The Archetypal Paul, Nov 09 '15 at 16:00
@TheArchetypalPaul : not disagreeing with your comment. That may leave out "efficient" part of the question; still looking for an elegant way to do this to see if Lenses/Monocle can help there. do you know? — Vikas Pandya, Nov 09 '15 at 17:13
Read about concept called `Lenses`. Some libraries like Monocle/scalaz implement it. — Maxim, Nov 09 '15 at 17:25
@Maxim, er, yes, the OP did already say that in the question! — The Archetypal Paul, Nov 09 '15 at 17:30
@VikasPandya, why all the copies/chopping? Why in your use-case does it make sense to filter out the other address of people, rather than regard a person's record as immutable and just produce a list of people with at least one address with the right zip code? You'd seem to be be giving yourself a future issue with working out which Person object captures the current details of that person correctly... — The Archetypal Paul, Nov 09 '15 at 17:35

score 4 · Accepted Answer · answered Nov 09 '15 at 17:57

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.

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

1 Answers1