карта запуска STArray над списком STArrays? - PullRequest
Новая
       28

карта запуска STArray над списком STArrays?

11 голосов
/ 28 ноября 2011

У меня есть функция, которая рекурсивно создает плоский список матриц из дерева, которые должны быть изменяемыми, так как их элементы часто обновляются во время их создания.До сих пор я придумал рекурсивное решение, которое имеет подпись: 

doAll :: .. -> [ST s (STArray s (Int, Int) Int)]

Причина, по которой я не возвращаю [UArray (Int,Int) Int] напрямую, заключается в том, что doAll вызывается рекурсивно, изменяет элементы матриц всписок и добавляет новые матрицы.Я не хочу заморозить и разморозить матрицы без необходимости.

Пока все хорошо.Я могу проверить n -ую матрицу (типа Array (Int, Int) Int) в ghci

runSTArray (matrices !! 0)
runSTArray (matrices !! 1)

и действительно получаю правильные результаты для своего алгоритма.Однако я не нашел способа сопоставить runSTUArray со списком, который возвращается doAll: 

map (runSTArray) matrices

Couldn't match expected type `forall s. ST s (STArray s i0 e0)'
            with actual type `ST s0 (STArray s0 (Int, Int) Int)'

Та же проблема возникает, если я пытаюсь рекурсивно оценивать список или пытаюсьоценивать отдельные элементы, заключенные в функцию

Может кто-нибудь объяснить, что происходит (я действительно не понимал значения ключевого слова forall) и как я могу оценить массивы в списке?

Ответы [ 2 ]

10 голосов
/ 28 ноября 2011

Это печальное следствие трюка с типом, который делает ST безопасным.Во-первых, вам нужно знать, как работает ST.Единственный способ перейти от монады ST к чистому коду - это использовать функцию runST или другие функции, построенные на ней, например runSTArray.Это все в форме forall s..Это означает, что для построения массива из STArray компилятор должен иметь возможность определить, что он может заменить любой тип, который ему нравится, на переменную типа s внутри runST.

Теперь рассмотримфункция map :: (a -> b) -> [a] -> [b].Это показывает, что каждый элемент в списке должен иметь точно такой же тип (a), а следовательно, и тот же s.Но это дополнительное ограничение нарушает тип runSTArray, который объявляет, что компилятор должен иметь возможность свободно подставлять другие значения для s.

Вы можете обойти это, определив новую функцию, чтобы сначала заморозитьмассивы внутри монады ST, затем запустите получившееся действие ST: 

runSTArrays :: Ix ix => (forall s. [ST s (STArray s ix a)]) -> [Array ix a]
runSTArrays arrayList = runST $ (sequence arrayList >>= mapM freeze)

Обратите внимание, что forall требует расширения RankNTypes.

4 голосов
/ 28 ноября 2011

Вы только что отскочили от ограничений системы типов.

RunSTArray имеет более высокий рейтинг типа.Вы должны передать ему ST-действие, чья переменная типа состояния уникальна.Тем не менее, в Haskell, как правило, невозможно иметь такие значения в списках.

Все это умная схема, которая гарантирует, что значения, которые вы производите в действии ST, не могут оттуда сбежать.Это значит, что ваш дизайн каким-то образом поврежден.

Одно предложение: вы не можете обработать значения в другом действии ST, например 

sequence [ ... your ST s (STArray s x) ...] >>= processing
  where
     processing :: [STArray s x] -> ST s (your results)
...