American Checkers

Question

I am implementing the logic for a Checkers game in F#. I am writing my code in a library so it can be called from any UI provider, and am trying to do it in good FP style. I currently have the following code; each file is provided in the order of compilation:

Checkers.fs This contains some unions and records that will be used throughout the entire library.

type Player = Black | White

type PieceType = Checker | King

type Coord = {
    Row :int
    Column :int
} with
    static member (+) (coord1 :Coord, coord2 :Coord) =
        {Row = coord1.Row + coord2.Row; Column = coord1.Column + coord2.Column}

Piece.fs This is an immutable class representing a Piece. It contains each option as a static member to ease building boards manually.

type Piece(player:Player, pieceType:PieceType) =
    member this.Player = player
    member this.PieceType = pieceType

    member this.Promote() =
        new Piece(player, PieceType.King)

    override this.Equals (obj) =
        let piece = obj :?> Piece
        piece.Player = this.Player &&
        piece.PieceType = this.PieceType

    override this.GetHashCode() =
        this.Player.GetHashCode() ^^^ this.PieceType.GetHashCode()

    static member WhiteChecker() =
        Some <| new Piece(Player.White, PieceType.Checker)

    static member BlackChecker() =
        Some <| new Piece(Player.Black, PieceType.Checker)

    static member WhiteKing() =
        Some <| new Piece(Player.White, PieceType.King)

    static member BlackKing() =
        Some <| new Piece(Player.Black, PieceType.King)

Board.fs This type represents a board, and the only stateful member of this class is immutable, like Piece. The second optional constructor is for ease of creating a board from a hard-coded list in C#; it may not remain in future versions.

type Board(board) =
    new () = Board(Board.DefaultBoard)

    new(board :IEnumerable<IEnumerable<Option<Piece>>>) =
        let boardArray = List.ofSeq(board.Select(fun r -> List.ofSeq(r)))
        Board(boardArray)

    member this.Board :Option<Piece> list list = board

    member this.Item
        with get(coord :Coord) =
            this.Board.[coord.Row].[coord.Column]

    member this.Item
        with get(row :int) =
            this.Board.[row]

    static member DefaultBoard :Option<Piece> list list =
        [
            [None; Piece.BlackChecker(); None; Piece.BlackChecker(); None; Piece.BlackChecker(); None; Piece.BlackChecker()];
            [Piece.BlackChecker(); None; Piece.BlackChecker(); None; Piece.BlackChecker(); None; Piece.BlackChecker(); None];
            [None; Piece.BlackChecker(); None; Piece.BlackChecker(); None; Piece.BlackChecker(); None; Piece.BlackChecker()];
            [None; None; None; None; None; None; None; None];
            [None; None; None; None; None; None; None; None];
            [Piece.WhiteChecker(); None; Piece.WhiteChecker(); None; Piece.WhiteChecker(); None; Piece.WhiteChecker(); None];
            [None; Piece.WhiteChecker(); None; Piece.WhiteChecker(); None; Piece.WhiteChecker(); None; Piece.WhiteChecker()];
            [Piece.WhiteChecker(); None; Piece.WhiteChecker(); None; Piece.WhiteChecker(); None; Piece.WhiteChecker(); None];
        ];

FSharpExtensions.fs This module contains many functions for internal use only. Most of these functions are designed to be based on a certain type to make calling them easier; perhaps they should be included in the type rather than being extensions like this?

module FSharpExtensions =

    let internal getJumpedCoord(startCoord, endCoord) =
        {Row = startCoord.Row - Math.Sign(startCoord.Row - endCoord.Row); Column = startCoord.Column - Math.Sign(startCoord.Column - endCoord.Column)}

    let internal checkMoveDirection(piece :Piece, startCoord :Coord, endCoord :Coord) =
        match piece.PieceType with
        | PieceType.Checker ->
            match piece.Player with
            | Player.Black -> startCoord.Row < endCoord.Row
            | Player.White -> startCoord.Row > endCoord.Row
        | PieceType.King -> true

    let internal moveIsDiagonal(startCoord :Coord, endCoord :Coord) =
        startCoord <> endCoord &&
        System.Math.Abs(startCoord.Row - endCoord.Row) = System.Math.Abs(startCoord.Column - endCoord.Column)

    let internal kingRowIndex(player) =
        match player with
        | Player.Black -> 7
        | Player.White -> 0

    type Board with
        member internal board.CoordExists(coord :Coord) =
            coord.Row > 0 && coord.Row < board.Board.Length &&
            coord.Column > 0 && coord.Column < board.Board.[0].Length

        member internal board.IsValidCheckerHop(startCoord :Coord, endCoord :Coord) =
            let piece = board.[startCoord].Value

            checkMoveDirection(piece, startCoord, endCoord) &&
            board.[endCoord].IsNone

        member internal board.IsValidKingHop(startCoord :Coord, endCoord :Coord) =
            board.[endCoord].IsNone

        member internal board.IsValidCheckerJump(startCoord :Coord, endCoord :Coord) =
            let piece = board.[startCoord].Value

            let jumpedCoord = getJumpedCoord(startCoord, endCoord)
            let jumpedPiece = board.[jumpedCoord]

            checkMoveDirection(piece, startCoord, endCoord) &&
            board.[endCoord].IsNone &&
            jumpedPiece.IsSome &&
            jumpedPiece.Value.Player <> piece.Player

        member internal board.IsValidKingJump(startCoord :Coord, endCoord :Coord) =
            let piece = board.[startCoord].Value

            let jumpedCoord = getJumpedCoord(startCoord, endCoord)
            let jumpedPiece = board.[jumpedCoord]

            board.[endCoord].IsNone &&
            jumpedPiece.IsSome &&
            jumpedPiece.Value.Player <> piece.Player

        member internal board.IsValidHop(startCoord :Coord, endCoord :Coord) =
            match board.[startCoord].Value.PieceType with
            | PieceType.Checker -> board.IsValidCheckerHop(startCoord, endCoord)
            | PieceType.King -> board.IsValidKingHop(startCoord, endCoord)

        member internal board.IsValidJump(startCoord :Coord, endCoord :Coord) =
            match board.[startCoord].Value.PieceType with
            | PieceType.Checker -> board.IsValidCheckerJump(startCoord, endCoord)
            | PieceType.King -> board.IsValidKingJump(startCoord, endCoord)

        member internal board.SetPieceAt(coord :Coord, piece :Option<Piece>) =
            let boardItems = List.init 8 (fun row ->
                match row with
                | i when i = coord.Row ->
                    List.init 8 (fun col ->
                        match col with
                        | j when j = coord.Column -> piece
                        | _ -> board.[row].[col]
                    )
                | _ -> board.[row]
            )
            new Board(boardItems)

        member internal board.Jump(startCoord :Coord, endCoord :Coord) =
            let kingRowIndex = kingRowIndex(board.[startCoord].Value.Player)

            let piece =
                match endCoord.Row with
                | row when row = kingRowIndex -> Some <| board.[startCoord].Value.Promote()
                | _ -> board.[startCoord]

            let jumpedCoord = getJumpedCoord(startCoord, endCoord)

            board.SetPieceAt(startCoord, None).SetPieceAt(endCoord, piece).SetPieceAt(jumpedCoord, None)

        member internal board.Hop(startCoord :Coord, endCoord :Coord) =
            let kingRowIndex = kingRowIndex(board.[startCoord].Value.Player)

            let piece =
                match endCoord.Row with
                | row when row = kingRowIndex -> Some <| board.[startCoord].Value.Promote()
                | _ -> board.[startCoord]

            board.SetPieceAt(startCoord, None).SetPieceAt(endCoord, piece)

ExtensionMethods.fs This is really the public API of my library. I designed the methods like this so they could be called as boardInstance.Member(...) in both C# and F#.

[<Extension>]
type ExtensionMethods() =

    [<Extension>]
    static member IsValidMove(board :Board, startCoord :Coord, endCoord :Coord) =
        board.CoordExists(startCoord) &&
        board.CoordExists(endCoord) &&
        board.[startCoord].IsSome &&
        moveIsDiagonal(startCoord, endCoord) &&
        match Math.Abs(startCoord.Row - endCoord.Row) with
        | 1 -> board.IsValidHop(startCoord, endCoord)
        | 2 -> board.IsValidJump(startCoord, endCoord)
        | _ -> false

    [<Extension>]
    static member Move(board :Board, startCoord :Coord, endCoord :Coord) :Option<Board> =
        match ExtensionMethods.IsValidMove(board, startCoord, endCoord) with
        | false -> None
        | true ->
            match Math.Abs(startCoord.Row - endCoord.Row) with
            | 1 -> Some <| board.Hop (startCoord, endCoord)
            | 2 -> Some <| board.Jump (startCoord, endCoord)
            | _ -> None

    [<Extension>]
    static member Move(board :Board, coordinates :IEnumerable<Coord>) =
        let coords = List.ofSeq(coordinates)

        match coords.Length with
        | b when b >= 3 ->
            let newBoard = ExtensionMethods.Move (board, coords.Head, coords.[1])
            ExtensionMethods.Move (newBoard, coords.Tail)
        | _ -> ExtensionMethods.Move (board, coords.Head, coords.[1])

    static member internal Move(board :Option<Board>, coordinates :IEnumerable<Coord>) =
        match board.IsSome with
        | false -> None
        | true -> ExtensionMethods.Move(board.Value, coordinates)

Any and all comments welcome. If you see something that I can improve, or that I am not doing something the idiomatic F# way, please let me know.

Answer 1

One of the many benefits of F# is that it's a multiparadigmatic language; while it embraces a functional-first ideal, it clearly also enables you to write object-oriented code. This is useful if you're coming from a C# background, like I did some years ago. You can get started quickly writing F#, concentrating on learning the language syntax. Naturally, if you do that, you'd tend to start your F# journey writing F# in an object-oriented style. There's nothing wrong with that; it's part of the voyage.

It looks like you've already made an effort to make your F# code immutable, which is an important step in the right direction. In general, it's looking good.

You also use the word idiomatic F#, and that opens another discussion. Most importantly, what's idiomatic has a subjective component. Still, when I write F# code these days, my code is mostly assembled from functional types (records, discriminated unions, lists, tuples) and let-bound functions. Most of the code I've seen from other seasoned F# programmers seem to follow that pattern as well. With that in mind, here are some suggestions that would, in my opinion, make the code more idiomatic.

Use functional types

You already start by declaring the two record types Player and PieceType, and that's a good start, but why make Coord a class? You can make it a record, too:

type Coord = { Row :int; Column :int }

You can still support addition:

let (+) coord1 coord2 =
    { Row = coord1.Row + coord2.Row; Column = coord1.Column + coord2.Column }

Notice how type annotations aren't required. Since this function reads from Row and Column labels, the compiler can infer that both coord1 and coord2 are Coord values.

The + function still works, as this FSI session demonstrates:

> { Row = 1; Column = 4 } + { Row = 2; Column = 3 };;
val it : Coord = {Row = 3; Column = 7;}

In the same spirit, it's easy to refactor Piece to a record and associated functions:

type Piece = { Player : Player; PieceType : PieceType }

let promote p = { p with PieceType = King }

let whiteChecker = Some { Player = White; PieceType = Checker }

let blackChecker = Some { Player = Black; PieceType = Checker }

let whiteKing    = Some { Player = White; PieceType = King }

let blackKing    = Some { Player = Black; PieceType = King }

F#'s functional types all have structural equality, so you can see how this approach saves you from having to override Equals and GetHashCode.

Here, I also converted the 'factory' methods whiteChecker, blackKing, and so on, to values. The original functions always returned the same value, so I didn't see any reason to make them functions.

Use built-in types

The Board class is little but a wrapper around Piece option list list, so it can be eliminated. It can sometimes be useful to define a type alias:

type Board = Piece option list list

It can help you better communicate intent, but it doesn't preclude a user from providing a 'raw' Piece option list list value. This keeps things more flexible.

The only behaviour defined by Board are the two Item properties and the default board, all of which can easily be defined as let-bound values:

let row = List.item

let square coord = List.item coord.Row >> List.item coord.Column

Notice how row is nothing but an alias for List.item. Likewise, square is a composition of List.item functions. These functions are actually much more generic than the ones defined in the Board class, but they work correctly with a board as well.

You could define the default board like above, but perhaps you'll find the following more readable:

let defaultBoard = 
    [
        List.replicate 4 [None; blackChecker] |> List.concat
        List.replicate 4 [blackChecker; None] |> List.concat
        List.replicate 4 [None; blackChecker] |> List.concat
        List.replicate 8 None
        List.replicate 8 None
        List.replicate 4 [whiteChecker; None] |> List.concat
        List.replicate 4 [None; whiteChecker] |> List.concat
        List.replicate 4 [whiteChecker; None] |> List.concat
    ]

Code readability is subjective, but this is both shorter, and explicitly highlights the repetitive nature of the default board. On the other hand, as a reader, you can't 'see' the whole board laid out in the code.

In any case, you can get a row from the default board:

> row 2 defaultBoard;;
val it : Piece option list =
  [null; Some {Player = Black; PieceType = Checker;};
   null; Some {Player = Black; PieceType = Checker;};
   null; Some {Player = Black; PieceType = Checker;};
   null; Some {Player = Black; PieceType = Checker;}]

You can also get a single square:

> square { Row = 2; Column = 1 } defaultBoard;;
val it : Piece option = Some {Player = Black; PieceType = Checker;}

As far as I can tell, you could convert all the extension methods in FSharpExtensions to let-bound functions as well, but I think I'll conclude my review here.

C# interop

My general preference, if I need to expose an F# library to C# is to write the F# as idiomatically as possible. This means that I'll make no concessions to C# when writing my implementation.

Once I know what my F# implementation looks like, I can always slap an object-oriented Facade over the F# code, if necessary.

Some functional types, like records and sequences are easily consumable from C#, since they're simply immutable classes and IEnumerable<T> sequences, but other types, like discriminated unions, require more translation in order to look object-oriented.