Honing my craft

Tictactoe in Haskell

August 12, 2019

Code can be found here

While I struggle with some misunderstandings of the OCaml module system, I decided to put my interpreter on temporary hold to try some Haskell. It’s a language that’s been on my radar and been a goal to learn. A combination of Haskell’s terse notation ( it turns out sum . take 10 $ (*) <$> [2,4,6] <*> [1,2,3,4,5] is a completely legitimate, if daunting line of code ) combined with the new terminology (cue monad tutorial) caused some delay. But after deciding to commit, and OCaml’s slightly more friendly entry to FP, I felt capable of getting my hands dirty. I felt particularly inspired after seeing code written for Github’s Semantic project. At some point, I’d like to work on some meaty Haskell productive code and there’s no place to start like starting.

After reading a lot of Learn You A Haskell For Great Good and watching some Youtube videos, I felt reasonably comfortable in being able to write a small Tictactoe CLI game. I went with Stack as my build tool of choice.

Like OCaml, Haskell’s type system encourages domain modeling early. I decided to make my board a list of 9 elements, where each element could be either an X, an O, or empty. Since Haskell doesn’t really have a null type, I decided to create both a Move as well as a Cell

import System.Environment
import Data.List

data Move = X | O
data Cell = Occupied Move | Empty

We’re taking System.Environment because we’ll need some IO behavior, and Data.List for some future functions.

I could have made Cell a Maybe type, but chose a more descriptive way to express a cell. This way, I can keep track of the move to play as well as see what was in the cell. I also needed a way to render this board out. Since I’m using custom types, I needed to create instances of the Show typeclass.

instance Show Move where
  show X = "X"
  show O = "O"

instance Show Cell where
  show (Occupied X)     = "X"
  show (Occupied O)    = "O"
  show Empty            = " "

I’m semi-positive I could have used deriving (Show) on my Move type but that’ll be for a later refactor. Today’s primary goal was just writing code. My next plan was to get some board-rendering code up. I needed a function that simply took my board, my [Cell] and output something pretty.

renderRow :: [Cell] -> String
renderRow row = intercalate " | " $ fmap show row

dividingLine :: String
dividingLine = "----------"

renderBoard :: [Cell] -> IO ()
renderBoard board = do
  putStrLn $ renderRow firstRow
  putStrLn dividingLine
  putStrLn $ renderRow secondRow
  putStrLn dividingLine
  putStrLn $ renderRow thirdRow
  where firstRow  = take 3 board
        secondRow = drop 3 . take 6 $ board
        thirdRow  = drop 6 board

renderRow takes a list of cells and returns the readable version joined by pipes. renderBoard just some some list-slicing to render no more than 3 rows of 3 elements. Since I’m writing to console, I’ll need to return an IO (), the IO monad. Without getting too in the weeds, I/O is considered to be a side-effect and therefore Haskell forces you to wrap it in a monad.

If I were to call renderBoard with a list of empty elements [Empty, Empty, Empty, Empty, Empty, Empty, Empty, Empty, Empty] I would get a very pretty

  |   |
  |   |
  |   |

My next goal was some idea of assignment. I needed to be able to take a Move and a [Cell] and return an updated board. There are a couple of rules to this

  1. The selected cell must be within bounds.
  2. The selected cell must be free.

Given this, I decided to simply create a map of input strings to List indices. Is it pretty? Nope. But it works fine for this case.

getBoardIndex :: String -> Maybe Int
getBoardIndex "A1" = Just 0
getBoardIndex "A2" = Just 1
getBoardIndex "A3" = Just 2
getBoardIndex "B1" = Just 3
getBoardIndex "B2" = Just 4
getBoardIndex "B3" = Just 5
getBoardIndex "C1" = Just 6
getBoardIndex "C2" = Just 7
getBoardIndex "C3" = Just 8
getBoardIndex _    = Nothing

Pattern matching in Haskell is a little more terse than OCaml, in that I don’t need a match statement. I simply create functions for every possiblity, similar to Elixir’s matching. You’ll see also I’m returning a Maybe Int - I chose this because not just do I care if a board index is real, but also if it’s free. Two if statements, so I can use monadic binding, or the >>= operator. For reference:

  (>>=)            :: m a -> (a -> m b) -> m b

What this says is “Give me a monad of some a, and give me a function that turns some a into a monad of b and I’ll return a monad of b. If I have a Maybe Int from getBoardIndex and my function for “is that cell free to assign” takes an Int and returns a Maybe then I can use this binding.

data CellTransform = Success [Cell] | Fail String [Cell]

verifyIsFree ::  [Cell] -> Int -> Maybe Int
verifyIsFree board ix = if board !! ix == Empty then Just ix else Nothing

assignCell :: String -> Move -> [Cell] -> CellTransform
assignCell location move board =
  case getBoardIndex location >>= verifyIsFree board of
    Nothing -> Fail "Invalid move" board
    Just i -> Success ((take i board) ++ [Occupied move] ++ (drop (i+1) board))

You’ll see this new CellTransform type. I added a new type just to carry along error messages and an unmodified board if the board is taken. So my verifyIsFree takes a board and index, and if the board is free at that element returns the index in a Maybe, else Nothing. Since I’m doing some equality checks of a custom data type, I’ll need to make sure that Cell is also an instance of the Eq typeclass

instance Eq Cell where
  Occupied X == Occupied X = True
  Occupied O == Occupied O = True
  Empty == Empty           = True
  _ == _                   = False

This just sets my equality operator for all possible states of a Cell.

Lastly, my actual game. I need my game to

  1. Ask for input
  2. Try to assign the cell 3a) If the cell is invalid, tell the user and let them pick again 3b) If the cell is valid, check for a winner 4a) If there’s a winner, alert them and end the game 4b) If there’s no winner, hand over to the next player

Let’s get this coded out

playRound :: Move  -> [Cell] -> IO ()
playRound move board = do
  putStrLn $ (show move) ++ " 's turn."
  putStrLn $ "Pick a cell from A1 to C3."
  renderBoard board
  putStr "\nInput: "
  cell <- getLine
  case assignCell cell move board of
    Fail err board -> do
      putStrLn err
      playRound move board
    Success newBoard -> do
      if isThereAWinner move newBoard then do
        putStrLn $ ("Winner! " ++ (show move) ++ " has won!")
        renderBoard newBoard
        return ()
      else playRound (nextMove move) newBoard

Since we’re using I/O again, we need to return an IO Monad. That also gives us the do notation benefits of some slightly more imperative-reading code.

You’ll see some fake functions - isThereAWinner and nextMove move. We can code these out.

nextMove :: Move -> Move
nextMove X = O
nextMove O = X

isThereAWinner :: Move -> [Cell] -> Bool
isThereAWinner move board =
  or [
    -- check top row
    board !! 0 == (Occupied move) && board !! 1 == (Occupied move) && board !! 2 == (Occupied move),
    -- check middle row
    board !! 3 == (Occupied move) && board !! 4 == (Occupied move) && board !! 5 == (Occupied move),
    -- check bottom row
    board !! 6 == (Occupied move) && board !! 7 == (Occupied move) && board !! 8 == (Occupied move),
    -- check left column
    board !! 0 == (Occupied move) && board !! 3 == (Occupied move) && board !! 6 == (Occupied move),
    -- check middle column
    board !! 1 == (Occupied move) && board !! 4 == (Occupied move) && board !! 7 == (Occupied move),
    -- check right column
    board !! 2 == (Occupied move) && board !! 5 == (Occupied move) && board !! 8 == (Occupied move),
    -- check top left -> bottom right
    board !! 0 == (Occupied move) && board !! 4 == (Occupied move) && board !! 8 == (Occupied move),
    -- check bottom left -> top right
    board !! 6 == (Occupied move) && board !! 4 == (Occupied move) && board !! 2 == (Occupied move)

This is my least-favorite function here. It’s readable with comments, but definitely isn’t pleasant. I can’t imagine changing this into a 5x5 tic-tac-toe board or something. But once we have this, we can create a main function.

main :: IO ()
main = do
  putStrLn $ "The game is beginning."
  let newBoard = replicate 9 Empty
  playRound X newBoard

And we can build our tictactoe.hs with stack ghc tictactoe.hs and run ./tictactoe to play!

This was a fun experiment. I tried to avoid having to dig too into monadic operators, the State monad, or advanced Haskell techniques. My primary focus was to just type code and try to get comfortable with the syntax. The compiler is pretty helpful, but not as explicit as Elm’s compiler. Since my career goals are to get a job writing backend ML-family code (Scala, OCaml, Haskell, etc) I’ll keep on practicing. I’d love any project ideas. I might try to write a Lisp interpreter for a bigger, meatier project.

Nikhil Thomas

I work and live in Brooklyn, NY building software.