arrays - 在 Haskell 中以 O(1) 时间获得 Ix 范围的中间

Question

我在 Haskell 中玩弄这个代码 kata，我遇到了这个主题中的问题。

找到索引为单个数值的数组的中点很简单，但 Haskell 的数组索引可以是 Ix 类型类的任何实例，包括例如元组 (Int, Word, Card)，其中 card 是Ix 但不是 Num。

获取数组中点的一种方法是查询其长度，查询索引列表，然后删除该列表的一半，但这需要 O(n) 时间。

有谁知道一种在恒定时间内索引的方法？我觉得应该有一个，因为 Ix 范围应该与整数范围双射。

Answer 1

Ixtypeclass 只需要从 type 的值注入i到Int. index一起range可以给我们逆映射：

index' :: (Ix i) => (i, i) -> Int -> i
index' b x = range b ! x

如您所见index'，至少在线性时间内进行评估。我们也无法知道工作多长时间range b。它以用户在实例定义中定义的方式进行评估。因此，当且仅当我们有某种index'在恒定时间内起作用的情况下，您的情况所需的优化（获取数组的中点）才能发生。由于Ixtypeclass 没有给我们从Intto 的常量时间映射i，我们应该询问用户。考虑下一个代码：

midpoint :: (Ix j) => (Int -> j) -> Array j e -> e
midpoint f a = a ! f middle
               where middle = rangeSize (bounds a) `div` 2

现在取数组中点的复杂度取决于用户定义的复杂度f。因此，如果我们的索引类型的值i可以在恒定时间内从Int值评估，反之亦然——我们得到恒定时间的中点。

还要考虑以下ixmap功能Data.Ix：

ixmap :: (Ix i, Ix j) => (i, i) -> (i -> j) -> Array j e -> Array i e