initialization of arrays

initialization of arrays

[David Monniaux]

[en français: l'initialisation de tableaux n'est pas pratique pour les
types mutables...]

Hi,

creating an array initializes all the cells to the same physical content.
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.

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?

I feel it's now doable somehow with the Obj module (I'm testing it), but
using undocumented features is cumbersome and unsafe...

Thanks.

Re: initialization of arrays

[Pierre Weis]

> [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/

Re: initialization of arrays

[Christophe Raffalli]

Hi,

I agree with this, but more generally we need a syntactic sugar to copy a
record and change some fields like

{ r with a = e; b = f; ... }

Or anything like that ! 
(this would give record copy by removing the with part)

When you use a record with many fields it makes the program much longer (and
less readable) when you often need to change one or two field in a record.

----
Christophe Raffalli
Universite Paris XII

URL: http://www.logique.jussieu.fr/www.raffalli