2
\$\begingroup\$

I am looking for the elements that are zeroes in a square matrix (of size n), as a list of pair. I don't really like the following code, some condition seems rendundant but my knowledge of OCaml is limited and I can't find an elegant way to refactor it:

let find_zeroes input_matrix n =
    let rec aux i j n =
        if(i == n) then []
        else begin
            if(input_matrix.(i).(j) == 0) then begin
                if(j < n-1) then (i,j)::(aux i (j+1) n)
                else (i,j)::(aux (i+1) 0 n)
            end else begin
                if(j < n-1) then (aux i (j+1) n)
                else (aux (i+1) 0 n)
            end
        end
    in aux 0 0 n
;;

Actually, the n arugment is optional:

let find_zeroes input_matrix =
    let rec aux i j n =
        if(i == n) then []
        else begin
            if(input_matrix.(i).(j) == 0) then begin
                if(j < n-1) then (i,j)::(aux i (j+1) n)
                else (i,j)::(aux (i+1) 0 n)
            end else begin
                if(j < n-1) then (aux i (j+1) n)
                else (aux (i+1) 0 n)
            end
        end
    in aux 0 0 (Array.length input_matrix)
;;
\$\endgroup\$

1 Answer 1

2
\$\begingroup\$

I would try to decouple the idea of traversing the matrix to collect information about its content and the actual definition of find_zeros. This way you can reuse the same traversal to implement other functions too.

This leads to something like this (I don't assume that the matrix is a square one): indexedTraversal takes a function add and an initial value ini for the accumulator we will use when traversing the matrix mat. add updates the accumulator given the position of the current cell and its content.

type 'a matrix = 'a array array

let indexedTraversal
    (add : int -> int -> 'a -> 'b -> 'b)
    (ini : 'b)
    (mat : 'a matrix)
    : 'b =
  let m = Array.length mat     in
  let n = Array.length mat.(0) in
  let rec aux (i : int) (j : int) (acc : 'b) =
    let acc' = add i j mat.(i).(j) acc in
         if j < n - 1 then aux i (j + 1) acc'
    else if i < m - 1 then aux (i + 1) 0 acc'
    else acc'
  in aux 0 0 ini

(nota: I don't check that m > 0 here so Array.length mat.(0) might raise an error. You can (and should!) add the test to handle that edge case)

You can then implement find_zeros by defining an appropriate testElt and calling indexedTraversal with the empty list as the inital accumulator. Here I call List.rev because otherwise the result is actually the reverse of what you had implemented. If you don't care about the order in which the elements are listed, you can just do away with it.

let find_zeros (m : int matrix) : (int * int) list =
  let testElt i j x ijs = if x == 0 then (i,j)::ijs else ijs
  in List.rev (indexedTraversal testElt [] m)

We can try it on a simple example and it works:

utop # find_zeros [| [|0;1|]; [|1;0|]|];;
- : (int * int) list = [(0, 0); (1, 1)]    
\$\endgroup\$
2
  • \$\begingroup\$ Thank you ! Side question, what is the point of specifying the types of the variables in OCaml since everything is resolved at compile time ? \$\endgroup\$
    – RUser4512
    Mar 19, 2016 at 14:53
  • 1
    \$\begingroup\$ @RUser4512 In my daily work I tend to use type systems where type inference is not possible so I am used to writing the types first and then implementing the function. It's not needed in OCaml however it helps me structure my thoughts and (hopefully) makes my intent clearer to the reader so I do it anyway. \$\endgroup\$
    – gallais
    Mar 19, 2016 at 15:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.