I think I discovered my first Monoid instance

29 Sep 2020

      Hi.

A common theme of some Haskell talks seems to be to motivate people to
go and hunt for instances of standard typeclasses.  As the hobbyist
Haskell programmer that I am, I kept on wondering if I would
ever find some.  It feels sort of unrealistic, or at least unlikely,
that I should suddenly start to see meaningful structure in
code just because I think I know some typeclasses.

I think I finally discovered a Monoid instance that helps to express a
concept in code pretty well.  However, unsure about the soundness of my
blundering about, I'd like to confirm (or disprove!) my findings
before I fall in love with the approach too much.

In my chess library (chessIO) I use bitboards to represent chess positions.

data QuadBitboard = QBB { black :: {-# UNPACK #-} !Word64
                        , pbq :: {-# UNPACK #-} !Word64
                        , nbk :: {-# UNPACK #-} !Word64
                        , rqk :: {-# UNPACK #-} !Word64
                        } deriving (Eq)

A quad bitboard is a space optimisation based on the observation
that a square can only be occupied by one piece.

occupied QBB{pbq, nbk, rqk} = pbq  .|.  nbk  .|.  rqk
pnr      QBB{pbq, nbk, rqk} = pbq `xor` nbk `xor` rqk
white                       = liftA2 xor occupied black
pawns                       = liftA2 (.&.) pnr pbq
knights                     = liftA2 (.&.) pnr nbk
bishops                     = liftA2 (.&.) pbq nbk
rooks                       = liftA2 (.&.) pnr rqk
queens                      = liftA2 (.&.) pbq rqk
kings                       = liftA2 (.&.) nbk rqk

We can create a bitboard with a single occupied square:

square :: Int -> Word4 -> QuadBitboard
square !sq !nb = QBB (f 0) (f 1) (f 2) (f 3) where
  !b = bit sq
  f !n = fromIntegral ((nb `unsafeShiftR` n) .&. 1) * b

And, as an aside, we can even use pattern synonyms to give these nibbles
meaningful names.

pattern NoPiece     = 0
pattern WhitePawn   = 2
pattern WhiteKnight = 4
pattern WhiteBishop = 6
pattern WhiteRook   = 8
pattern WhiteQueen  = 10
pattern WhiteKing   = 12
pattern BlackPawn   = 3
pattern BlackKnight = 5
pattern BlackBishop = 7
pattern BlackRook   = 9
pattern BlackQueen  = 11
pattern BlackKing   = 13

But what felt really like a cool discovery, is combination:

instance Monoid QuadBitboard where
  mempty = QBB 0 0 0 0

-- | bitwise XOR
instance Semigroup QuadBitboard where
  QBB b0 b1 b2 b3 <> QBB b0' b1' b2' b3' =
    QBB (b0 `xor` b0') (b1 `xor` b1') (b2 `xor` b2') (b3 `xor` b3')

With this, we can pretty easily define a function to create a quad
bitboard from a string:

instance IsString QuadBitboard where
  fromString = go (7, 0) mempty where
    go _ !qbb "" = qbb
    go (!r,_) qbb ('/':xs) = go (r - 1, 0) qbb xs
    go (!r,!f) !qbb (x:xs)
      | inRange ('1','8') x = go (r, f + (ord x - ord '0')) qbb xs
      | otherwise = go (r, f + 1) (qbb <> square (r*8+f) nb) xs where
        nb = case x of
          'P' -> WhitePawn
          'N' -> WhiteKnight
          'B' -> WhiteBishop
          'R' -> WhiteRook
          'Q' -> WhiteQueen
          'K' -> WhiteKing
          'p' -> BlackPawn
          'n' -> BlackKnight
          'b' -> BlackBishop
          'r' -> BlackRook
          'q' -> BlackQueen
          'k' -> BlackKing
          _ -> error $ "QuadBitBoard.fromString: Illegal FEN character " <> show x

standard :: QuadBitboard
standard = "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR"

The rest of the module builds on the Monoid instance of QuadBitboard.

Again, this is the first time a instance like this turns up in my Haskell
experiments.  It feels extremely satisfying having discovered this. But
maybe I am violating some laws (I hear instances do that sometimes!) or
some other thing is totally wrong.  One might say
I am not fully trusting the peace.

https://hackage.haskell.org/package/chessIO/docs/Game-Chess-QuadBitboard.htm...

-- 
CYa,
  ⡍⠁⠗⠊⠕

Mario Lang

Ben Franksen

Henning Thielemann

Ben Franksen

Andrew Butterfield

Andrew Butterfield

Henning Thielemann

Jaro Reinders

Andrew Butterfield

Oleg Grenrus

tags

participants (6)