haskell - 被多个数据结构引用时更新记录

Question

假设我有一个记录，例如Person ，并且我希望能够通过多个数据结构查找此人。也许有一个按姓名的索引，另一个按人的邮政编码的索引，以及另一个按人的当前纬度和经度的索引。也许还有更多的数据结构。所有这些都存在，因为我需要有效地查找一个或多个具有不同标准的人。

如果我只需要读取一个人的属性，this is no problem .但是现在假设我需要使用其中一种数据结构查找一个人，然后更新该人的数据。

在 OOP 语言中，每个数据结构都指向内存中的同一个人。因此，当您更新一个时，您也在隐式更新其他数据结构的所指对象。这几乎是副作用和杂质的定义。我知道这与 Haskell 范式完全背道而驰，而且我不希望 Haskell 以这种方式工作。

那么，Haskell 式的方法是什么？需要明确的是，问题是这样的:我通过一个数据结构查找一个人，然后将该人(可能还有一些其他任意数据)传递给 ArbitraryData -> Person -> Person 类型的函数。 .如何在所有各种查找结构中传播此更改？

作为一个相对较新的 Haskell，我的第一直觉是每次更新一个人时，用新更新的人重建每个查找结构。但这似乎是一种仪式，我有很多机会以 GHC 无法检测到的方式搞砸，而且一点也不优雅。 Haskell 以其优雅而闻名，我无法想象它缺少一个优雅的解决方案来解决这样一个常见的基本问题。所以我想我错过了一些东西。

作为引用，这个问题扩展了我在以下问题中讨论的一些问题:

Multiple lookup structures for same data: Memory duplication?

Identity of simulation objects in Haskell

编辑

我刚刚想到的一个解决方案:不要在主状态下维护每个查找结构的副本。只需保留一份所有人员的列表，这是我们更新人员时唯一需要更新的内容。每次您需要按邮政编码查找时，将所有人的列表传递给一个函数，该函数会生成有效的按邮政编码数据结构。然后对结果执行查找。

我不知道这是否有效。如果它导致 CPU 在每次使用时实际上都重新计算查找结构，这是 Not Acceptable 。但我知道 Haskell 有时可以避免重新评估相同的表达式。不幸的是，我还没有弄清楚什么时候会出现这种情况。所以我不知道这种方法是否可行。

所以换句话说:我可以编写我的函数，就好像它们每次都在计算查找一样，而实际上 GHC 会针对底层数据没有改变的情况对其进行优化？因为这将是我上面确定的问题的一个非常优雅的解决方案。

Answer 1

自从我回答了这个问题后，Freenode 上#haskell 中的一些人推荐了替代的预制解决方案:

mm_freak_推荐 Data.IxSet .

东利推荐 Data.Store ，据说可以提供镜片。

您可以创建一个包含查找表的数据结构，以及 Vector 实际的 Person s。查找表将为您提供 Int或 Int 的列表s(而不是 Person 或 Person 的列表)，它是 Vector Person 的索引.例如:

data PersonStuff = PersonStuff {
                                 persons              :: Vector Person,
                                 firstNameLookupTable :: LookupTable Name,
                                 ...
                               }

data LookupTable a = LookupTable {
                                   table  :: Map a Int,
                                   update :: Person -> Person -> Map a Int -> Map a Int
                                 }

update函数被赋予旧的 Person ，更新后的 Person ，并且只有在相关细节发生变化时才会更新表格。当一个 Person通过方便的 PersonStuff 进行修改您将编写的函数，这些函数将为您更新所有查找表，返回一个新的 PersonStuff与所有相关数据。这使得具有快速查找的纯数据结构成为可能。

您可以制作 updatePeopleWithFirstName :: Name -> (Person -> Person) -> PersonStuff -> PersonStuff 之类的函数这将得到所有有名字的人，应用 Person -> Person对于他们每个人，修改他们在 Vector 中的条目，并使用 update更新所有查找表的函数。