[Caml-list] Compute the equivalence classes

[Ly Kim Quyen <lykimq@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 1588 bytes --]

Dear group,

I have an question about data structure and types. I have a function calculates
transitive closure of relation represented as an adjacency matrix

let trans_closure (m: 'a array array) : 'a array array =
  let last_cols = length m - 1 in
    for k = 0 to last_cols do
      for i = 0 to last_cols do
for j = 0 to last_cols do
  m.(i).(j) <- m.(i).(j) || (m.(i).(k) && m.(k).(j))
done;
      done;
  done;
  m
;;

(* transpose matrix A is the matrix A' formed by turning rows into
   columns and vice versa: (A')i,j = Aj,i.*)
let transpose (m: 'a array array) : 'a array array =
  let tc = trans_closure m in
  let last_cols = length m - 1 in
  for i = 0 to last_cols do
    for j = 0 to last_cols do
      tc.(j).(i) <- tc.(i).(j)
    done;
  done;
  tc
;;

I would like to compute equivalence classes, it is disjoint between matrix
transitive closure  and matrix transpose. I would like it returns for me a
new list with the type: list of list [[]]

I have a function convert 'a array array to 'a list list

let to_list (m : 'a array array) : 'a list list =
  List.map to_list (to_list m)

let eq_class (m: 'a array array) : 'a list list =
  let lst = length m - 1 in
      for i = 0 to lst do
for j = 0 to lst do
  let a = tc.(i).(j) && trans.(i).(j) in
            if a
            then
           ???

I'm stuck here, I don't know how I can add the result "a" into the new list
of list. I think I should create a new list with type 'a list list, but I
don't know where I should write it?

Thank you for helping me understand and give me some advises.

Best regards,
Gwen

[-- Attachment #2: Type: text/html, Size: 4703 bytes --]