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

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)

0


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
0


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

• Very good. snd >> (=) 0 was unexpected. I need to train a lot to get this kind of simplicity that F# offers. – Gabriel Dec 3 '16 at 2:20

In F# we prefer match over if:

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


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. :)

• I'd definitely NOT match on simple booleans. – CaringDev Dec 2 '16 at 8:55
• @CaringDev Personally, I use match on simple booleans only because it forces me to account for all possible outcomes. I can cheat and abuse the procedural portions of F# by simply using if someBooleanCheck and then omit the else. You can almost always avoid if construct in F#. Also: stackoverflow.com/questions/7986641/… – Der Kommissar Dec 6 '16 at 19:52