在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 没有为我们提供从Int到 的恒定时间映射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