Is this Bridges code F# idiomatic?

Question

Introduction

I'm primarily a C# programmer, just starting out with learning F#. I found myself with a problem which felt like it was appropriate for a functional language, and now that I have the first module in place, I want to get a review before ploughing on

Problem Statement

The game Bridges works as follows:

• The board is an NxM grid of locations
• Each location can (but doesn't have to) contain an island which has a number written on it
• Each island can also be connected horizontally or vertically to an adjacent island by a bridge. The adjacent island can be any distance, as long as it is directly along a compass direction.
• There can be at most two bridges connecting a pair of islands, and bridges may not cross
• The aim of the game is to draw bridges such that every island has a number of bridges connected to it equal to the number written on it. Additionally, every island must be reachable from every other island by the network of bridges.

                                                        

The ultimate aim of the program will be to have a Bridges solver, which can take any board and solve it by applying some algorithms and using a tree search where it can't work out a certain next move. But what I'm including for this review is just the core module, which defines the relevant types and provides the basic functions needed to interact with the game.

The Code

module Core

let MaxBridgesInConnection = 2

type Island = {
    Position : int * int
    Required : int
}

type Connection = {
    Origin : Island
    Destination : Island
    Bridges : int
}

type Board = {
    Islands : Island list
    Connections : Connection list
}

let PointBetween start finish (X, Y) =
    let between a b x =
        (x >= a && x <= b) || (x <= a && x >= b)
    match start, finish with
    | (0, startY), (0, finishY) -> between startY finishY Y
    | (startX, 0), (finishX, 0) -> between startX finishX X
    | _ -> failwith "Between must be used for a horizontal or vertical line"

let Cross a b =
    match (a.Origin.Position, a.Destination.Position, b.Origin.Position, b.Destination.Position) with 
    | (aOrig, aDest, bOrig, bDest) -> 
        PointBetween aOrig aDest bOrig
        && PointBetween aOrig aDest bDest
        && PointBetween bOrig bDest aOrig
        && PointBetween bOrig bDest aDest

let IslandConnections board island =
    board.Connections
    |> List.filter (fun con -> con.Origin = island || con.Destination = island)
    |> Set.ofList

let RemainingBridges board island =
    let connections = 
        IslandConnections board island
        |> Set.count
    island.Required - connections

let CanAddBridges board connection count =
    let blockedBy other =
        other.Bridges > 0 && Cross connection other
    connection.Bridges + count - 1 < MaxBridgesInConnection
    && (List.exists blockedBy board.Connections |> not)

let AddBridge board connection =
    if CanAddBridges board connection 1 |> not then failwith "Tried to add invalid bridge"

    let incrementMatching candidate =
        if candidate=connection 
        then { connection with Bridges = connection.Bridges + 1 } 
        else connection
    { board with Connections = List.map incrementMatching board.Connections }

let IncompleteIslands board =
    let incomplete island =
        IslandConnections board island
        |> Seq.sumBy (fun connection -> connection.Bridges)
        |> (>) island.Required
    board.Islands
    |> List.filter incomplete

let ConnectedTo board island =
    let otherEnd island connection =
        match connection with
        | { Bridges = 0 } -> None
        | { Origin = orig; Destination = dest } when orig = island -> Some(dest)
        | { Origin = orig; Destination = dest } when dest = island -> Some(orig)
        | _ -> None
    let allConnectedTo island =
        board.Connections |> List.choose (otherEnd island)
    let rec loop islands seen =
        match islands with
        | head::tail when Set.contains head seen -> loop tail (seen.Add head)
        | head::tail -> loop (tail@(allConnectedTo head)) (seen.Add head)
        | [] -> seen
    loop [ island ] Set.empty

let Connected board =
    ConnectedTo board board.Islands.[0]
    |> Set.count
    |> (=) board.Islands.Length

let Finished board =
     IncompleteIslands board |> List.isEmpty
     && Connected board

Notes

As I said, I'm just starting out, so a lot of what I'm looking for is basic code-style stuff. That's with a particular focus on writing idiomatic F# code, but at the same time I'm aware that it's possible that I'm over-compensating and- for example- putting functions at the module level that really should be members on a type. I'm also interested in any advice relating to encapsulation.

As for the design, I always find myself having a lot of trouble when trying to deal with something that needs to be thought of as both a graph (checking all islands are connected) and as having an actual physical location (bridges can't cross) at the same time. This design is the best way I could come up with for this particular problem, after some false starts, but I'd be happy to hear high-level alternatives. If it's not clear, a Board should already have all possible Connections at all times; when a bridge is added, the Bridges field for the Connection will be incremented. Creation of boards from just a list of islands will be handled by another module

Answer 1

This design is the best way I could come up with for this particular problem, after some false starts, but I'd be happy to hear high-level alternatives.

Let's explore what this would look like with an adjacency-list representation of the graph. Apologies for any errors I introduce along the way.

One motivating factor is that a lot of operations that we do are local, not global -- we're often just interested in the neighbours of a particular island.

First let's change the data types:

type Island = {
    Position : int * int
    Required : int
}

type Connection = {
    Origin : Island
    Destination : Island
    Bridges : int
}

type Board = {
    Islands : Island list
    Connections : Connection list
}

type Island = {
    Position : int * int
    Required : int
    Connections : Map<Island, int>
}

type Board = {
    Islands : Island list
}

There are other possible choices for Map<Island, int>, but let's stick with this for now.

The original definition of RemainingBridges looks a bit off:

let IslandConnections board island =
    board.Connections
    |> List.filter (fun con -> con.Origin = island || con.Destination = island)
    |> Set.ofList

let RemainingBridges board island =
    let connections = 
        IslandConnections board island
        |> Set.count
    island.Required - connections

I think it's counting the number of connections, when it should be counting bridges. Assuming the logic of the original is correct, we can rewrite it as

let RemainingBridges (island : Island) =
    island.Required - (Seq.length island.Connections)

Or if we're supposed to count bridges,

let RemainingBridges (island : Island) =
    island.Required - Seq.sumBy snd (Map.toSeq island.Connections)

We can use RemainingBridges to simplify IncompleteIsland

let IncompleteIslands board =
    let incomplete island =
        IslandConnections board island
        |> Seq.sumBy (fun connection -> connection.Bridges)
        |> (>) island.Required
    board.Islands
    |> List.filter incomplete

let IncompleteIslands (board : Board) =
    List.filter (fun island -> RemainingBridges island > 0) board.Islands

At this point we can remove IslandConnections altogether.

Next up is ConnectedTo. Here's a good example of us being interested in local operations -- we can remove the board parameter.

let ConnectedTo (island : Island) =
    let allConnectedTo (island : Island) =
        island.Connections |> Map.toList |> List.map fst
    let rec loop islands seen =
        match islands with
        | head::tail when Set.contains head seen -> loop tail (seen.Add head)
        | head::tail -> loop (tail@(allConnectedTo head)) (seen.Add head)
        | [] -> seen
    loop [island] Set.empty

Which leads to

let Connected (board : Board) =
    board.Islands.Length = Set.count (ConnectedTo board.Islands.[0])

The remaining functions don't look as nice as I would like them to. I'll post them here for completeness, but there are (hopefully!) cleaner ways to express them.

let Bridges (island : Island) (other : Island) =
    match Map.tryFind other island.Connections with
    | Some n -> n
    | None -> 0

let Cross (aOrig : int * int) (aDest : int * int) (bOrig : int * int) (bDest : int * int) =
    PointBetween aOrig aDest bOrig
    && PointBetween aOrig aDest bDest
    && PointBetween bOrig bDest aOrig
    && PointBetween bOrig bDest aDest

let CanAddBridges board (a : Island) (b : Island) count =
    let blockedBy (d : Island) =
        Map.exists (fun c _ -> Cross a.Position b.Position c.Position d.Position) d.Connections
    Bridges a b + count - 1 < MaxBridgesInConnection
    && (List.exists blockedBy board.Islands |> not)

let AddBridge board islandA islandB =
    if CanAddBridges board islandA islandB 1 |> not then failwith "Tried to add invalid bridge"

    let addBridge (island : Island) (other : Island) =
        let bridges = Bridges island other
        { island with Connections = Map.add island (bridges + 1) island.Connections }

    let incrementMatching candidate =
        if candidate = islandA then addBridge candidate islandB
        else if candidate = islandB then addBridge candidate islandA
        else candidate
    { board with Islands = List.map incrementMatching board.Islands }

Answer 2

module Core

This sounds way too general to me. Unless this code is in a namespace that you're not showing here, you should use a more descriptive name.

---

type Connection = {
    Origin : Island
    Destination : Island
    Bridges : int
}

I don't like that you have undirected graph, but you're calling the edges Origin and Destination, as if the edge was directed. Though I'm not sure what would be a better solution: tuples are also ordered and creating a custom "unordered pair" type just for this is an overkill.

---

let PointBetween start finish (X, Y) =
    let between a b x =
        (x >= a && x <= b) || (x <= a && x >= b)
    match start, finish with
    | (0, startY), (0, finishY) -> between startY finishY Y
    | (startX, 0), (finishX, 0) -> between startX finishX X
    | _ -> failwith "Between must be used for a horizontal or vertical line"

I don't think this can work. Vertical line is not just a line that has both X coordinates zero, it's a line that has both X coordinates the same.

To fix the pattern, you could do something like:

match start, finish with
| (startX, startY), (finishX, finishY) when startX = finishX -> between startY finishY Y
| (startX, startY), (finishX, finishY) when startY = finishY -> between startX finishX X
| _ -> failwith "Between must be used for a horizontal or vertical line"

But that's not very nice and I think it would be better using if-elif-else:

let (startX, startY) = start
let (finishX, finishY) = finish

if startX = finishX then between startY finishY Y
elif startY = finishY then between startX finishX X
else failwith "Between must be used for a horizontal or vertical line"

---

match (a.Origin.Position, a.Destination.Position, b.Origin.Position, b.Destination.Position) with 
| (aOrig, aDest, bOrig, bDest) -> 

I don't think you should be using pattern matching like this. If you want to assign to multiple variables at the same time, you can use let:

let (aOrig, aDest, bOrig, bDest) =
    (a.Origin.Position, a.Destination.Position, b.Origin.Position, b.Destination.Position)

---

PointBetween aOrig aDest bOrig
&& PointBetween aOrig aDest bDest
&& PointBetween bOrig bDest aOrig
&& PointBetween bOrig bDest aDest

You could get rid of some of the duplication here by writing a list of tuples of the parameter combinations and then calling List.forall PointBetween:

[aOrig, aDest, bOrig; aOrig, aDest, bDest;
 bOrig, bDest, aOrig; bOrig, bDest, aDest] |>
    List.forall PointBetween

Though this requires that you declare PointBetween in tupled form:

let PointBetween(start, finish, (X, Y)) =

I have also considered generating the sequence of points, instead of hard-coding it, but the best I could figure out is:

[ for (con1, con2) in [a, b; b, a] do
  for v in [con2.Origin; con2.Destination] do
  yield (con1.Origin.Position, con1.Destination.Position, v.Position) ]

I think think makes the structure more obvious, but it's also more complicated, so it's probably the worse option.

---

IslandConnections board island
|> Seq.sumBy (fun connection -> connection.Bridges)
|> (>) island.Required

That |> (>) part looks confusing to me. I would probably write this as:

let existingConnections = 
    IslandConnections board island
    |> Seq.sumBy (fun connection -> connection.Bridges)
existingConnections > island.Required