Loading ...
Sorry, an error occurred while loading the content.
 

a probable wrong filling of a list

Expand Messages
  • Lecca Paola
    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?


      Thanks a lot in advance,
      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")
    • William D. Neumann
      ... 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
      • William D. Neumann
        ... 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
        • William D. Neumann
          ... 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
          • Bill James
            ... 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.