Connect elements of a list to elements of an other list using a two-dim array

Story:

I build a kind of labyrinth. This labyrinth is divided in seven steps. You start with the first, then second, and so on to the seventh. You cannot go back to a previous step. Each step contains 3 to 5 rooms. Every room of a step is connected to at least one room of the next step. As well, every room of a step is connected to at least one room of the previous one. No hallway (connection between rooms) can cross another hallway. No room can have more than 3 source-rooms, neither more than 3 destination-rooms.

Implementation:

My point is to create a matrix (two-dim array) which depict the connection of a step to its successor. Rows represent the rooms of the source step, and columns the destination step. As I want to practice it, F# is required.

Decisions:

The matrix will only contains 3 values:
- M[i,j] = 1 means that source-room #i is connected to destination-room #j
- M[i,j] = 0 means that source-room can not be connected to destination-room
- M[i,j] = -1 means that source-room can be connected (but is not) to destination-room

Constraints:

1. Because hallways cannot be crossed, first source-room is imperatively connected to the first destination-room ; same for last rooms.
2. Because rooms can not have more than three destination-room, the first source-room can only be connected to the three first destination-rooms, and the last destination-room can only be connected to the three last source-rooms.

Code:

module MapConnections =
let IsUncertain array row col =
Array2D.get array row col = -1

let IsDisconnected array row col =
Array2D.get array row col = 0

let IsConnected array row col =
Array2D.get array row col = 1

let ListUncertain array =
let mutable list : (int*int) list = list.Empty
for i  in 0 .. Array2D.length1 array - 1 do
for j in 0 .. Array2D.length2 array - 1 do
if IsUncertain array i j then
list <- list @ [(i,j)]
list

let ListDisconnected array =
let mutable list : (int*int) list = list.Empty
for i  in 0 .. Array2D.length1 array - 1 do
for j in 0 .. Array2D.length2 array - 1 do
if IsDisconnected array i j then
list <- list @ [(i,j)]
list

let ListConnected array =
let mutable list : (int*int) list = list.Empty
for i  in 0 .. Array2D.length1 array - 1 do
for j in 0 .. Array2D.length2 array - 1 do
if IsConnected array i j then
list <- list @ [(i,j)]
list

let CountUncertain array =
ListUncertain array |> Seq.length<int*int>

let CountDisconnection array =
ListDisconnected array |> Seq.length<int*int>

let CountConnection array =
ListConnected array |> Seq.length<int*int>

let Disconnect array row col =
if IsUncertain array row col then
Array2D.set array row col 0
IsDisconnected array row col

// Check no-cross rule
let Connect array row col =
if IsUncertain array row col then
Array2D.set array row col 1
// Disconnect all 'top-right' connections
for i in 0 .. row - 1 do
for j in col + 1 .. Array2D.length2 array - 1 do
Disconnect array i j |> ignore
// Disconnect all 'bottom-left' connections
for i in row + 1 .. Array2D.length1 array - 1 do
for j in 0 .. col - 1 do
Disconnect array i j |> ignore
IsConnected array row col

// Check no-more-than-three rule
let Create rows cols =
let matrix = Array2D.create rows cols -1
Connect matrix 0 0 |> ignore
Connect matrix (rows - 1) (cols - 1) |> ignore
for i in 3 .. rows - 1 do
Disconnect matrix i 0 |> ignore
for i in 0 .. rows - 4 do
Disconnect matrix i (cols - 1) |> ignore
for j in 3 .. cols - 1 do
Disconnect matrix 0 j |> ignore
for j in 0 .. cols - 4 do
Disconnect matrix (rows - 1) j |> ignore
matrix

What I want to be sure:

I want to follow the F# conventions. For example, if lists are non-mutable, I presume that a mutable list is something to avoid?

I'm not sure, I understand what the purpose of your code is, so here are some general thoughts:

You have 3 identical functions except for a predicate:

let ListUncertain array =
let mutable list : (int*int) list = list.Empty
for i  in 0 .. Array2D.length1 array - 1 do
for j in 0 .. Array2D.length2 array - 1 do
if IsUncertain array i j then
list <- list @ [(i,j)]
list

let ListDisconnected array =

let ListConnected array =

So a generalization is appropriate:

let toFilteredList predicate array =
let mutable list : (int*int) list = list.Empty
for i  in 0 .. Array2D.length1 array - 1 do
for j in 0 .. Array2D.length2 array - 1 do
if predicate array i j then
list <- list @ [(i,j)]
list

which then could be called from each specialized function like:

let ListUncertain array = array |> toFilteredList IsUncertain

etc.

Building a list by repeated concatenations of single item lists is rather expensive and in general in functional programming mutable objects should be avoided:

list <- list @ [(i,j)]

Instead it may be better to use higher order functions like:

let toSeq<'a> = Seq.cast<'a>

let filterBy cellType array =
array
|> Array2D.mapi (fun r c x -> (r, c, x))
|> toSeq<int*int*int>
|> Seq.where (fun (r, c, x) -> cellType = x)
|> Seq.map (fun (r, c, _) -> (r, c))

where cellType is -1, 0 or 1 and then call it as:

let ListUncertain array = array |> filterBy -1

As an alternative you can "yield" a sequence like:

let filterBy predicate array =
seq {for i  in 0 .. Array2D.length1 array - 1 do
for j in 0 .. Array2D.length2 array - 1 do
if predicate array i j then
yield (i,j)}

which is maybe a better solution?

Overall I think I would use a discriminated union type instead of -1, 0, 1 as cell types:

type CellType =
| Uncertain
| Disconnected
| Connected

let getAt array row col = Array2D.get array row col
let setAt array row col value = Array2D.set array row col value

let IsUncertain array row col = Uncertain = getAt array row col

let IsDisconnected array row col = Disconnected = getAt array row col

let IsConnected array row col = Connected = getAt array row col

let filterBy predicate array =
seq {for i  in 0 .. Array2D.length1 array - 1 do
for j in 0 .. Array2D.length2 array - 1 do
if predicate array i j then
yield (i,j)}

let ListUncertain array = array |> filterBy IsUncertain

let ListDisconnected array = array |> filterBy IsDisconnected

let ListConnected array = array |> filterBy IsConnected

let CountUncertain array = ListUncertain array |> Seq.length

let CountDisconnection array = ListDisconnected array |> Seq.length

let CountConnection array = ListConnected array |> Seq.length

let Disconnect array row col =
match getAt array row col with
| Uncertain ->
setAt array row col Disconnected
true
| Connected -> false
| Disconnected -> true

// Check no-cross rule
let Connect array row col =
if IsUncertain array row col then
setAt array row col Connected
// Disconnect all 'top-right' connections
for i in 0 .. row - 1 do
for j in col + 1 .. Array2D.length2 array - 1 do
Disconnect array i j |> ignore
// Disconnect all 'bottom-left' connections
for i in row + 1 .. Array2D.length1 array - 1 do
for j in 0 .. col - 1 do
Disconnect array i j |> ignore
IsConnected array row col

// Check no-more-than-three rule
let Create rows cols =
let matrix = Array2D.create rows cols Uncertain
Connect matrix 0 0 |> ignore
Connect matrix (rows - 1) (cols - 1) |> ignore
for i in 3 .. rows - 1 do
Disconnect matrix i 0 |> ignore
for i in 0 .. rows - 4 do
Disconnect matrix i (cols - 1) |> ignore
for j in 3 .. cols - 1 do
Disconnect matrix 0 j |> ignore
for j in 0 .. cols - 4 do
Disconnect matrix (rows - 1) j |> ignore
matrix

The most significant improvement is, that there are no "magic numbers" left in the code - they are replaced with descriptive union types.

There may be other - smarter - ways to do it all, but this is what I can contribute with.