ekmett / guanxi

Relational programming in Haskell. Mostly developed on twitch.
http://twitch.tv/ekmett
Other
253 stars 29 forks source link

Interpreting solutions from DLX? #17

Closed identicalsnowflake closed 5 years ago

identicalsnowflake commented 5 years ago

I'm trying to examine solutions (rather than just the cardinality of the solution set) from the DLX module and I don't understand the results:

module Main where

import Control.Lens
import Control.Monad.ST
import Cover.DLX
import Data.Foldable
import Data.STRef

example :: [ [ Int ] ]
example = runST $ do

  x <- newCover_

  _ <- addItems x 3

  addRow x [ 1 , 0 , 0 ] -- called 3?
  addRow x [ 0 , 1 , 1 ] -- called 4?
  addRow x [ 0 , 1 , 1 ] -- called 6?
  addRow x [ 1 , 0 , 0 ] -- called 8?

  solutions <- newSTRef (mempty :: [ [ Int ] ])

  solve x (\s -> modifySTRef solutions ((:) s))

  readSTRef solutions

  where
    addRow c xs = addOption c
      $ ifoldr (\i (x :: Int) a -> if x == 0 then a else i : a) mempty xs

main :: IO ()
main = do
  traverse_ print $ example

Four solutions are printed ([8,6], [8,4], [3,6], and [3,4]), but I'm not sure where it's coming up with those row names -- I expected the solutions [0,1], [0,2], [3,1], and [3,2].

Am I interpreting these results incorrectly, or is something being garbled somewhere between the C API and the Haskell layer?

identicalsnowflake commented 5 years ago

Ah, I see - addOption returns a name as Option, which is an internal alias for Word32. Makes sense.

Might be better to have addOption :: HasCover m s => s -> [Int] -> m Int or export the Option alias and have solve :: HasCover m s => s -> ([ Option ] -> m ()) -> m (), as currently these two seem to refer to the same piece of data by different types.