From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105]) by walapai.inria.fr (8.13.6/8.13.6) with ESMTP id p9VFamd4005749 for ; Mon, 31 Oct 2011 16:36:48 +0100 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AhsBAP2/rk7RVaE2kGdsb2JhbABChHeBSKJuCCIBAQEBCQkNBxQEIYILAg8dARsWCAMSAw03AiQBEQEFAVecFIJbCosMR4JghHU9iHACBQqHZIEUBIgEjAqNMz2DfA X-IronPort-AV: E=Sophos;i="4.69,432,1315173600"; d="scan'208";a="115863450" Received: from mail-fx0-f54.google.com ([209.85.161.54]) by mail4-smtp-sop.national.inria.fr with ESMTP/TLS/RC4-SHA; 31 Oct 2011 16:36:43 +0100 Received: by faar19 with SMTP id r19so11602534faa.27 for ; Mon, 31 Oct 2011 08:36:42 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=mime-version:from:date:message-id:subject:to:content-type; bh=jZkHalbSl222GKoEc4JSQz4XB12b4zlb8Vkp+tM7KYc=; b=poCEIS93t9IKShDFZ8hvng5kg++kjFP4I9kp90LDkzNJZQQ7k3RvvuNlwAbYACktVw GXNfnBzlkJDzbeeDf3DDP8b15r4Sg1cNSnIfcYHWHolGurfOKNK5KqnhU9jhgH0LVn1D vlbB9fdld7GIdECdryjMZvyXAi5xveVErE+lk= Received: by 10.223.61.138 with SMTP id t10mr30022838fah.20.1320075402333; Mon, 31 Oct 2011 08:36:42 -0700 (PDT) MIME-Version: 1.0 Received: by 10.223.104.143 with HTTP; Mon, 31 Oct 2011 08:36:01 -0700 (PDT) From: Ly Kim Quyen Date: Mon, 31 Oct 2011 23:36:01 +0800 Message-ID: To: caml-list@inria.fr Content-Type: multipart/alternative; boundary=001517402a6e6ed06204b09a0115 Subject: [Caml-list] Compute the equivalence classes --001517402a6e6ed06204b09a0115 Content-Type: text/plain; charset=UTF-8 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 --001517402a6e6ed06204b09a0115 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Dear group,

I have an question about data structure and types. I h= ave a function=C2=A0calculates transitive closure of relation represented as an=C2=A0<= /span>adjacency ma= trix

let trans_= closure (m: 'a array array) : 'a array array =3D
=C2=A0 let last_col= s =3D length m - 1 in
=C2=A0 =C2=A0 for k =3D 0 to last_cols do
=C2=A0 =C2=A0 =C2=A0 for i =3D 0 to last_cols do
for j =3D 0 to last_cols do
=C2=A0m.(i).(j) <- m.(i).(= j) || (m.(i).(k) && m.(k).(j))
done;=
=C2=A0 =C2=A0 =C2= =A0 done;
=C2= =A0 done;
=C2= =A0 m
;;

<= div style=3D"font-family:arial, helvetica, sans-serif">
(* transpose ma= trix A is the matrix A' formed by turning rows into
=C2=A0 = =C2=A0columns and vice versa: (A')i,j =3D Aj,i.*)
let transpose (m: 'a array array) : 'a array array =3D
=C2=A0 let tc =3D trans_closure m in
=C2=A0 let last_cols =3D = length m - 1 in
=C2=A0 for i =3D 0 to last_cols do
=C2= =A0 =C2=A0 for j =3D 0 to last_cols do
=C2=A0 =C2=A0 =C2=A0 tc.(j).(i) <- tc.(i).(j)
=C2=A0 =C2= =A0 done;
=C2=A0 done;
=C2=A0 tc
;;
I would like to compute equivalence classes, it is=C2=A0disjoint between=C2=A0matrix transitive closure =C2= =A0and 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

le= t to_list (m : 'a array array) : 'a list list =3D
=C2=A0 List.map to_list (to_list m)

=
let eq_class (m: 'a= array array) : 'a list list =3D
=C2=A0=C2=A0let lst =3D lengt= h m - 1 in
=C2=A0 =C2=A0 =C2=A0 for i =3D 0 to lst do
<= span style=3D"white-space:pre-wrap"> for j =3D 0 to lst do
=C2=A0let a =3D tc.(i).(= j) && trans.(i).(j) in
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 if a
=C2=A0= =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0???
I'm= stuck here, I don't know how I can add the result "a" into t= he new list of list. I think I should create a new list with type 'a li= st list, but I don't know where I should write it?

Thank you for helping me understand= and give me some=C2=A0advises.

Best regards,
Gwen