Haskell 数独网格的可变数组

Question

我正在尝试在 Haskell 中编写数独游戏 generator/solver 作为学习练习，但我运行在 [=12= 中生成可变数组时遇到困难] 单子。

我的 parse 函数的输入将是一个 String 的 81 个字符，包含数字 1 到 9 和占位符（.，-, 或 0).

这是我写的函数，但它不会编译，我不知道我需要什么类型：

import           Control.Monad
import           Control.Monad.ST
import           Data.Array.ST
import qualified Data.Array.Unboxed as U
import           Data.Char          (digitToInt, isDigit)
import           Data.List          (zip)

data Cell = Cell
  { values   :: Word16
  , original :: Bool
  } deriving (Show)

parse input =
  runSTUArray $
  U.array ((0, 0), (8, 8)) $
  map
    (\(i, d) ->
       ( (quot i 9, mod i 9)
       , if isDigit d && d /= '0'
           then Cell {values = bit $ digitToInt d, original = True}
           else Cell {values = 2 ^ 11 - 2, original = False})) $
  zip [0 ..] input

函数的输出应该是包含单元格的可变 9 x 9 网格的不可变表示。

我该如何解决这个问题？

Answer 1

您正在使用 runSTUArray，这意味着您打算使用 UArray (Int, Int) Cell。您不能这样：UArray 仅适用于 select 少数元素类型。您可以使用正常的 Array。或者，您可以使用 type Cell = Word16 并将 Bool 塞入其中。无论如何，没有理由使用ST。 listArray 函数将执行：

import Data.Array
-- listArray :: Ix i => (i, i) -> [e] -> Array i e

parse :: String -> Array (Int, Int) Cell
parse = listArray ((0, 0), (8, 8)) . map chr2cell
  where chr2cell c | isDigit c && c /= '0' = Cell (bit $ intToDigit c) True
                   | otherwise = Cell (2^11 - 2) False

如果您选择使用UArray _ Word16，您只需稍微修改一下chr2cell。如果您使用的是最近的 GHC，您甚至可以选择：

{-# LANGUAGE PatternSynonyms, ViewPatterns #-}
type Cell = Word16
pattern Cell :: Word16 -> Bool -> Word16
pattern Cell { values, original } <- (_ -> (values, original))
  where Cell values original = _

您可以在第一个和第二个 _ 中分别填充解构和构造单元格 to/from 一个 Word16 和一个 Bool 的函数，以创建一个记录模式同义词，就像普通记录构造函数一样工作，但实际上并不创建新类型。

Haskell 数独网格的可变数组

Haskell mutable array for sudoku grid

monads

haskell

mutable