# You can't sink me

Here is a Battlehips game in F#. Now, before you start jumping up and down on my code, please understand that, for all its awesomeness, F# has a serious limitation: Its compilation is linear, and the solution structure cannot have folders. Any code that uses other code must be below the other code, whether in the same file, or in another file lower than the first file in the compilation sequence.

Here is my GeneralData file. It contains basic data and methods not specifically relevant to other groups.

module GeneralData

type direction = Horizontal | Vertical

type public point = {x :int; y :int}
type public battleship = {coordinate :point; direction :direction; length :int}

let charToDirection (character :char) :direction =
match character with
| 'H' | 'h' -> Horizontal
| 'V' | 'v' -> Vertical
| _ -> raise <| new System.ArgumentException("character must be 'H' or 'V'", "character")

let directionToChar (character :direction) :char =
match character with
| Horizontal -> 'H'
| Vertical -> 'V'


Next in the compilation hierarchy is my Board class:

module Board

open GeneralData
open System

[<Flags>]
type public squareState = Empty = 0 | Ship = 1 | Bombarded = 2

type public Board() =
let mutable board :squareState[,] = Array2D.init 10 10 (fun x y -> squareState.Empty)

let getChar (state :squareState) :char =
if state.HasFlag(squareState.Bombarded) && state.HasFlag(squareState.Ship) then
'X'
elif state.HasFlag(squareState.Bombarded) then
'O'
else
' '

let getCharShowingShips (state :squareState) :char =
if state.HasFlag(squareState.Bombarded) && state.HasFlag(squareState.Ship) then
'X'
elif state.HasFlag(squareState.Bombarded) then
'O'
elif state.HasFlag(squareState.Ship) then
'S'
else
' '

member self.boardArray :squareState[,] = board

member public self.placeShip(ship :battleship) =
for i = 0 to ship.length - 1 do
// This member should only be called before bombardment starts,
// which means that all squares are either flagged "Empty" (0) or "Ship" (1)
// No need to combine the exising flag with the "Ship flag
match ship.direction with
| Horizontal -> board.[ship.coordinate.x, ship.coordinate.y + i] <- squareState.Ship
| Vertical -> board.[ship.coordinate.x + i, ship.coordinate.y] <- squareState.Ship

member public self.canPlaceShip (ship :battleship) :bool =
let mutable allFreeCoordinates = true

for i = 0 to ship.length - 1 do
// This member should only be called before bombardment starts,
// which means that all squares are either flagged "Empty" (0) or "Ship" (1)
// No need to use the HasFlag member
match ship.direction with
| Horizontal -> allFreeCoordinates <- allFreeCoordinates
&& not (ship.coordinate.y + i > 9)
&& not (board.[ship.coordinate.x, ship.coordinate.y + i] = squareState.Ship)
| Vertical -> allFreeCoordinates <- allFreeCoordinates
&& not (ship.coordinate.x + i > 9)
&& not (board.[ship.coordinate.x + i, ship.coordinate.y] = squareState.Ship)

allFreeCoordinates

member public self.bombard(coord :point) =
if coord.x < 0 || coord.x > 10 ||
coord.y < 0 || coord.y > 10 then
raise <| new System.ArgumentException("Point must be in range ([0-9], [0-9]", "coord")

if board.[coord.x, coord.y].HasFlag(squareState.Bombarded) then
raise <| new System.ArgumentException("Square already bombarded", "coord")

// Save the original "Ship" flag (if any) in addition to adding the "Bombarded" flag
board.[coord.x, coord.y] <- board.[coord.x, coord.y] ||| squareState.Bombarded

member public self.areAllShipsSunk() :bool =
let mutable shipNotSunk = true
for x = 0 to 9 do
for y = 0 to 9 do
let state = board.[x, y]
if state.HasFlag(squareState.Ship) && not (state.HasFlag squareState.Bombarded) then
shipNotSunk <- false

shipNotSunk

member public self.state(coord :point) =
if coord.x < 0 || coord.x > 10 ||
coord.y < 0 || coord.y > 10 then
raise <| new System.ArgumentException("Point must be in range ([0-9], [0-9]", "coord")

board.[coord.x, coord.y]

member public self.print() =
printfn "--------------------------------------------"
for i = 0 to 9 do
// print row number and first token
printf "%s%d" (if i = 9 then "" else " ") (i + 1)

for j = 0 to 9 do
printf " | %c" (getChar(board.[i, j]))

printfn " |%s--------------------------------------------" Environment.NewLine

printfn "%s" (String.Format("     1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10"))

member public self.printShowingShips() =
printfn "--------------------------------------------"
for i = 0 to 9 do
// print row number and first token
printf "%s%d" (if i = 9 then "" else " ") (i + 1)

for j = 0 to 9 do
printf " | %c" (getCharShowingShips(board.[i, j]))

printfn " |%s--------------------------------------------" Environment.NewLine

printfn "%s" (String.Format("     1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10"))


The InputFunctions module follows the Board class, and contains a representation of a game board:

module InputFunctions

open Board
open GeneralData
open System

// internal for testing purposes only
let internal isValidInput (board :Board) (shipLength :int) (input :string[]) :bool =
let mutable xInput : int = -1
let mutable yInput : int = -1

let isValidInput = input.Length = 3 &&
Int32.TryParse(input.[0], &xInput) &&
xInput >= 1 && xInput <= 10 &&
Int32.TryParse(input.[1], &yInput) &&
yInput >= 1 && yInput <= 10 &&
Array.contains input.[2].[0] [|'H'; 'V'; 'h'; 'v'|]

// adjust coordinate for 1-based UI
let coord = {x = xInput - 1; y = yInput - 1}
isValidInput && (board.canPlaceShip {coordinate = coord; direction = charToDirection(input.[2].[0]); length = shipLength})

let inputBattleshipCoord (board :Board) (shipName :string) (shipLength :int) :battleship =

// invalid array to trigger loop
let mutable input = [|"-1"; "-1"; "I"|]

// todo: check if input also fits on board
while not (isValidInput board shipLength input) do
printf "Please enter the upper left position for your %s (%d squares long) in the format 'Row:Column:{V or H}' (without the quotes or braces): " shipName shipLength

let coordinate :point = {x = Int32.Parse(input.[0]) - 1; y = Int32.Parse(input.[1]) - 1}
{coordinate = coordinate; direction = charToDirection(input.[2].[0]); length = shipLength}

// internal for testing purposes only
let internal isValidBombardInput (board :Board) (input :string[]) =
let mutable xInput :int = -1
let mutable yInput :int = -1

input.Length = 2 &&
Int32.TryParse(input.[0], &xInput) &&
xInput >= 1 && xInput <= 10 &&
Int32.TryParse(input.[1], &yInput) &&
yInput >= 1 && yInput <= 10 &&
not (board.state({x = xInput - 1; y = yInput - 1}).HasFlag(squareState.Bombarded))

let inputBombardPoint (board :Board) :point =
let mutable input = [||]

while not (isValidBombardInput board input) do
printf "Input the point you want to bombard as 'Row:Column' (without the quotes): "

{x = Int32.Parse(input.[0]) - 1; y = Int32.Parse(input.[1]) - 1}


Finally, here is the Battleships module, which runs the game:

module Start

open Board
open GeneralData
open InputFunctions
open System
open System.Collections.Generic

let ships :(string * int)[] =
[|
("Aircraft carrier", 5)
("Battleship", 4)
("Frigate", 3)
("Submarine", 3)
("Minesweeper", 2)
|]

let rand = new Random()

let placeUserShips (board :Board) =
for i = 0 to ships.Length - 1 do
let shipName, shipLength = ships.[i]
let ship = inputBattleshipCoord board shipName shipLength
board.placeShip ship
board.printShowingShips()

let placeComputerShips (board :Board) =
for i = 0 to ships.Length - 1 do
// invalid value to trigger loop
let mutable shipPlaced = false

while not shipPlaced do
let xCoord = rand.Next(0, 10)
let yCoord = rand.Next(0, 10)
let direction = if rand.Next(0, 2) = 0 then Horizontal else Vertical
let ship = {coordinate = {x = xCoord; y = yCoord}; direction = direction; length = snd ships.[i]}

if board.canPlaceShip ship then
board.placeShip ship
shipPlaced <- true

let userBombard (board :Board) =
let mutable bombard = true

while bombard do
let point = inputBombardPoint board
board.bombard point

if not ((board.state point).HasFlag(squareState.Ship)) ||
board.areAllShipsSunk() then
bombard <- false

let computerBombard (board :Board) =
let openPoints = new List<point>()

for x = 0 to 9 do
for y = 0 to 9 do
let currentPoint = {x = x; y = y}
if not (board.state(currentPoint).HasFlag(squareState.Bombarded)) then

let mutable bombard = true
while bombard do
let nextPoint = rand.Next(0, openPoints.Count)
board.bombard openPoints.[nextPoint]

if not ((board.state openPoints.[nextPoint]).HasFlag(squareState.Ship)) ||
board.areAllShipsSunk() then
bombard <- false
else
openPoints.RemoveAt nextPoint

[<EntryPoint>]
let main argv =
let userBoard = new Board()

// display empty board so user knows how/where to place ships
userBoard.printShowingShips()
placeUserShips userBoard

let computerBoard = new Board()
placeComputerShips computerBoard

while not (computerBoard.areAllShipsSunk()) && not (userBoard.areAllShipsSunk()) do
// no need to check computer win because the loop would have ended
userBombard computerBoard
computerBoard.print()
printfn ""

// check user win
if not (computerBoard.areAllShipsSunk()) then
computerBombard userBoard
userBoard.print()
printfn ""

printfn (if computerBoard.areAllShipsSunk() then "You won!" else "You lost!")
0


I have this set up with a very basic algorithm for the computer to play (random-selection, hence the title--you'd have pretty bad luck to be fully sunk). Next, my plan is to create a Player interface with two classes implementing it (HumanPlayer and ComputerPlayer). This will help clean some of the muddle of the Battleships module up, and will make it easier to implement a better algorithm for the computer, and may make it easier to let the user choose to play the computer or another person.

Some of my specific concerns about this is that I may have implemented this in either a too-C# or too-OOP manner. I'm not really familiar with functional programming or F#, so feel free to comment on anything that should be done differently.

• Quick nit-pick: the Board module must be second, not third, because it is used by InputFunctions – AlexFoxGill Sep 13 '16 at 11:22
• @AlexFoxGill You are right--the Board module is second in my program. – user34073 Sep 13 '16 at 15:20
• In case you didn't see it, there's a question here where someone has taken the functional route - it may help – AlexFoxGill Sep 20 '16 at 8:15

You are correct in your statement that this is a pretty standard OOP implementation. The key signs are lots of mutable state and explicit loops. It's hard to give a line-by-line critique because a functional program would be structured so differently (maybe this is why nobody has posted an answer yet!)

First let's tackle a small stylistic point: It's generally accepted that in F#, types and type members are PascalCase, whereas function names are camelCase.

Another thing that stands out is that the functions in your code are quite long. A common consequence of FP, and in particular designing with types, is that you end up with smaller functions at every level, which can be composed and used at the higher level.

A common temptation when modelling two-dimensional boards such as in Battleships (or Chess, Noughts and Crosses etc) is to try and model the physical nature of the board - ie, a 2-dimensional array. However, when you think about the domain, this is only superficial. What you really have on a "board" is a series of points/coordinates, a set of ships which occupy some of those points, and a series of guesses (again, points). With the 2d-array approach, you're immediately restricted to working with primitive values by indexing into the array. Although you had the right idea by creating the point record type, you didn't leverage the ability to work on the point level - instead, all the functions which use the point type are further up the conceptual hierarchy, mainly in the Board type. The mental model of the array restricts your thinking to X and Y values, rather than dealing in points.

I'd like to give a longer answer but I'm out of time right now, I'll gladly respond to any questions you have! I started working on a functional version of the problem, I only got as far as the "domain" (no input events or rendering yet) but perhaps this will help you visualise how a functional version would be structured:

module Common =
type Result<'TSuccess,'TError> =
| Success of 'TSuccess
| Error of 'TError

module Seq =
let overlaps (xs: 'a seq) (ys: 'a seq) = Seq.exists2 (=) xs ys

module Domain =
type Direction = Horizontal | Vertical

type Point = {
X: int
Y: int
} with
static member zero = { X = 0; Y = 0 }
static member addX (p: Point) (i: int) = { p with X = p.X + i }
static member addY (p: Point) (i: int) = { p with Y = p.Y + i }
static member (>~=) (a: Point, b: Point) =
a.X >= b.X && a.Y >= b.Y

type Ship = {
Name: string
Length: int
}

let ships = [
{ Name = "Aircraft Carrier"; Length = 5 }
{ Name = "Battleship"; Length = 4 }
{ Name = "Frigate"; Length = 3 }
{ Name = "Submarine"; Length = 3 }
{ Name = "Minesweeper"; Length = 2 }
]

type PlacedShip = {
Ship: Ship
Position: Point
Direction: Direction
} with
static member allPoints (ps: PlacedShip) =
static member lastPoint (ps: PlacedShip) =
Point.add ps.Direction ps.Position (ps.Ship.Length - 1)

type BoardState = {
Ships: PlacedShip list
Guessed: Set<Point>
Bounds: Point
} with
static member allPlacedPoints (bs: BoardState) =
bs.Ships
|> Seq.collect PlacedShip.allPoints
|> Set.ofSeq

static member placeShip (bs: BoardState) (s: PlacedShip) =
let withinBounds =
bs.Bounds >~= (PlacedShip.lastPoint s) && s.Position >~= Point.zero

let overlapsOtherShips =
bs
|> BoardState.allPlacedPoints
|> Seq.overlaps (PlacedShip.allPoints s)

if not withinBounds then
Common.Error "This ship placement is out of bounds"
else if overlapsOtherShips then
Common.Error "This ship placement overlaps another ship"
else
Common.Success { bs with Ships = s :: bs.Ships }

static member addGuess (bs: BoardState) (p: Point) =
if Set.contains p bs.Guessed then
Common.Error <| sprintf "The coordinate %A has already been guessed" p
else
Common.Success { bs with Guessed = Set.add p bs.Guessed }

static member hasLost (bs: BoardState) =
bs
|> BoardState.allPlacedPoints
|> Set.isSubset bs.Guessed

type Player = {
Name: string
Board: BoardState
}

• Thanks. I guess I have a lot to learn about FP. And I thought my functions were pretty short (I guess they were... for OOP functions...). – user34073 Sep 13 '16 at 16:13

# Imperative Programming vs. Functional Programming

AlexFoxGill brought up the point that your code is structured a lot like something you'd write in an imperative language, however, the major differences between functional and imperative programming weren't brought up. The two biggest differences you need to know about are how code is structured and how flow control is different.

Code in imperative languages is structured in a way that describes how the performs tasks that manage the state. Code in functional languages is structured in a way that describes what inputs are required and how that input is transformed. Many functional languages, like F# and Haskell, allow you to write imperative code to some degree, but most of the time there's a better, functional, solution.

Flow control in imperative languages the stuff that you'd typically expect (if, for, foreach, do, while, etc.). Nothing out of the ordinary. Flow control in functional languages is based much more around function calls and recursion. Again, many functional languages allow you to write imperative flow control to some degree, but most of the time there's a better solution.

These are the two biggest things you should be aware of, but there are some more. This chart from MSDN provides some nice comparisons between imperative and functional languages, and I think it's very helpful.

# Miscellaneous code tips

In F#, you typically want to avoid writing if-elif-else chains like you did here:

if state.HasFlag(squareState.Bombarded) && state.HasFlag(squareState.Ship) then
'X'
elif state.HasFlag(squareState.Bombarded) then
'O'
elif state.HasFlag(squareState.Ship) then
'S'
else
' '


Instead of doing the above, you can use F# pattern matching using match. F# also provides a when clause that can be used in pattern matching to provide a condition for each pattern. If we use both of these things, the above piece of code becomes this:

match state with
| state when state.HasFlag(squareState.Bombarded) && state.HasFlag(squareState.Ship) -> 'X'
| state when state.HasFlag(squareState.Bombarded) -> 'O'
| state when state.HasFlag(squareState.Ship) -> 'S'
| _ -> ' '


Loops, especially for loops, are also generally something you want to avoid unless they're absolutely necessary. In many cases, for loops can be shortened down to a function being mapped over a range, or something similar.

In most cases, it's not necessary to explicitly specify variable, parameter and return types. For example, if I had the following function:

let f (a: int) (b: int): int =
...


It could be re-written as this:

let f a b =
...
`

As long as your variable names are good enough and your code is written clearly, you don't need to specify types. In fact - it often makes your code look less cluttered and more readable.