From: Pierre Weis <Pierre.Weis@inria.fr>
Message-Id: <199705051706.TAA22495@pauillac.inria.fr>
Subject: Re: initialization of arrays
In-Reply-To: <Pine.GSO.3.95.970429214123.25931A-100000@terreaux> from David Monniaux at "Apr 29, 97 10:08:15 pm"
To: David.Monniaux@ens-lyon.fr (David Monniaux)
Date: Mon, 5 May 1997 19:06:04 +0200 (MET DST)
> [en français: l'initialisation de tableaux n'est pas pratique pour les
> types mutables...]
[en français: il faut initialiser les tableaux avec des fonctions
d'initialisation appele'es pour chaque e'le'ment du tableau...]
> Hi,
>
> creating an array initializes all the cells to the same physical content.
Yes, since the name ``Array'' is a bit cheating in Caml: there are no
arrays, just flat vectors. Arrays are incoded into these flat vectors
as vectors having vectors as elements (hence this strange
'a array array type for a matrix). That's why a naive definition of a
matrix (Array.create n (Array.create m 0)) leads to the unexpected
sharing of the matrix's rows.
> That is not very handy when the content is a mutable record. Of course,
> one can initialize the cells with copies of a given record. There we run
> into another problem: the only way I know of, given a record, produce
> another record of the same content, is to write the following kind of
> code:
> { field1=a.field1; field2=a.field2 ...}
> This is quite cumbersome.
Yes it is, but you need not to use this kind of ``by hand'' copy. You
should instead define a copying function for your records:
let copy_record { field1=a1; field2=a2 ...} = { field1=a1; field2=a2...};;
You then have to use a functional initialisation of your
array, using an explicit function argument to initialize items:
(* val init_array : int -> (int -> 'a) -> 'a = <fun> *)
let init_array n f =
if n = 0 then [||] else
let val0 = f 0 in
let v = Array.create n val0 in
for i = 1 to n - 1 do
v.(i) <- f i
done;
v;;
You then use
# let arr = init_array 10 (function i -> i);;
val arr : int array = [|0; 1; 2; 3; 4; 5; 6; 7; 8; 9|]
to get a vector initialized with given integers.
In the same vein, you may also initialize a matrix:
# let mat = init_array 5 (function i -> init_array 5 (function j -> i + j));;
val mat : int array array =
[|[|0; 1; 2; 3; 4|]; [|1; 2; 3; 4; 5|]; [|2; 3; 4; 5; 6|];
[|3; 4; 5; 6; 7|]; [|4; 5; 6; 7; 8|]|]
In your case, initialisation with a mutable record is just:
init_array n
(function i -> init_array m
(function j -> {field1 = e1; field2 = e2; ...}))
or equivalently
init_matrix n m (function i -> function j -> {field1 = e1; field2 = e2; ...})
Note that, using the expanded form, you can finely monitor the
sharing. For instance
init_array n
(function i -> init_array m
(let e1 = ... and e2 = ... in
(function j -> {field1 = e1; field2 = e2; ...})))
means that expressions e1 and e2 will be computed once for each row
(hence their values are shared among elements of a row).
Now copying a matrix with your mutable record values is defined via
the record copying function:
let copy a =
init_matrix n m (function i -> function j -> copy_record a.(i).(j))
With init_array, a matrix copying function is a one-liner:
(* val shallow_copy_matrix : 'a array array -> 'a array array = <fun> *)
let shallow_copy_matrix a =
init_array (Array.length a) (function i -> Array.copy a.(i));;
(* copy_matrix : 'a array array -> (int -> int -> 'b) -> 'b array array *)
let copy_matrix a f =
init_array (Array.length a)
(function i -> init_array (Array.length a.(i)) (function j -> f i j));;
You may also define a general functional matrix initializer to derive
the copying functions:
(* init_matrix : int -> int -> (int -> int -> 'a) -> 'a array array *)
let init_matrix n m f =
init_array n (function i -> init_array m (function j -> f i j));;
(* map_matrix : 'a array array -> (int -> int -> 'b) -> 'b array array *)
let map_matrix a f =
let n = Array.length a in
if n = 0 then [||] else
let m = Array.length a.(0) in
init_matrix n m f;;
let copy_matrix = map_matrix;;
> Wouldn't it be handy to have a function of type 'a->'a that duplicates
> physically a piece of data, and functions that create vectors or
> matrices with copy?
The problem is: how deep will be the copy? If you want the copy
function to handle properly matrix it cannot be a shallow copy. Thus
this copy function will be costy and hard to use. Anyway, copying of
vectors and matrices is really trivial using Array.copy and copy_matrix.
> I feel it's now doable somehow with the Obj module (I'm testing it), but
> using undocumented features is cumbersome and unsafe...
You're right. I guess we could have a Matrix module, defining the same
set of primitives as the Array module for 'a array array values: you
then solve your problem with Matrix.copy, Matrix.create (and other
problems as matrix concatenation, filling or blitting).
> Thanks.
Pierre Weis
INRIA, Projet Cristal, Pierre.Weis@inria.fr, http://pauillac.inria.fr/~weis/
This archive was generated by hypermail 2b29 : Sun Jan 02 2000 - 11:58:10 MET