From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82]) by walapai.inria.fr (8.13.6/8.13.6) with ESMTP id p9VGDpma006875 for ; Mon, 31 Oct 2011 17:13:51 +0100 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AiEBALvIrk7RVdi2imdsb2JhbABChj+ibggiAQEBCgkNBxIGIYFyAQEBAQIBEgIsARsWBwEDAQsGBQs7IQEBEQEFARwGEyKHYJcNCotTgmCEej2IcAIFCoh4BIgAhHeHF4o2gn09g3I X-IronPort-AV: E=Sophos;i="4.69,432,1315173600"; d="scan'208";a="127284491" Received: from mail-qy0-f182.google.com ([209.85.216.182]) by mail1-smtp-roc.national.inria.fr with ESMTP/TLS/RC4-SHA; 31 Oct 2011 17:13:45 +0100 Received: by qyg14 with SMTP id 14so7099431qyg.6 for ; Mon, 31 Oct 2011 09:13:44 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=jEsUJb9KnxGAY4slmMMZ7cUSaNqk0WzD8W+K2PYNWmM=; b=ZIZOF3Y+DqTjM3tTZ8yakHvJbmj4SAFum81Fc1D5tGRMbBsXHQz5yIZOS/Gx15FCGB xwzP5b6r2IogN6UuRj0IRNHfWcyrkz3gzE0Stm218l5nbvdcO4671jRYs5DEdnVwbnus l/BQPQKf6vELOjcS2edfkQ/nho9o57jxOgljY= MIME-Version: 1.0 Received: by 10.229.230.68 with SMTP id jl4mr3029626qcb.126.1320077624163; Mon, 31 Oct 2011 09:13:44 -0700 (PDT) Received: by 10.229.212.131 with HTTP; Mon, 31 Oct 2011 09:13:43 -0700 (PDT) In-Reply-To: References: Date: Mon, 31 Oct 2011 19:13:43 +0300 Message-ID: From: Kakadu To: Ly Kim Quyen Cc: caml-list@inria.fr Content-Type: multipart/alternative; boundary=0016363b8d00dd409604b09a85ce Subject: Re: [Caml-list] Compute the equivalence classes --0016363b8d00dd409604b09a85ce Content-Type: text/plain; charset=ISO-8859-1 maybe let eq_class tc trans : 'a list list = let ans = (* create result matrix here *) in 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 ans.(i).(j) <- ... else .... done done; to_list ans ;; If I have understanded correctly..... --------------- Kakadu On Mon, Oct 31, 2011 at 7:36 PM, Ly Kim Quyen wrote: > 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 > --0016363b8d00dd409604b09a85ce Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable
maybe

let eq_class tc trans : 'a list list =3D
=A0 let ans =3D (* crea= te result matrix here *) in
=A0=A0let lst =3D length m - 1 in
=A0 =A0 =A0 for i =3D 0 to lst do
for j =3D 0 to lst do
=A0let a =3D tc.(i).(j) && trans.(i).(= j) in
=A0 =A0 =A0 = =A0 =A0 =A0 if a
=A0 =A0 =A0 = =A0 =A0 =A0 then ans.(i).(j) <- ...
=A0=A0=A0=A0=A0=A0=A0= =A0=A0=A0=A0 else ....
=A0=A0=A0=A0=A0=A0= =A0 done
=A0 =A0 =A0=A0 done;
=A0=A0=A0=A0 to_list ans
;;
=A0 =A0 =A0 =A0 = =A0=A0
If I have understanded correctly.....


---------------
Kakadu


On Mon, Oct 31, 2011 at 7:36 PM, Ly Kim Quyen &= lt;lykimq@gmail.com> wrot= e:
Dear group,

I have an question about data s= tructure and types. I have a function=A0calculates transitive closure of relation repr= esented as an=A0adjacency matrix

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

<= div style=3D"font-family:arial, helvetica, sans-serif">
(* transpose ma= trix A is the matrix A' formed by turning rows into
=A0 =A0co= lumns and vice versa: (A')i,j =3D Aj,i.*)
let transpose (m: 'a array array) : 'a array array =3D
=A0 let tc =3D trans_closure m in
=A0 let last_cols =3D length= m - 1 in
=A0 for i =3D 0 to last_cols do
=A0 =A0 for j= =3D 0 to last_cols do
=A0 =A0 =A0 tc.(j).(i) <- tc.(i).(j)
=A0 =A0 done;
<= div>=A0 done;
=A0 tc
;;
I would like to compute equivalence classes, it is=A0d= isjoint between=A0matrix transitive closure =A0and mat= rix transpose. I would like it returns for me a new list with the type: lis= t 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
=A0 List.map to_list (to_list m)

let eq_class (m: 'a ar= ray array) : 'a list list =3D
=A0=A0let lst =3D length m - = 1 in
=A0 =A0 =A0 for i =3D 0 to lst do
for j =3D 0 to lst do
=A0let a =3D tc.(i).(j) = && trans.(i).(j) in
=A0 =A0 =A0 =A0 =A0 =A0 if a
=A0 =A0 =A0 =A0 =A0 =A0???<= /font>
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=A0advises.

Best regards,
Gwen