Поднятие значения в монаде State в Haskell

Я пишу генератор/решатель судоку на Haskell в качестве учебного упражнения.

Моя функция solve принимает UArray, но возвращает State Int (UArray ...), так что она также может вернуть максимальный уровень сложности, найденный при решении.

Это моя функция до сих пор (все еще на очень ранней экспериментальной стадии):

import Control.Monad.State       (State, put)
import Control.Monad.Trans.Class (lift)
import Data.Array.MArray         (thaw)
import Data.Array.ST             (runSTUArray)
import Data.Array.Unboxed        (UArray)

-- ...

type Cell = Word16

solve :: UArray (Int, Int) Cell -> State Int (UArray (Int, Int) Cell)
solve grid = do
  return $ runSTUArray $ do
    arr <- thaw grid
    lift $ put 42
    return arr

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

  • Couldn't match kind ‘*’ with ‘* -> *’
    When matching the kind of ‘ST’
  • In a stmt of a 'do' block: lift $ put 42
    In the second argument of ‘($)’, namely
      ‘do arr <- thaw grid
          lift $ put 42
          return arr’
    In the second argument of ‘($)’, namely
      ‘runSTUArray
         $ do arr <- thaw grid
              lift $ put 42
              return arr’
     |
 128 |     lift $ put 42
     |     ^^^^^^^^^^^^^

haskell state-monad lifting
person Ralph    schedule 18.03.2018    source источник
comment
Кажется, я вижу свою собственную проблему, но понятия не имею, как ее решить. Монада ST не встроена в преобразователь StateT, поэтому операцию put нельзя поднять.   -  person Ralph    schedule 18.03.2018

Ответы (3)


arrow_upward
1
arrow_downward

runSTUArray ... — чистое значение, оно ничего не знает о «внешней монаде». И State заботится о том, как вы его используете, вы не можете непрозрачно передать его в ST.

Что вы можете сделать:

Вариант 1: изменить всю программу, чтобы переместить больше логики на сторону ST. Тогда вместо State вы должны использовать STRef:

solve :: ST s (STRef Int) -> ST s (UArray (Int, Int) Cell) -> ST s ()
...

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

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

import Control.Monad.State (State, put, get)
import Data.Word (Word16)

import qualified Data.Vector.Unboxed as DVU

type Cell = Word16

solve :: DVU.Vector Cell -> State Int (DVU.Vector Cell)
solve grid = do
  oldState <- get
  let (newState, newGrid) = DVU.createT (do
          arr <- DVU.thaw grid
          pure (oldState + 42, arr))
  put newState
  pure newGrid

векторы только одномерные, к сожалению

person max630    schedule 19.03.2018
comment
FYI stackoverflow.com/a/49356530/2303202 выглядит возможным с массивами - person max630; 19.03.2018
comment
Нет, подпись ((forall s . ST s a) -> b) не соответствует случаю runSTUArray, потому что a имеет в своих параметрах s. Таким образом, связанный трюк не поможет - если вы попытаетесь передать изменяемый массив другому экстрактору ST, он не будет скомпилирован, потому что переменная типа «s» выйдет из своей области видимости. - person max630; 20.03.2018

arrow_upward
0
arrow_downward

solve grid имеет форму return $ .... Это означает, что State Int (UArray (Int, Int) Cell) является просто специализированным Monad m => m (UArray (Int, Int) Cell) - ... не имеет доступа к функциям этой конкретной монады, это просто значение UArray (Int, Int) Cell, которое вы возвращаете.

person Gurkenglas    schedule 18.03.2018
comment
Если я перемещу put 42 в строку над return $ runSTUArray $ do, он скомпилируется и запустится правильно. Я просто пытаюсь понять, как установить состояние во внешней монаде State изнутри монады ST. - person Ralph; 18.03.2018

arrow_upward
0
arrow_downward

Я смог получить небольшую вариацию для компиляции и запуска после изменения монады State на кортеж (Int, Grid):

import Control.Monad.ST    (ST, runST)
import Data.Array.MArray   (freeze, thaw, writeArray)
import Data.Array.ST       (STUArray)
import Data.Array.Unboxed  (UArray)
import Data.Word (Word16)

type Cell = Word16
type Grid = UArray (Int, Int) Cell

solve :: Grid -> (Int, Grid)
solve grid =
  runST $ do
    mut <- thaw grid :: ST s (STUArray s (Int, Int) Cell)
    writeArray mut (0, 0) 0 -- test that I can actually write
    frozen <- freeze mut
    return (42, frozen)

Это отлично работает для моего приложения.

person Ralph    schedule 01.06.2018