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           -- stackrus when compiled
  findMin2 arr           -- stackrus 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

Большая проблема в 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 в длинном списке является распространенной причиной переполнения стека в монадах, чьи (>>=) не достаточно ленив, так как

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Таким образом, он создает огромный массив, чтобы вычислить минимум. Вы можете легко исправить это, используя seq (или шаблон взрыва), чтобы сделать его строгим в m,

Однако главный вопрос: как правильно реализовать такую ​​"складную" операцию на больших STArray пока внутри ST?

Как правило, вы будете использовать строгий ST вариант (и для типов, как Int, вы должны почти наверняка использовать STUArrayс вместо STArrayс). Тогда самое важное правило - ваши функции должны быть достаточно строгими. Структура findMin2 все в порядке, реализация просто слишком ленива.

Если производительность имеет значение, вам часто придется избегать общих функций высшего порядка, таких как foldM и пишите свои собственные циклы, чтобы избежать размещения списков и контролировать строгость в точности так, как этого требует проблема.

Answer 2

Это, вероятно, результат 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 3

Проблема в том, что минимум - это не строгий фолд, поэтому он вызывает наращивание thunk. Используйте (сложите мин).

Теперь мы добавляем кучу слов, чтобы их игнорировать, потому что stackru оказался бесполезным и больше не позволяет публиковать прямой ответ.