Haskell mutable array for sudoku grid

Question

I'm trying to write a sudoku generator/solver in Haskell as a learning exercise, but I'm running into difficulty producing a mutable array in the ST monad.

The input to my parse function will be a String of 81 characters containing the digits 1 through 9 and placeholders (., -, or 0).

This is the function that I wrote, but it will not compile and I can't figure out what types I need:

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

The output of the function should be an immutable representation of a mutable 9 x 9 grid containing cells.

How can I fix this?

What does it mean to have an immutable representation of something mutable? What is the "this" you are asking for help fixing? — Thomas M. DuBuisson
– Thomas M. DuBuisson, Commented Mar 17, 2018 at 22:06

HTNW · Accepted Answer · 2018-03-17 23:35:11Z

1

You are using runSTUArray, which implies the intent to have a UArray (Int, Int) Cell. You can't have this: UArray is meant only for a select few element types. You can use a normal Array. Or, you can have type Cell = Word16 and just cram the Bool into it. In any case, there is no reason to use ST. The listArray function will do:

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

If you choose to use UArray _ Word16, you simply need to modify chr2cell a bit. If you are on recent GHC, you can even opt to have:

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

where you can fill the first and second _s with functions that deconstruct and construct cells to/from a Word16 and a Bool, respectively, to create a record pattern synonym that works just like a normal record constructor but doesn't actually create a new type.

answered Mar 17, 2018 at 23:35

HTNW

29.7k2 gold badges38 silver badges63 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Ralph Over a year ago

Thanks. That is very helpful.

Collectives™ on Stack Overflow

Haskell mutable array for sudoku grid

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related