arrays - Haskell 中的数组

Question

如何使用构造函数数组在 haskell 中创建数组？我的意思是，它会创建第一个元素等等吗？在那种情况下，它如何读取关联列表？

例如，如果我们考虑以下两个程序:-

ar :: Int->(Array Int Int)
ar n = array (0,(n-1)) (((n-1),1):[(i,((ar n)!(i+1))) | i<-[0..(n-2)]])

ar :: Int->(Array Int Int)
ar n = array (0,(n-1)) ((0,1):[(i,((ar n)!(i-1))) | i<-[1..(n-1)]])

这两个会有不同的时间复杂度吗？

Answer 1

这取决于实现，但在合理的实现中，两者具有相同的复杂性(数组大小呈线性)。

GHC的数组实现中，如果我们看代码

array (l,u) ies
    = let n = safeRangeSize (l,u)
      in unsafeArray' (l,u) n
                      [(safeIndex (l,u) n i, e) | (i, e) <- ies]

{-# INLINE unsafeArray' #-}
unsafeArray' :: Ix i => (i,i) -> Int -> [(Int, e)] -> Array i e
unsafeArray' (l,u) n@(I# n#) ies = runST (ST $ \s1# ->
    case newArray# n# arrEleBottom s1# of
        (# s2#, marr# #) ->
            foldr (fill marr#) (done l u n marr#) ies s2#)

{-# INLINE fill #-}
fill :: MutableArray# s e -> (Int, e) -> STRep s a -> STRep s a
-- NB: put the \s after the "=" so that 'fill' 
--     inlines when applied to three args 
fill marr# (I# i#, e) next 
 = \s1# -> case writeArray# marr# i# e s1# of 
             s2# -> next s2# 

我们可以看到，首先为数组分配了一 block 新的内存，然后依次填充arrEleBottom。 (这是一个带有消息“未定义数组元素”的 error 调用)，然后列表中提供的元素按照它们在列表中出现的顺序写入相应的索引。

通常，由于它是一个装箱数组，因此在构造时写入数组的是一个 thunk，它指定如何在需要时计算该值(明确指定的值，如示例中的文字 1，将导致一个指向写入数组的值的直接指针)。

当强制评估这种 thunk 时，它也可能强制评估数组中的进一步 thunk - 如果 thunk 引用其他数组元素，就像这里一样。在这里的具体示例中，强制任何 thunk 会导致稍后强制所有 thunk。在数组的前面，直到到达不引用另一个数组元素的条目的末尾。在第一个示例中，如果强制的第一个数组元素是索引 0 处的元素，则构建一个与数组长度成比例的 thunk，然后将其减小，因此强制第一个数组元素的复杂度为 O(n)，然后所有进一步的元素都已经被评估，并且强制它们是 O(1)。在第二个示例中，情况是对称的，强制最后一个元素首先会产生总评估成本。如果以不同的顺序请求元素，则评估所有 thunk 的成本将分散在对不同元素的请求中，但总成本是相同的。评估任何尚未评估的 thunk 的成本与其与下一个已评估的 thunk 的距离成正比，并且包括评估其间的所有 thunk。

由于数组访问是恒定的时间(缓存效果除外，但如果您向前或向后填充数组，这些不应该有区别，如果索引是随机顺序，它们可能会产生很大的不同，但这仍然不会影响时间复杂度)，两者具有相同的复杂度。

但是请注意，您使用 ar n定义数组元素会带来分配多个数组的风险(如果在没有优化的情况下编译，GHC 会这样做 - 刚刚测试过:即使可能发生优化)。为了确保只有一个被构建，让它

ar n = result
  where
    result = array (0,n-1) (... result!index ...)