Haskell在O（1）时间获得Ix范围的中间值

我在Haskell中玩this代码kata，我在主题中遇到了这个问题。Haskell在O（1）时间获得Ix范围的中间值

查找索引为单个数值的数组的中点很简单，但Haskell的数组索引可以是Ix类型类的任何实例，包括例如元组（卡，Int，Word，Card）是Ix的一个实例，但不是Num的一个实例。

获取数组中点的一种方法是查询其长度，查询索引列表，并将该列表的一半放下，但这需要O（n）时间。

有没有人知道一种方法来索引做它在恒定时间？我觉得应该有一个，因为Ix范围应该用整数范围进行投射。

来源

2010-09-08 Alex R

如果真的存在一个双射，那么为什么不映射到整数，计算中点，然后采取逆映射回它的索引类型？我不知道什么样的机制会允许Haskell这样做，但似乎有可能？ – Gian 2010-09-08 14:28:24

“Ix”类中的函数'index'是bijection的一部分，将索引映射到整数，但另一个缺失，据我所知。 – yatima2975 2010-09-08 14:51:13

Ix typeclass仅要求从i类型的值注入到Int的值。 index与range在一起可以给我们逆映射：

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

正如你可以看到index'线性时间至少评估。我们也无法知道range b的工作时间。它以用户在实例定义中定义的方式进行评估。所以在你的情况下需要优化（获得一个数组的中点）可以发生当且仅当我们有某种类型的恒定时间工作的index'。由于Ix typeclass没有给我们提供从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

来源

2010-09-08 15:40:08 fizruk

Haskell在O（1）时间获得Ix范围的中间值

回答

相关问题