为查询索引Haskell数据结构

Question

我有一个Data.Vector的Dog记录,每个标识House中说狗的生活.我需要一个查找例程来查找住在房子里的所有狗,模糊地如下,但我需要不断的时间查找,这是第一个版本无法提供的.

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

据我所知,优化Haskell代码的一个中心规则是编译器只在封闭lambda表达式内部计算每个表达式.因此,我必须在绑定之前dogs为dogs_by_houses dogs表达式内部的特定内容构建一个查找表h,是吗？

我认为这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才有意义.

使用a MVector而create不是折叠返回修改的不可变向量有什么大的优势吗？我所有尝试使用MVector并且create迄今为止所有尝试都必须不那么简洁,不同层次的dos或fold (>>)类似构造或其他.我认为dbh即使没有明确给出,编译器也应该简单地构建MVector.

这个算法是不可能用列表实现的？你偶尔会看到人们建立懒惰的素数列表,然后选择第n个素数primes !! 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

我会建立表

Vec.accumulate (:) (Vec.replicate maxHouse []) 
  (Vec.map (\ d -> (dog_house d, d)) dogs)

肯定会分配最多一个中间向量,我怀疑它根本不足以分配任何中间向量.

Answer 2

我曾经遇到过一个令人讨厌的陷阱做这样的事情.我使用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

我想你必须做同样的事情.