Существует два очевидных "идиоматических" способа выполнения вложенных циклов в Haskell: использование монады списка или использование forM_
для замены традиционного fors
. Я установил контрольный показатель, чтобы определить, скомпилированы ли они для жестких циклов:
import Control.Monad.Loop
import Control.Monad.Primitive
import Control.Monad
import Control.Monad.IO.Class
import qualified Data.Vector.Unboxed.Mutable as MV
import qualified Data.Vector.Unboxed as V
times = 100000
side = 100
-- Using `forM_` to replace traditional fors
test_a mvec =
forM_ [0..times-1] $ \ n -> do
forM_ [0..side-1] $ \ y -> do
forM_ [0..side-1] $ \ x -> do
MV.write mvec (y*side+x) 1
-- Using the list monad to replace traditional forms
test_b mvec = sequence_ $ do
n <- [0..times-1]
y <- [0..side-1]
x <- [0..side-1]
return $ MV.write mvec (y*side+x) 1
main = do
let vec = V.generate (side*side) (const 0)
mvec <- V.unsafeThaw vec :: IO (MV.MVector (PrimState IO) Int)
-- test_a mvec
-- test_b mvec
vec' <- V.unsafeFreeze mvec :: IO (V.Vector Int)
print $ V.sum vec'
Этот тест создает вектор 100x100, записывает 1 в каждый индекс с помощью вложенного цикла и повторяет это 100k раз. Компилируя те, которые имеют только ghc -O2 test.hs -o test
(версия ghc 7.8.4), результаты: 3.853s
для версии forM_
и 10.460s
для list monad
. Чтобы предоставить ссылку, я также запрограммировал этот тест на JavaScript:
var side = 100;
var times = 100000;
var vec = [];
for (var i=0; i<side*side; ++i)
vec.push(0);
for (var n=0; n<times; ++n)
for (var y=0; y<side; ++y)
for (var x=0; x<side; ++x)
vec[x+y*side] = 1;
var s = 0;
for (var i=0; i<side*side; ++i)
s += vec[i];
console.log(s);
Эта эквивалентная программа JavaScript принимает 1s
, что приводит к избиению нераспознанных векторов Haskell, что является необычным, предполагая, что Haskell не запускает цикл в постоянном пространстве, а вместо этого выполняет выделение. Затем я нашел библиотеку, которая утверждает, что предоставляет жесткие циклы, гарантированные типом Control.Monad.Loop
:
-- Using `for` from Control.Monad.Loop
test_c mvec = exec_ $ do
n <- for 0 (< times) (+ 1)
x <- for 0 (< side) (+ 1)
y <- for 0 (< side) (+ 1)
liftIO (MV.write mvec (y*side+x) 1)
Что работает в 1s
. Эта библиотека не очень используется и далека от идиоматической, хотя, так что каков идиоматический способ быстрого вычисления двумерных вычислений с постоянным пространством? (Обратите внимание, что это не относится к REPA, поскольку я хочу для выполнения произвольных операций ввода-вывода в сетке.)