Scala tic-tac-toe no mutable state

Question

The following was an exercise for me to try to understand how state can be passed down the stack without immutability.

I'm used to writing java code and this is just a way for me to understand.

I've made no attempt to make the computer play a clever game. It just selects a random move. Player is always X. Player always starts first. Moves are made by entering the 0 based index of the grid

 0 | 1 | 2
---+---+---
 3 | 4 | 5
-----------
 6 | 7 | 8 

However I found it difficult to write and find the piece that calculates if there is any winning line very messy to read.

import scala.annotation.tailrec
import scala.io.StdIn
import scala.util.{Success, Failure, Random,Try}
/**
 * A simple expirement in tic tac toe the idea
 * is to try to have something that contains state
 * without having vars. 
 */
object ttt extends App {
 object Player extends Enumeration {
 val X, O = Value
 }
 val grid: List[Option[Player.Value]] =
 None :: None :: None ::
 None :: None :: None ::
 None :: None :: None ::
 Nil
 val winningLines = List(0, 1, 2) ::
 List(3, 4, 5) ::
 List(6, 7, 8) ::
 List(0, 3, 6) ::
 List(1, 4, 7) ::
 List(2, 5, 8) ::
 List(1, 4, 8) ::
 List(2, 4, 6) :: Nil
 @tailrec
 def play(next: Player.Value, grid: List[Option[Player.Value]]): String = {
 val sliceHorizontal = (g:List[Option[Player.Value]]) => 
 g.slice(0, 3) :: 
 g.slice(3, 6) :: 
 g.slice(6, 9) :: Nil
 val toPrint = (p: Option[Player.Value]) => if (p.isEmpty) " " else " " + p.get.toString() + " "
 val gridPrint = (g: List[List[Option[Player.Value]]]) => g.map(_.map(toPrint).mkString("|")).mkString("\n---+---+---\n")+"\n\n"
 println(gridPrint(sliceHorizontal(grid)))
 val emptyCells = (g: List[Option[Any]]) => g.zipWithIndex.
 filter(_._1.isEmpty).
 map(_._2)
 lazy val randomCell = Random.shuffle(emptyCells(grid)).head
 def playerChoice(g: List[Option[Player.Value]]): Int = {
 print("Please enter selection, ")
 val result = Try(StdIn.readInt());
 result match {
 case Success(v) => if (emptyCells(g).contains(v)) v else playerChoice(g)
 case Failure(_) => playerChoice(g)
 }
 }
 if (emptyCells(grid).isEmpty) {
 "Draw"
 } else {
 val newGrid = if (next == Player.O) {
 grid.updated(randomCell, Some(Player.O))
 } else {
 grid.updated(playerChoice(grid), Some(Player.X))
 }
 def listOfDuplicates[A](x: A, length: Int): List[A] = {
 if (length < 1) Nil
 else x :: listOfDuplicates(x, length - 1)
 }
 def allEqual[A](first: A, seq: List[A]):Boolean = {
 if (seq isEmpty) true
 else if (first != seq.head) false
 else allEqual(first, seq.tail)
 }
 //Okay this is very messy not used to this
 val hasWon= (p: Player.Value) => winningLines.
 foldLeft(false)((i, s) => i || allEqual(Some(p), s.map(newGrid(_)))) 
 if (hasWon(Player.X)) {
 println(gridPrint(sliceHorizontal(newGrid)))
 "X Wins"
 } else if (hasWon(Player.O)) {
 println(gridPrint(sliceHorizontal(newGrid)))
 "O Wins"
 } else play(if (next == Player.O) Player.X else Player.O, newGrid)
 }
 }
 println(play(Player.X, grid))
}

How can I clean this up and make it more idiomatic? easier to read? Also for tic-tac-toe it doesn't matter much but for a large game if it wasn't tail recursive I guess I couldn't use this strategy for holding state between moves.

• Athas: @200_success what does the tic-tac-toe tag really add to the question?
• 200_success: Tagging makes it easier for future users of this site to find tic-tac-toe-related questions.
• Athas: I didn't know it was something people came to the site to fine.
• Athas: Follow up question stackoverflow.com/questions/48833026/…

Answer 1

I won't comment about your algorithm, as I understand that that's not the focus of this review - suffice it to say that there are better ways of checking winning than comparing against hard-coded winning lines, even in Scala.

Also, Scala has a beautiful and extensive standard library, especially for collections - learn and use it!

In no particular order:

• Don't explicitly construct lists - use factory methods

  i.e., List.apply(values: T*), a variadic method which can be invoked with syntax sugar as List(value1, value2, ... valueN), as well as similar fill and tabulate.

  In fact, fill makes your listOfDuplicates function redundant. There's also a forall method taking a boolean predicate and a list and returning whether all elements of the list satisfy the predicate or not, which makes your allEqual method kind of redundant.

• Use appropriate prompts and notification when interacting with the user

  For example, when you recurse in playerChoice, you do not let the user know why you're prompting him/her for input again. let him/her know that the position is occupied or invalid before asking him/her again.

• Use IndexedSeq for random-access immutable collections

  Here I recommend using IndexedSeq instead of Vector specifically to ensure that we type to interfaces - you might want to swap out the implementation for an array later on. This'll also make you update the function signatures.

  Why IndexedSeq instead of List? You use updated, a function which accesses elements by index. This is \$O(n)\$ for a List, but amortized \$O(1)\$ for Vector or Array, which follow the IndexedSeq interface.

• collect instead of chained filter and map

collect allows you to combine filter and map, essentially allowing you to do pattern-matching in situ. Leads to 1 less intermediate collection (seeing that you aren't using lazy .views) and cleaner code.

• Use nested/local functions instead of function literals

  In Scala, you can put def within def and so on. This'll allow you to get around the ugly List[Option[Any]] you have for emptyCells and replace it with a proper type parameter. You do this for allEqual already, I don't know why you aren't doing it for everything else (did you copy allEqual` from somewhere else?).

• Alias long, frequently used types

Type-alias Player.Value to Player and import it to reduce some visual clutter. Also do the same with List[Option[Player.Value]] by aliasing it to Grid to reduce visual clutter even more.

• Use more descriptive variable names

  grid for g and value/position for v couldn't hurt.

• Proper spacing and indentation

  Good enough, but somewhat inconsistent. Put it through an IDE autoformatter, e.g., IntelliJ IDEA's.

• Some general ideas for improvement

  • Incorporate a clean quit mechanism, maybe a q at the prompt?
  • A help menu where you explain how to play would be nice.
  • Adding player choice is not that difficult - try it. Just a wee bit of initialization code.

All in all, functional programming is about composing functions together to write programs; immutability and stuff is good to have but it isn't primary. You have some repetition, as in the hasWon check - see if you can get rid of it (Hint - you might want a function which can iterate over the values of the Player enum and check if any of them have won).

Also, this

def hasWon(p: Player) = winningLines.foldLeft(false)((i, s) => i || allEqual(Some(p), s.map(newGrid(_))))

isn't really ugly. It's a mouthful, yes, but that can be improved with better parameter names (something I'm not doing for you right now - I hope I've indicated how to do it on your own). Don't worry - you'll get used to it. I nowadays find that foldLeft easier to read than a couple nested for loops.

Here's the current code (I might throw in more improvements later):

import scala.annotation.tailrec
import scala.io.StdIn
import scala.util.{Success, Failure, Random,Try}
/**
 * A simple expirement in tic tac toe the idea
 * is to try to have something that contains state
 * without having vars. 
 */
object TicTacToe extends App {
 object Player extends Enumeration {
 val X, O = Value
 type Player = Value
 }
 import Player._
 type Grid = Seq[Option[Player]]
 val grid: Grid = IndexedSeq.fill(9)(None)
 val winningLines = 
 IndexedSeq(
 IndexedSeq(0, 1, 2),
 IndexedSeq(3, 4, 5),
 IndexedSeq(6, 7, 8),
 IndexedSeq(0, 3, 6),
 IndexedSeq(1, 4, 7),
 IndexedSeq(2, 5, 8),
 IndexedSeq(1, 4, 8),
 IndexedSeq(2, 4, 6))
 @tailrec
 def play(next: Player.Value, grid: Grid): String = {
 def sliceHorizontal(g: Grid) = 
 IndexedSeq(
 g.slice(0, 3),
 g.slice(3, 6),
 g.slice(6, 9))
 def playerRepr(p: Option[Player]) = p.map(v => s" $v ").getOrElse(" ")
 def gridRepr(g: Seq[Grid]) = g.map(_.map(playerRepr).mkString("|")).mkString("", "\n---+---+---\n", "\n\n")
 def printGrid(g: Grid) = println(gridRepr(sliceHorizontal(g)))
 printGrid(grid)
 def emptyCells[T](g: Seq[Option[T]]) = 
 g.zipWithIndex.collect {
 case (value, index) if value.isEmpty => index
 }
 lazy val randomCell = Random.shuffle(emptyCells(grid)).head
 @tailrec
 def playerChoice(g: Grid): Int = {
 print("Please enter selection: ")
 Try(StdIn.readInt()) match {
 case Success(v) => 
 if (emptyCells(g).contains(v)) v 
 else {
 println("Position already occupied, please try a different one")
 playerChoice(g)
 }
 case Failure(_) => 
 println("Invalid Position - try a value between 0 and 8")
 playerChoice(g)
 }
 }
 if (emptyCells(grid).isEmpty) {
 "Draw"
 } else {
 val newGrid = if (next == O) {
 grid.updated(randomCell, Some(O))
 } else {
 grid.updated(playerChoice(grid), Some(X))
 }
 def allEqual[A](first: A, seq: Seq[A]): Boolean = seq.forall(_ == first)
 def hasWon(p: Player) = winningLines.foldLeft(false)((i, s) => i || allEqual(Some(p), s.map(newGrid(_)))) 
 if (hasWon(X)) {
 printGrid(newGrid)
 "X Wins"
 } else if (hasWon(O)) {
 printGrid(newGrid)
 "O Wins"
 } else {
 play(if (next == O) X else O, newGrid)
 }
 }
 }
 println(play(Player.X, grid))
}

• Athas: Thank you so much. Better player input / handling wouldn't have been hard. Its kind of outside what I was attempting to do and I ignored it. I do find the iterating over sub lists with the for all messy coming from being used to mutable state. I.e a forall / foreach doesn't clollect a value so that confused me. Theres also some performance things I may have done if there was more rows to go through. I'm currently just trying to understand how to avoid mutable state and wondered if there were patterns rather than library components that are used for generalisation. I must read style guide.
• Athas: type alias is wonderful and I didn't know about that feature
• Athas: All Equal was not a copy but I really needed it at that point and looked up the syntax. Assuming it would be simiiar to java.
• Tamoghna Chowdhury: @Athas, the best thing about functional programming is learning how there are many general solutions to specific problems - and you don't even have to code them up yourself - they're in the standard library already.
• Tamoghna Chowdhury: Also, it's not like idiomatic Scala shuns mutable state or side effects in general (which includes println and family) - it (functional programming) wants you to isolate state mutation into controlled segments. Your code is also verifiably correct given the semantics of all included functions, which is far more difficult to verify for procedural code.