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似乎没有任何影响.

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

Answer 1

这可能getElems是一个坏主意的结果.在这种情况下,数组完全是一​​个坏主意:

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

这个给你答案:(1,1,1).

如果你想使用数组,我建议将数组转换为a Array或UArrayfirst,然后使用elems或转换该数组assocs.如果您使用runSTArray或使用,则无需额外费用runSTUArray.