3

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?

如果这是不可能的，那么在进行函数式编程时最好（最有效）的选择是什么？

4

2 回答 2

2

一个解决方案需要map和 3 个操作：

  1. toTuples将数组视为元组列表，(i,e)其中i索引和e数组中该索引处的元素。
  2. fromTuples从元组列表中创建并加载一个数组。
  3. swap它接受一个元组(a,b)并返回(b,a)

因此，解决方案将是（在 Haskellish 表示法中）：

invert = fromTuples . map swap . toTuples
于 2013-10-10T07:35:40.223 回答
2

在这种情况下，数组是可变的还是不可变的？一般来说，我希望可变案例与您的 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使用zipWithandrange将指定范围内的索引与列出的元素相关联。那部分应该是线性时间，从数组中提取元素和索引的一次性操作也是如此。

每当输入数组索引和元素的集合不同时，一些元素将是undefined，无论好坏，它们都比 Python 的None. 例如，我相信你可以通过在 Maybe monad 上undefined实现新Ix a实例来克服这个问题。

快速旁注：查看Haskell 98 Library ReportinvPerm中的示例。它做了类似于 的事情，但预先假设输入数组的元素是其索引的排列。invertArray

于 2013-10-11T07:55:19.083 回答