OCaml - Conversion from one-dimensional array to two-dimensional array

Question

I'm trying to convert a one-dimensional array to a two-dimensional array in OCaml.

When testing the function I wrote:

# to_array2d [|1;2;3;1;2;4;1;2;5|];;

I get this incorrect result:

int array array = [|[|1; 2; 5|]; [|1; 2; 5|]; [|1; 2; 5|]|]

The correct result should be:

int array array = [|[|1; 2; 3|]; [|1; 2; 4|]; [|1; 2; 5|]|]

Here is the code:

let to_array2d (array1d: int array) : int array array = 
    let dim = int_of_float (sqrt (float (Array.length array1d))) in
        let array2d = Array.make dim (Array.make dim 0 ) in
            for i = 0 to (dim - 1) do 
                    for j = 0 to (dim - 1) do
                        array2d.(i).(j) <- (Array.get array1d (i * dim + j))
                    done
                done;
                array2d
;;

What am I doing wrong?

Hi Thomas, maybe your question would be easier to read if you would explicitly write which output you had expected. Also, maybe you can move the input, expected output and actual output before your code, this is probably a better catchline. :) — Michaël Le Barbier, Mar 29 '15 at 18:21

score 3 · Accepted Answer · edited May 23 '17 at 11:45

The faulty place in your code is

let b =
  Array.make dim (Array.make dim 0)

which does not what you intend. The name b is not in your code but is convenient for the discussion. To understand what you see, let us rewrite this code in the following equivalent manner:

let b =
  let a = Array.make dim 0 in
  Array.make dim a

This code produces an array of length dim whose entries are all a. These are not copies of a, they are just a with kind of a different name. The proper way to express this in OCaml is to say that these structures are physically equal and the == operator tests for physical equality.

# b.(0) == b.(1);;
true

Physical equality is a stronger relation than structural equality tested by the more usual = operator. It is specified that given two physically equal mutable structures like b.(0) and b.(1), the modification of any of them will also affect the other one, or in the words of the documentation of the Pervasives module:

val (==) : 'a -> 'a -> bool e1 == e2 tests for physical equality of e1 and e2. On mutable types such as references, arrays, byte sequences, records with mutable fields and objects with mutable instance variables, e1 == e2 is true if and only if physical modification of e1 also affects e2. On non-mutable types, the behavior of ( == ) is implementation-dependent; however, it is guaranteed that e1 == e2 implies compare e1 e2 = 0.

We can think to this as a formal way to say that these two structures are “really the same”.

If you want to fox the structure of your code, you can take advantage of the Array.make_matrix function which will generate a fresh 2-dimensional array. If you are tired of debugging errors in for-loops, you can use the more ocaml-ish solution:

let unpack dim a =
  let line i =
    Array.init dim (fun j -> a.(i*dim + j))
  in
  Array.init dim line

let to_array2d a =
  let dim = int_of_float (sqrt (float (Array.length array1d))) in
  unpack dim a

See Also

Thank you for the detailed information and the better structured solution! One thing: `let dim = int_of_float (sqrt (float (Array.length array1d))) in` should be: `let dim = int_of_float (sqrt (float (Array.length a))) in` — Thomas Vanhelden, Mar 30 '15 at 09:31
Thank you for pointing that. Maybe this is obvious enough, so that an edit is not really required. — Michaël Le Barbier, Apr 08 '15 at 08:09

score 2 · Answer 2 · edited May 23 '17 at 12:09

2

You're creating 2D array incorrectly. Array.make will just copy the second argument dim times. So, you have an array of three pointers to the same array. Look here for more details on how to cook array properly. Your particular case can be written much nicer with Array.init function

let to_array2d (array1d: int array) : int array array = 
  let dim = int_of_float (sqrt (float (Array.length array1d))) in
  Array.init dim (fun i -> Array.init dim (fun j -> array1d.(i * dim + j)))

Although, I don't like the idea with sqrting length.

A very good explanation of this issue can be found in the OCaml Book. Look at the page 68 (page 94 of the pdf).

edited May 23 '17 at 12:09

Community

1
1

answered Mar 29 '15 at 17:23

ivg

34,431
2
35
63

Actually, the argument is not copied (this pretty much the reason why the code of the OP does not work as he expects.) Also, there is no such a thing as pointers in OCaml, the relevant concept is *physical equality*. – Michaël Le Barbier Mar 29 '15 at 18:05
BTW I am not a huge fan of the `sqrt` thing either. :) – Michaël Le Barbier Mar 29 '15 at 18:18
Well I'm trying to address the OP, taking into account its background, without introducing to many new concepts. Using "pointer" word will momentary trigger a correct associations. What concerning physical equality it is a little bit more complex concept. Strictly speaking it denotes, that objects are physically equal, if and only if physical modification of one object affects the other. And the idea of pointers is used to describe this issue in the OCaml Book. – ivg Mar 29 '15 at 18:48

score 2 · Answer 3 · answered Mar 29 '15 at 17:38

2

To elaborate on @ivg's answer: Array.make will take the value you give it and put it into all the elements of a new array. For values with structure (like arrays) this means you will end up with three occurrences of the very same value.

# let a = Array.make 3 (Array.make 4 0);;
 val a : int array array = [|[|0; 0; 0; 0|]; [|0; 0; 0; 0|]; [|0; 0; 0; 0|]|]
# a.(1).(3) <- 17;;
- : unit = ()
# a;;
- : int array array = [|[|0; 0; 0; 17|]; [|0; 0; 0; 17|]; [|0; 0; 0; 17|]|]
#

You don't want occurrences of the very same array. You want a different array each time. For that you can use Array.init (say).

# let a = Array.init 3 (fun _ -> Array.make 4 0);;
val a : int array array = [|[|0; 0; 0; 0|]; [|0; 0; 0; 0|]; [|0; 0; 0; 0|]|]
# a.(1).(3) <- 17;;
- : unit = ()
# a;;
- : int array array = [|[|0; 0; 0; 0|]; [|0; 0; 0; 17|]; [|0; 0; 0; 0|]|]

answered Mar 29 '15 at 17:38

Jeffrey Scofield

65,646
2
72
108

The key concept to describe this phenomenon is *physical equality* which you seems to refer to, without naming it. – Michaël Le Barbier Mar 29 '15 at 18:15
Yes, very true. Trying to keep it simple. You can find my take on physical equality here: http://stackoverflow.com/questions/13590307/whats-the-difference-between-equal-and-identical-in-ocaml/13590433#13590433 or here: http://stackoverflow.com/questions/29121354/how-can-i-check-two-pointers-meet-each-other-when-going-through-a-list – Jeffrey Scofield Mar 29 '15 at 18:33
There is a link to that question with your answer in my answer to this question. What a terrible way to phrase it! ;) – Michaël Le Barbier Mar 29 '15 at 18:34

OCaml - Conversion from one-dimensional array to two-dimensional array

3 Answers3