STArray 和堆栈溢出

Question

我正在努力理解为什么以下尝试在 STArray 中查找最小元素会导致在使用 ghc（7.4.1，无论 -O 级别如何）编译时堆栈空间溢出，但在ghci中工作正常：

import Control.Monad
import Control.Monad.ST
import Control.Applicative
import Data.Array.ST
n = 1000 :: Int
minElem = runST $ do
  arr <- newArray ((1,1),(n,n)) 0 :: ST s (STArray s (Int,Int) Int)
  let ixs = [(i,j) | i <- [1..n], j <- [1..n]]
  forM_ ixs $ (i,j) -> writeArray arr (i,j) (i*j `mod` 7927)
--  readArray arr (34,56)  -- this works OK
--  findMin1 arr           -- stackoverflows when compiled
  findMin2 arr           -- stackoverflows when compiled
findMin1 arr = do
  es <- getElems arr
  return $ minimum es
findMin2 arr = do
  e11 <- readArray arr (1,1) 
  foldM (m ij -> min m <$> readArray arr ij) e11 ixs
      where ixs = [(i,j) | i <- [1..n], j <- [1..n]]
main = print minElem

注意：切换到STUArray或ST.Lazy似乎没有任何效果。

但主要问题是：在ST内部对大STArray实施这种"折叠式"操作的正确方法是什么？

Answer 1

这可能是getElems是个坏主意的结果。 在这种情况下，数组完全是一个坏主意：

minimum (zipWith (x y -> (x, y, mod (x*y) 7927)) [1..1000] [1..1000])

这个马上给你答案：（1,1,1）。

如果您无论如何都想使用数组，我建议先将数组转换为Array或UArray，然后在该数组上使用elems或assocs。 如果您使用 runSTArray 或 runSTUArray 执行此操作，这不会产生额外费用。

Answer 2

findMin1 中最大的问题是getElems：

getElems :: (MArray a e m, Ix i) => a i e -> m [e]
getElems marr = do
  (_l, _u) <- getBounds marr      -- Hmm, why is that there?
  n <- getNumElements marr
  sequence [unsafeRead marr i | i <- [0 .. n - 1]]

在长列表中使用 sequence 是 monads 中堆栈溢出的常见原因，因为 monad (>>=)不够懒惰，因为

sequence ms = foldr k (return []) ms
        where
          k m m' = do { x <- m; xs <- m'; return (x:xs) }

然后，它必须构建一个与列表长度成比例的大小。 getElems可以使用Control.Monad.ST.Lazy，但随后填充数组

forM_ ixs $ (i,j) -> writeArray arr (i,j) (i*j `mod` 7927)

产生溢出堆栈的巨大混乱。对于严格的ST变体，您需要将getElems替换为无需sequence即可构建列表的东西，或者 - 更好的是 - 在不创建元素列表的情况下计算最小值。对于懒惰的ST变体，您需要确保数组的填充不会产生巨大的混乱，例如通过强制writeArray调用的结果

let fill i j
      | i > n     = return ()
      | j > n     = fill (i+1) 1
      | otherwise = do
          () <- writeArray arr (i,j) $ (i*j `mod` 7927)
          fill i (j+1)
() <- fill 1 1

findMin2的问题是

foldM (m ij -> min m <$> readArray arr ij) e11 ixs

在m中很懒惰，所以它构建了一个巨大的thunk来计算最小值。您可以通过使用 seq（或 bang-pattern）使其严格m来轻松解决此问题。

但主要问题是：在ST内部对大STArray实施这种"折叠式"操作的正确方法是什么？

通常，你会使用严格的ST变体（对于像Int这样的类型，你几乎肯定应该使用STUArray s而不是STArray s）。那么最重要的规则是你的函数足够严格。findMin2的结构还可以，实现只是太懒了。

如果性能很重要，您通常必须避免使用通用的高阶函数（如 foldM 并编写自己的循环，以避免分配列表并完全按照手头问题的要求控制严格性。

Answer 3

问题是最小值是一个非严格的折叠，所以它会导致混乱的积累。 使用（折叠分钟）。

现在我们添加一堆要忽略的措辞，因为 stackoverflow 已经变得毫无价值，不再允许发布简单的答案。