Writing a Tictactoe game in Haskell
Tags: haskell, functional
Published: 2019-08-12 20:30:47


***
Code can be found [here](https://github.com/nt591/haskell-playground/blob/master/random/tictactoe.hs)
***

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](https://github.com/github/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](http://learnyouahaskell.com) and watching some Youtube videos, I felt reasonably comfortable in being able to write a small Tictactoe CLI game. I went with [Stack](https://docs.haskellstack.org/en/stable/README/) 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`

```haskell
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](https://www.haskell.org/tutorial/stdclasses.html).

```haskell
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.

```haskell
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](http://learnyouahaskell.com/input-and-output). 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.

```haskell
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:

```haskell
  (>>=)            :: 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.

```haskell
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](http://hackage.haskell.org/package/base-4.12.0.0/docs/Data-Eq.html)


```haskell
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

```haskell
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.

```haskell
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.

```haskell
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.