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

Question

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?

Answer 1

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.