Probabilistic Matrix Inspection - Suggested by a paper, implemented by me

Question

I have read this paper and I actually found it interesting.

This is an attempt to implement the proposed algorithm. I would like to know:

• Is my algorithm correct by what is discribed in the paper?
• Is my algorithm easy to understand?

Here is my little program

// Based on http://www.ijcai.org/Proceedings/16/Papers/053.pdf
//
// The paper uses two matrices, but I decided to "join" them into 1 matrix of 
// tuples. Things are easier this way (isn't it a valid reason?).
//
// A matrix is a list of lists, but...
//
// It is not like you would expect.
//
// Each inner list represents a column, not a row!
//
// A "standard" visualization of a matrix is:
//        column1  column2  column3
//  row1 (1,  90) (1,  10) (0,  90)
//  row2 (0,   0) (1, 100) (1,  40)
//  row3 (0,  10) (1,  80) (1, 100)
//
// In my program it is seen as:
//           row1        row2        row3
//  colum1 (1,  90)    (0,   0)    (0,  10)
//  colum2 (1,  10)    (1, 100)    (1,  80)    
//  colum3 (0,  90)    (1,  40)    (1, 100)
//
// It is made this way because, in this specific case, it is easier to go 
// recursively in a list of columns.

let exampleMatrix = [
    [1,  90;    0,   0;    0,  10]

    [1,  10;    1, 100;    1,  80]

    [0,  90;    1,  40;    1, 100]
]

let optimalColumnOrderOf matrix =
    let sumProbabilities column =
        column
        |> List.map (fun (_, q) -> q)
        |> List.reduce (+)

    let comparator column1 column2 =
        let sum1 = sumProbabilities column1
        let sum2 = sumProbabilities column2

        sum2 - sum1

    matrix
    |> List.sortWith comparator

let thereIsZeroProbabilityIn column =
    List.exists (fun (_, q) -> q = 0) column

let optimalRowOrderOf column =
    let comparator (_, q1) (_, q2) =
        q2 - q1

    column
    |> List.sortWith comparator

let isColumnFeaseble column =
    let thereIsZeroIn c =
        c
        |> optimalRowOrderOf
        |> List.exists (fun (n, _) -> n = 0)

    if thereIsZeroProbabilityIn column then false
    else 
        column
        |> List.filter (fun (_, q) -> q < 100)
        |> thereIsZeroIn
        |> not

let isMatrixFeaseble matrix =
    matrix
    |> optimalColumnOrderOf
    |> List.exists isColumnFeaseble

[<EntryPoint>]
let main argv =
    printf "%O" (isMatrixFeaseble exampleMatrix)

    System.Console.ReadKey() |> ignore

    0

Answer 1

Lets first look at the code:

let sumProbabilities column =
    column
    |> List.map (fun (_, q) -> q)
    |> List.reduce (+)

is almost equivalent (does not throw on empty list but returns 0) to

let sumProbabilities = List.sumBy snd

such that optimalColumnOrderOf becomes

let optimalColumnOrderOf =
    let sumProbabilities = List.sumBy snd
    let comparator c1 c2 =
        let sum1 = sumProbabilities c1
        let sum2 = sumProbabilities c2
        sum2 - sum1
    List.sortWith comparator

Personally I like leaving out the parameter (a.k.a. eta-conversion) to facilitate moving functions around (as we'll be doing shortly). This is a disputed topic, however.

Similarly, thereIsZeroProbabilityIn can be rewritten:

let thereIsZeroProbabilityIn = List.exists (snd >> (=) 0)

which reads nicely as "there exists a tuple such that the second element equals zero".

Then, using the fact that sorting lists does not change the elements, i.e. the outcome of exists, get rid of all sorting

let thereIsZeroProbabilityIn = List.exists (snd >> (=) 0)

let isColumnFeasible column =
    let thereIsZeroIn =
        List.exists (fun (n, _) -> n = 0)

    if thereIsZeroProbabilityIn column then false
    else 
        column
        |> List.filter (fun (_, q) -> q < 100)
        |> thereIsZeroIn
        |> not

let isMatrixFeasible =
    List.exists isColumnFeasible

and applying logical equivalences if a then false else b = not a && b, not exists p = forall not p and not(a && b) = not a || not b as well as combining filter x and exists y into exists (x && y):

let thereIsNoZeroProbabilityIn = List.forall (snd >> (<>) 0)

let isColumnFeasible column =
    let thereIsNoZeroIn =
        // not << (List.exists (fun (n, q) -> n = 0 && q < 100))
        // List.forall (fun (n, q) -> not(n = 0 && q < 100))
        List.forall (fun (n, q) -> n <> 0 || q >= 100)

    thereIsNoZeroProbabilityIn column && thereIsNoZeroIn column

combining the foralls

let isColumnFeasible =
    List.forall (fun (n, q) -> (n <> 0 || q >= 100) && q <> 0)

let isMatrixFeasible =
    List.exists isColumnFeasible

we arrive at "a matrix is feasible when there exists a feasible column, i.e. a column containing no significant zeros" (significant = q < 100).

Finally, use "%b" to print bools and _ for unused args:

[<EntryPoint>]
let main _ =
    printf "%b" <| isMatrixFeasible exampleMatrix
    System.Console.ReadKey() |> ignore
    0

Whether that's equivalent to the paper, I don't know. For sure it is easier to understand than the original version.

Answer 2

In F# we prefer match over if:

if thereIsZeroProbabilityIn column then false
else 
    column
    |> List.filter (fun (_, q) -> q < 100)
    |> thereIsZeroIn
    |> not

Should, instead, be:

match thereIsZeroProbabilityIn column with
| true -> false
| false ->
    column
    |> List.filter (fun (_, q) -> q < 100)
    |> thereIsZeroIn
    |> not

In the case where you're only piping to one other function, you should stay consistent with whether you inline the pipe or not:

 System.Console.ReadKey() |> ignore

and

column
|> List.sortWith comparator

Are inconsistent, generally speaking I prefer to inline the pipe when there is only one pipe happening. (It seems to make be more readable that way.)

column |> List.sortWith comparator

You reduce LoC and make use of the horizontal spacing.

let comparator column1 column2 =
    let sum1 = sumProbabilities column1
    let sum2 = sumProbabilities column2

    sum2 - sum1

In that case you should not be using the local constants, they only create overhead on the stack, they're not used more than once, and they're not cached, so in reality they provide no additional value.

let comparator column1 column2 =
    (sumProbabilities column2) - (sumProbabilities column1)

Again, reduce vertical space a little.

Other than this, I have nothing else to say about the code except maybe to shorten some of the names. It's awful verbose. It's good F# already, my modifications are merely recommendations. Good work. :)