haskell - 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 执行此操作，则无需额外费用。