Scala tic-tac-toe no mutable state 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]]) =&gt; 
      g.slice(0, 3) :: 
      g.slice(3, 6) :: 
      g.slice(6, 9) :: Nil

    val toPrint = (p: Option[Player.Value]) =&gt; if (p.isEmpty) "   " else " " + p.get.toString() + " "
    val gridPrint = (g: List[List[Option[Player.Value]]]) =&gt; g.map(_.map(toPrint).mkString("|")).mkString("\n---+---+---\n")+"\n\n"
    println(gridPrint(sliceHorizontal(grid)))

    val emptyCells = (g: List[Option[Any]]) =&gt; 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) =&gt; if (emptyCells(g).contains(v)) v else playerChoice(g)
        case Failure(_) =&gt; 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 &lt; 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) =&gt; winningLines.
        foldLeft(false)((i, s) =&gt; 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.
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) =&gt; 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 =&gt; 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 =&gt; 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) =&gt; 
          if (emptyCells(g).contains(v)) v 
          else {
          println("Position already occupied, please try a different one")
          playerChoice(g)
        }
        case Failure(_) =&gt; 
          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) =&gt; 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))
}