arrays - 如何在功能上而不是程序上在线性时间内 "invert"数组？

Question

假设我有一个整数数组 A 使得 A[i] = j，我想“反转它”；也就是说，创建另一个整数数组 B 使得 B[j] = i。

这对于任何语言的线性时间程序来说都是微不足道的；这是一个 Python 示例:

def invert_procedurally(A):
    B = [None] * (max(A) + 1)
    for i, j in enumerate(A):
        B[j] = i
    return B

但是，有什么方法可以功能性地(如在函数式编程中，使用 map、reduce，或类似的功能)在线性时间内？

代码可能是这样的:

def invert_functionally(A):
    # We can't modify variables in FP; we can only return a value
    return map(???, A)                                       # What goes here?

如果这不可能，那么在进行函数式编程时最好(最有效)的替代方法是什么？

Answer 1

在这种情况下，数组是可变的还是不可变的？一般来说，我希望可变案例与您的 Python 实现一样简单，也许除了类型的一些皱纹之外。我假设您对不可变场景更感兴趣。

此操作会反转索引和元素，因此了解什么构成有效数组索引并对元素施加相同的约束也很重要。 Haskell 有一个名为 Ix 的索引约束类.任何 Ix 类型都是有序的并且有一个 range实现从一个指定索引到另一个索引的有序索引列表。我认为这个 Haskell 实现可以满足您的需求。

import Data.Array.IArray

invertArray :: (Ix x) => Array x x -> Array x x
invertArray arr = listArray (low,high) newElems
  where oldElems = elems arr
        newElems = indices arr
        low = minimum oldElems
        high = maximum oldElems

引擎盖下listArray uses zipWith and range将指定范围内的索引关联到列出的元素。这部分应该是线性时间，从数组中提取元素和索引的一次性操作也是如此。

只要输入数组索引和元素的集合不同，一些元素就会未定义，无论好坏，它比 Python 的 None 爆炸得更快。例如，我相信您可以通过在 Maybe monad 上实现新的 Ix a 实例来克服 undefined 问题。

快速旁注:查看 Haskell 98 Library Report 中的 invPerm 示例.它的作用类似于 invertArray，但预先假定输入数组的元素是其索引的排列。