在 Haskell 中提升 State monad 中的值

Question

我正在 Haskell 中写一个数独 generator/solver 作为学习练习。

我的 solve 函数接受一个 UArray 但 return 接受一个 State Int (UArray ...) 这样它也可以 return 它找到的最大难度级别解决.

这是我目前的功能（仍处于非常实验性的早期阶段）：

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
     |     ^^^^^^^^^^^^^

Answer 1

solve grid 的形式为 return $ ...。这意味着 State Int (UArray (Int, Int) Cell) 只是特化的 Monad m => m (UArray (Int, Int) Cell) - ... 无法访问这个特定 monad 的特性，它只是一个 UArray (Int, Int) Cell 值，你 return.

Answer 2

runSTUArray ... 是一个纯值，它对 "outer monad" 一无所知。 State 关心你如何使用它，你不能不透明地将它传递给 ST。

你可以做什么：

Option1：改变整个程序，将更多的逻辑移到ST端。你将使用 STRef 而不是 State：

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

Option2: 手动解压传给ST，再取回来显式放。但是有并发症。 runSTUArray 不允许与数组一起获取另一个值。我不知道如何使用当前数组函数安全地完成它。不安全你可以 re-implement 更好 runSTUArray 可以传递另一个值。您还可以添加假单元格并在那里对新状态进行编码。

vector 包中存在导出另一个值的方法，有（在新版本中）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

矢量只有 one-dimensional，不幸的是

Answer 3

在将 State monad 更改为元组 (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)

这适用于我的应用程序。

在 Haskell 中提升 State monad 中的值

Lifting a value in the State monad in Haskell

haskell

state-monad

lifting