高效优雅地从一个 case class 结构的列表中删除元素

Question

我是一名有用的助手，可以为您进行文本翻译。以下是需要翻译的内容：

我在一个List中有一个嵌套的case类结构

为了简单起见，我们将使用以下示例 -

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])

假设有一个 List[Department]；现在如果我想通过过滤每个 Person 的 Address 来创建一个新的 List[Department]，这些人没有特定的 zipCode 值；传统上我们可以按照以下方式操作：

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)
    }
 }

这种方法并不高效，因为它取决于嵌套级别，可能是O(n^2)或O(n^3)；

我正在尝试通过Monocle学习Lenses。到目前为止，我学到的是当你必须“修改”一个深度嵌套的case类结构时，Lenses非常有用，但还没有找到一种基于条件“chop off”某个嵌套结构部分并返回一个新结构的方法。在Monocle中是否可能实现这一点？此外，我不确定Lenses是否能够帮助实现更好的Big O时间复杂度？

- Vikas Pandya

---

考虑到要确定一个部门是否应该在新的部门中，必须查看所有人的所有地址，因此我认为它只能是O（#d * #p * #a）。 - The Archetypal Paul

@TheArchetypalPaul：不是不同意你的评论。这可能会忽略问题中的“高效”部分；仍在寻找一种优雅的方法来解决这个问题，看看Lenses/Monocle是否能够帮助。你知道吗？ - Vikas Pandya

阅读有关“Lenses”概念的文章。一些库，如Monocle/scalaz实现了它。 - Maxim

@Maxim，嗯，是的，原帖中已经在问题中说过了！ - The Archetypal Paul

@VikasPandya，为什么要复制/切割？在您的用例中，过滤掉其他人的地址而不是将人的记录视为不可变的，并只生成至少有一个正确邮政编码的地址列表，这是有意义的吗？您似乎会给自己带来未来的问题，如何确定哪个Person对象正确地捕获了该人的当前详细信息... - The Archetypal Paul

Answer 1

以下实质上在性能方面与您的实现基本等效，但可以争议地更清晰：

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))

这只是构建了一个遍历来导航到每个人的地址列表，以便您可以基于谓词进行修改。我不确定是否有更好的方法执行过滤（因为邮政编码不作为唯一索引），但也许Julien会提出一个。

- Travis Brown