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.