Map runSTArray над списком STArrays?

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

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

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

Пока все хорошо. Я могу проверить n -th матрицу (типа 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) и как я мог оценить массивы в списке?

Ответы

Ответ 1

Это неудачное следствие трюка типа, который делает 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.

Ответ 2

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

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

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

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

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