在由多个数据结构引用时更新记录

Question

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

如果我只需要阅读一个人的属性,这是没有问题的.但现在假设我需要使用其中一个数据结构查找一个人,然后更新该人的数据.

在OOP语言中,每个数据结构都指向内存中的同一个人.因此,当您更新一个时,您也隐式更新其他数据结构的引用.这几乎是副作用和杂质的定义.我知道这完全违背了Haskell范式,我并不期望Haskell以这种方式工作.

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

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

作为参考,这个问题扩展了我在以下问题中讨论的一些问题:

相同数据的多个查找结构:内存重复？

Haskell中模拟对象的身份

编辑

我想到的一个解决方案:不要在主状态中维护每个查找结构的副本.只保留一个存在的所有人的列表,这是我们更新人员时唯一需要更新的事项.每次你需要通过邮政编码进行查询时,将所有人员的列表传递给一个生成有效的by-zip-code数据结构的函数.然后对结果执行查找.

我不知道这是否有效.如果它导致CPU在每次使用时实际重新计算查找结构,则这是不可接受的.但我知道Haskell有时可以避免重新评估相同的表达式.不幸的是,在这种情况下我仍然没有想到.所以我不知道这种方法是否可行.

换句话说:我可以编写我的函数,就好像他们每次都在计算查询一样,实际上GHC会在底层数据没有改变的情况下优化它吗？因为那将是我上面提到的问题的一个非常优雅的解决方案.

Answer 1

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

• mm_freak_推荐Data.IxSet.
• donri推荐Data.Store,据说提供镜片.

您可以创建一个包含查找表的数据结构,以及一个Vector实际Person的数据结构.查找表将为您提供一个Int或一个Ints 列表(而不是一个Person或一个Persons 列表),它们是索引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您将编写的便捷函数修改a时,这些函数将为您更新所有查找表,返回PersonStuff包含所有相关数据的新函数.这使得具有快速查找的纯数据结构成为可能.

您可以使这样的函数updatePeopleWithFirstName :: Name -> (Person -> Person) -> PersonStuff -> PersonStuff获得具有名字的所有人,Person -> Person对每个人应用a ,修改其中的条目Vector,并使用这些update函数来更新所有lookupTable.