我对纯函数通常是 O(log n)的说法持怀疑态度。另请参阅提出该主张的 Edward Kmett 的回答。虽然这可能适用于理论上的随机可变数组访问，但是当对可重复结构（即不是随机的）进行适当研究时，随机可变数组访问可能不是大多数算法所需要的。我认为 Edward Kmett 在写“利用更新的局部性”时提到了这一点。
我认为 O(1) 在理论上可能在 n-queens 算法的纯函数版本中，通过为 DiffArray 添加一个撤消方法，该方法要求回顾差异以删除重复项并避免重放它们。
如果我对回溯 n-queens 算法运行方式的理解是正确的，那么 DiffArray 导致的减速是因为保留了不必要的差异。
在抽象中，“DiffArray”（不一定是 Haskell 的）具有（或可能具有）一个 set 元素方法，该方法返回数组的新副本并存储与原始副本的差异记录，包括指向新更改副本的指针。当原始副本需要访问一个元素时，必须反向重播此差异列表以撤消对当前副本副本的更改。请注意，在重放之前，这个单链表甚至必须走到最后，这会产生开销。
想象一下，这些被存储为一个双链表，并且有一个如下的撤消操作。
从抽象的概念层面来看，回溯 n-queens 算法所做的是对一些布尔数组进行递归操作，在每个递归级别上，在这些数组中递增地向前移动皇后的位置。看这个动画。
仅在我的脑海中解决这个问题，我想象 DiffArray 如此慢的原因是因为当皇后从一个位置移动到另一个位置时，原始位置的布尔标志设置回 false 并设置新位置为真，这些差异被记录下来，但它们是不必要的，因为当反向重放时，数组最终会得到与重放开始之前相同的值。因此，不需要使用 set 操作将其设置回 false，而是需要调用 undo 方法，可选地使用输入参数告诉 DiffArray 在上述差异的双链表中搜索什么“撤消到”值。如果在双链表的差异记录中找到该“撤消到”值，
这样做的目的是在回溯时删除整个数组的不必要复制。与算法的命令式版本相比，仍然有一些额外的开销，用于添加和撤消差异记录的添加，但这可能更接近于恒定时间，即 O(1)。
如果我正确理解了n-queen算法，undo操作的回溯只有一个，所以没有walk。因此，在移动皇后位置时甚至不需要存储设置元素的差异，因为它会在访问旧副本之前被撤消。我们只需要一种安全地表达这种类型的方法，这很容易做到，但我将把它作为练习留给读者，因为这篇文章已经太长了。
更新：我还没有为整个算法编写代码，但在我的脑海中，n-queens 可以在每个迭代行上实现，在以下对角线数组上折叠，其中每个元素是三元组：（它被占用的行索引或无，行索引数组与左右对角线相交，行索引数组与左右对角线相交）。可以使用递归或行索引数组的折叠来迭代行（折叠进行递归）。
下面是我设想的数据结构的接口。下面的语法是 Copute，但我认为它与 Scala 足够接近，您可以理解其意图。
请注意，如果 DiffArray 是多线程的，任何实现都会非常缓慢，但 n-queens 回溯算法不需要 DiffArray 是多线程的。感谢 Edward Kmett 在此答案的评论中指出这一点。
interface Array[T]
{
setElement : Int -> T -> Array[T] // Return copy with changed element.
setElement : Int -> Maybe[T] -> Array[T]
array : () -> Maybe[DiffArray[T]]// Return copy with the DiffArray interface, or None if first called setElement() before array().
}
// An immutable array, typically constructed with Array().
//
// If first called setElement() before array(), setElement doesn't store differences,
// array will return None, and thus setElement is as fast as a mutable imperative array.
//
// Else setElement stores differences, thus setElement is O(1) but with a constant extra overhead.
// And if setElement has been called, getElement incurs an up to O(n) sequential time complexity,
// because a copy must be made and the differences must be applied to the copy.
// The algorithm is described here:
// http://stackoverflow.com/questions/1255018/n-queens-in-haskell-without-list-traversal/7194832#7194832
// Similar to Haskell's implementation:
// http://www.haskell.org/haskellwiki/Arrays#DiffArray_.28module_Data.Array.Diff.29
// http://www.haskell.org/pipermail/glasgow-haskell-users/2003-November/005939.html
//
// If a multithreaded implementation is used, it can be extremely slow,
// because there is a race condition on every method, which requires internal critical sections.
interface DiffArray[T] inherits Array[T]
{
unset : () -> Array[T] // Return copy with the previous setElement() undone, and its difference removed.
getElement : Int -> Maybe[T] // Return the the element, or None if element is not set.
}
// An immutable array, typically constructed with Array( ... ) or Array().array.
更新：我正在研究Scala 实现，与我上面建议的相比，它具有改进的界面。我还解释了折叠优化如何接近与可变数组相同的恒定开销。