## a probable wrong filling of a list

Expand Messages
• Dear all, I wrote a function that, given two lists, returns true if the elements of the first list are equal twice the elements of the second, in any order the
Message 1 of 5 , Jul 27, 2006
Dear all,

I wrote a function that, given two lists, returns true if the elements of
the first list are equal twice the elements of the second, in any order
the elements of the two lists are placed.
So for example, if

l1 = [2; 4; 8]
l2 = [2; 1; 4]

the function must returns TRUE. The same result if

l1 = [2; 4; 8]
l2 = [1; 2; 4]

or

l1 = [8; 4; 2]
l2 = [1; 2; 4].

The code of the function is at the end of this e-mail. What I do not
understand is the output of the line

print_int (List.length !(a_list.(0)));

that is i x j, that's strange, 'cause each list a_list.(i) is filled by
(List.length l2' - 1) elements, so in the examples listed above it should
be 3. But the output is 9!

Of course there is something wrong in this function, but I do not see
what. Where is the problem?

Paola.

(************************************************************************)
let are_encoded_procs a b = if a = b*2 then true else false;;

if ( (List.length l1 != 0) && (List.length l2 != 0) ) then
(
let l1' = remove_equals l1 in
let l2' = remove_equals l2 in

if (List.length l1' = List.length l2') then
(

let a_list = Array.create (List.length l1') (ref []) in

let l1_a = Array.of_list l1 in
let l2_a = Array.of_list l2 in

for i = 0 to (List.length l1' - 1) do
(
for j = 0 to (List.length l2' - 1) do
insert (are_encoded_procs l1_a.(i) l2_a.(j))
a_list.(i);
done;
)
done;

print_int (List.length !(a_list.(0)));
print_string "\n";

(*print_string (list_to_string (List.map (display_bool)
!(a_list.(0))));*)

let hm_list = ref [] in

for k = 0 to (List.length l1' - 1) do
insert (how_many true !(a_list.(k))) hm_list;
done;

if (are_all 1 !hm_list) then ((print_int_list
!hm_list);true) else ((print_int_list !hm_list); false )
)
else false
)
else raise (Failure "The two lists cannot be empty")
• ... Um... no. Assuming insert is something like: let insert b lref = lref := b::!lref;; Then you will have (List.length l1 ) * (List.length l2 ) calls to
Message 2 of 5 , Jul 27, 2006
On Thu, 27 Jul 2006, Lecca Paola wrote:

> The code of the function is at the end of this e-mail. What I do not
> understand is the output of the line
>
> print_int (List.length !(a_list.(0)));
>
> that is i x j, that's strange, 'cause each list a_list.(i) is filled by
> (List.length l2' - 1) elements, so in the examples listed above it should
> be 3. But the output is 9!

Um... no. Assuming insert is something like:
let insert b lref = lref := b::!lref;;
Then you will have (List.length l1') * (List.length l2') calls to insert
as it's inside the inner loop.

BTW: Is there a reason this code is so complex? You can do the same thing
in just a couple of lines my using List.sort and List.map.

William D. Neumann

---

"There's just so many extra children, we could just feed the
children to these tigers. We don't need them, we're not doing
anything with them.

Tigers are noble and sleek; children are loud and messy."

-- Neko Case

Life is unfair. Kill yourself or get over it.
-- Black Box Recorder
• ... Whoops, braindead moment there. Though this is a part of it. When you do an Array.create, all of the cells of the array initially point to the same thing,
Message 3 of 5 , Jul 27, 2006
On Thu, 27 Jul 2006, William D. Neumann wrote:

> Um... no. Assuming insert is something like:
> let insert b lref = lref := b::!lref;;
> Then you will have (List.length l1') * (List.length l2') calls to insert
> as it's inside the inner loop.

Whoops, braindead moment there. Though this is a part of it.
When you do an Array.create, all of the cells of the array initially point
to the same thing, that is, the value you pass into the call to create.
They continue to point to that same element until you replace them with a
call to Array.set (or Array.init which calls set).

So here, a_list's elements all point to the same list ref. Now, when you
call insert, you are just modifying the contents of the list ref, and
never overwriting the contents of the various cells in a_list, hence, if
you modify the list ref in any cell, you modify the list ref in all the
cells. E.g.

# let a_list = Array.create 5 (ref []);;
val a_list : '_a list ref array =
[|{contents = []}; {contents = []}; {contents = []}; {contents = []};
{contents = []}|]
# let lr = a_list.(0);;
val lr : '_a list ref = {contents = []}
# lr := 1::!lr;;
- : unit = ()
# a_list;;
- : int list ref array =
[|{contents = [1]}; {contents = [1]}; {contents = [1]}; {contents = [1]};
{contents = [1]}|]

So what's the easy way to fix this? Well, the easiest way is to use
Array.init to create the array, rather than Array.create, as this will put
a different list ref in each cell of the array. E.g.

# let b_list = Array.init 5 (fun _ -> ref []);;
val b_list : '_a list ref array =
[|{contents = []}; {contents = []}; {contents = []}; {contents = []};
{contents = []}|]
# let lr = b_list.(0);;
val lr : '_a list ref = {contents = []}
# lr := 1::!lr;;
- : unit = ()
# b_list;;
- : int list ref array =
[|{contents = [1]}; {contents = []}; {contents = []}; {contents = []};
{contents = []}|]

Of course, there's that whole "why go through all this ugliness when a
couple of calls to the List module work so much better" that I mentioned
in the first response.

William D. Neumann

---

"There's just so many extra children, we could just feed the
children to these tigers. We don't need them, we're not doing
anything with them.

Tigers are noble and sleek; children are loud and messy."

-- Neko Case

Life is unfair. Kill yourself or get over it.
-- Black Box Recorder
• ... And just to provide a bit more insight: # a_list.(0)
Message 4 of 5 , Jul 27, 2006
On Thu, 27 Jul 2006, William D. Neumann wrote:

> So here, a_list's elements all point to the same list ref. Now, when you
> call insert, you are just modifying the contents of the list ref, and
> never overwriting the contents of the various cells in a_list, hence, if
> you modify the list ref in any cell, you modify the list ref in all the
> cells. E.g.
>
> # let a_list = Array.create 5 (ref []);;
> val a_list : '_a list ref array =
> [|{contents = []}; {contents = []}; {contents = []}; {contents = []};
> {contents = []}|]
> # let lr = a_list.(0);;
> val lr : '_a list ref = {contents = []}
> # lr := 1::!lr;;
> - : unit = ()
> # a_list;;
> - : int list ref array =
> [|{contents = [1]}; {contents = [1]}; {contents = [1]}; {contents = [1]};
> {contents = [1]}|]

And just to provide a bit more insight:

# a_list.(0) <- ref (2::!(a_list.(0)));;
- : unit = ()
# a_list;;
- : int list ref array =
[|{contents = [2; 1]}; {contents = [1]}; {contents = [1]}; {contents =
[1]};
{contents = [1]}|]
# let lr = a_list.(0);;
val lr : int list ref = {contents = [2; 1]}
# let lr1 = a_list.(1);;
val lr1 : int list ref = {contents = [1]}
# lr := 3::!lr;;
- : unit = ()
# lr1 := 4::!lr1;;
- : unit = ()
# a_list;;
- : int list ref array =
[|{contents = [3; 2; 1]}; {contents = [4; 1]}; {contents = [4; 1]};
{contents = [4; 1]}; {contents = [4; 1]}|]

William D. Neumann

---

"There's just so many extra children, we could just feed the
children to these tigers. We don't need them, we're not doing
anything with them.

Tigers are noble and sleek; children are loud and messy."

-- Neko Case

Life is unfair. Kill yourself or get over it.
-- Black Box Recorder
• ... elements of ... let doubled a b = List.for_all2 (fun m n - m = 2 * n) (List.sort compare a) (List.sort compare b) ;;
Message 5 of 5 , Aug 2, 2006
--- In ocaml_beginners@yahoogroups.com, Lecca Paola <lecca@...> wrote:
>
>
> Dear all,
>
> I wrote a function that, given two lists, returns true if the
elements of
> the first list are equal twice the elements of the second, in any order
> the elements of the two lists are placed.
> So for example, if
>
> l1 = [2; 4; 8]
> l2 = [2; 1; 4]
>
> the function must returns TRUE. The same result if
>
> l1 = [2; 4; 8]
> l2 = [1; 2; 4]
>
> or
>
> l1 = [8; 4; 2]
> l2 = [1; 2; 4].

let doubled a b =
List.for_all2 (fun m n -> m = 2 * n)
(List.sort compare a)
(List.sort compare b)
;;
Your message has been successfully submitted and would be delivered to recipients shortly.