algorithm - 为查询索引 Haskell 数据结构

Question

我有一个 Data.Vector 的 Dog 记录，每个记录都标识了所述狗居住的 House 。我需要一个查找例程来查找住在一个房子里的所有狗，如下所示，但我需要持续时间查找，这是第一个版本无法提供的。

dogs_by_houses dogs h = [ d | d <- Vec.toList dogs, h == house d ]

据我所知，优化 Haskell 代码的核心规则是编译器只计算每个表达式在其封闭的 lambda 表达式中一次。因此，在绑定(bind) h 之前，我必须在 dogs_by_houses dogs 表达式中为这个特定的 dogs 构建一个查找表，是吗？

我认为 Data.Vector 是完成此任务的最佳工具，尽管显然您不能像压缩 C++ 向量那样缩小它们。我将大致按如下方式实现:

dogs_by_houses :: Vec.Vector Dog -> Int -> [Dog]
dogs_by_houses dogs = let {
        dog_house = house_id . house ;
        v0 = Vec.replicate (maximum . map dog_house $ Vec.toList dogs) [] ;
        f v d = let { h = dog_house d } in v // [(h,d:v!h)] ;
        dbh = Vec.foldl' f v0 dogs
   } in (dbh !)

这里有什么愚蠢的优化吗？我认为像 dbh 这样的变量上的严格标记不会有太大帮助，因为根据定义 dogs 必须在 dbh 有意义之前遍历。

使用 MVector 和 create 而不是折叠返回修改后的不可变向量有什么大的优势吗？到目前为止，我所有使用 MVector 和 create 的尝试都没有那么简洁，do 或 fold (>>) 类似构造或其他任何东西。我认为编译器应该简单地构建 dbh，即使没有明确给出 MVector。

这个算法不可能用列表来实现吗？您偶尔会看到人们构建懒惰的无限素数列表，然后使用 primes 选择第 n 个素数! n.我假设每次以这种方式检索第 n 个素数时都需要遍历列表中的前 n 个素数。相反，我注意到 GHC 将字符串存储为 C 字符串，而不是列表。编译器是否会简单地将已知列表元素表示为一个数组，而不是为每个元素重新遍历列表？

更新:

我已经采用 Paul Johnson 和 Louis Wasserman 的答案来构建一个函数来以这种方式对任意向量进行索引，因为我必须基于几个不同的索引函数来这样做。

vector_indexer idx vec = \i -> (Vec.!) t i
  where m = maximum $ map idx $ Vec.toList vec
        t = Vec.accumulate (flip (:)) (Vec.replicate m []) 
               $ Vec.map (\v -> (idx v, v)) vec
dogs_by_houses = vector_indexer (house_id . house)

我还没有对此进行分析，但最终。我希望必须编写 my_d_by_h = dogs_by_houses my_dogs 并调用 my_d_by_h 才能从索引中受益。

Answer 1

我曾经在做这样的事情时遇到了一个令人讨厌的陷阱。我使用 Data.Map.Map 作为查找表，但原理是一样的。我的函数获取了一个键值对列表，构造了一个 Map，并返回了查找函数。它是这样的:

makeTable :: [(Key, Value)] -> Key -> Value
makeTable pairs = ((fromList pairs) !)

对我来说很明显我可以写类似的东西

myTable = makeTable [("foo", fooValue), ("bar", barValue)  ... and so on]

然后我可以通过说来进行 O(log N) 查找

v = myTable "foo"

然而，GHC 实际上所做的是为每次调用从列表中重建整个 map 。当您以这种方式创建部分应用程序时，GHC 不会尝试找出它可以从其获得的参数中派生出哪些值，它只是存储原始参数并为每次调用执行整个函数。完全合理的行为，但不是我想要的。

我不得不写的是:

makeTable pairs = \k -> table ! k
   where table = fromList pairs

我想您将不得不做同样的事情。