首页 文章

数据网格的Haskell可变数组

提问于
浏览
0

我'm trying to write a sudoku generator/solver in Haskell as a learning exercise, but I'm在 ST monad中遇到难以产生可变数组的问题 .

我的 parse 函数的输入将是 String ,包含数字 19 和占位符( .-0 )的81个字符 .

这是我写的函数,但它不会编译,我无法弄清楚我需要什么类型:

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网格的不可变表示 .

我怎样才能解决这个问题?

1 回答

  • 1

    您正在使用 runSTUArray ,这意味着有 UArray (Int, Int) Cell 的意图 . 你不能这样: UArray 仅适用于少数几种元素类型 . 你可以使用普通的 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 = _
    

    您可以在其中填充第一个和第二个 _ ,其功能分别为 Word16Bool 解构和构造单元格,以创建一个记录模式同义词,它就像普通记录构造函数一样,但实际上并不创建新的类型 .

相关问题