haskell - 在 Haskell 中提升 State monad 中的值

Question

我正在用 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
     |     ^^^^^^^^^^^^^

Answer 1

runSTUArray ... 是一个纯值，它不知道有关“外部 monad”的任何信息。 State 关心你如何使用它，你不能不透明地将它传递给 ST。

你可以做什么:

选项1:更改整个程序，将更多逻辑移至ST端。您可以使用 STRef 而不是 State:

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

不幸的是，向量只是一维的