how to update a list index from an index of another list in ocaml

by

I am new to ocaml. i am trying to implement doMove : int list -> int list -> move -> int list.

The first parameter is the list of volumes of the jars,
the second — the list that describes the current contents of the jars, and the
third — the move to be executed.

The result is a list that describes the updated contents of the jars. You can assume that the lists are always the same length, no jar contains more water than its volume, and the indices in the move are valid.

For example, calling doMove [5; 2] [5; 0] (Transfer (1, 0)) should result in a list [3; 2].

The error i had is
“This expression has type int list but an expression was expected of type
int”

type move = Transfer of int * int

let rec nth lst x =
  match lst with
  | [] -> raise (Failure "Not Found")
  | h :: t -> if x = 0 then h else nth t (x - 1)

let min x y = if x > y then y else x

let rec mapi f index list =
  match list with
  | [] -> []
  | x :: xs ->
    let result = f index x in
    result :: mapi f (index + 1) xs

let fst (a, _) = a

let snd (_, b) = b

let rec doMove jar_volumes jar_content move =
  let transfer_water_from_M_to_N m n jar_volumes jar_content =
    let jarM_volume_index = nth jar_volumes m in
    let jarN_volume_index = nth jar_volumes n in
    let jarM_content_index = nth jar_content m in
    let jarN_content_index = nth jar_content n in
    if jarM_content_index > 0 && jarN_content_index < jarN_volume_index then
      let compare_min_amount = min jarM_content_index (jarN_volume_index - jarN_content_index) in
      let new_jarM_content = jarM_content_index - compare_min_amount in
      let new_jarN_content = jarN_content_index + compare_min_amount in
      (new_jarM_content, new_jarN_content)
    else
      (jarM_content_index, jarN_content_index)
  in

  match move with
  | Transfer (m, n) ->
    let updated_jar_content =
      mapi (fun i content ->
        if i = m then fst (transfer_water_from_M_to_N m n jar_volumes jar_content)
        else if i = n then snd (transfer_water_from_M_to_N m n jar_volumes jar_content)
        else content)
      jar_content
    in
    updated_jar_content

i think the problem is with updated_jar_content. However, i have no clue how to solve it. Can anyone helps me with it? thanks a lot…

Quickly running your code in utop confirms the error you’re seeing is with jar_content.

This is because your mapi function expects three arguments: a function, an index, and a list. You’ve given it two: the function and the list. Because OCaml functions can be partially applied, you are allowed to give it two arguments, but the order of the arguments is important. OCaml sees jar_content where mapi expects an integer. To fix this error, give it an extra 0 argument.

  match move with
  | Transfer (m, n) ->
    let updated_jar_content =
      mapi (fun i content ->
        if i = m then fst (transfer_water_from_M_to_N m n jar_volumes jar_content)
        else if i = n then snd (transfer_water_from_M_to_N m n jar_volumes jar_content)
        else content)
      0 jar_content
    in
    updated_jar_content;;

Now, this compiles, but still does not produce the correct result, so there is more work to do.

# doMove [5;2] [5;0] (Transfer (1, 0));;
- : int list = [5; 0]

The other way to solve this error involves how you’ve defined mapi. Typically, we hide the start index argument, because it wouldn’t make sense to call it with anything other than zero.

let rec mapi f index list =
  match list with
  | [] -> []
  | x :: xs ->
    let result = f index x in
    result :: mapi f (index + 1) xs

This becomes the following, hiding the index argument with an inner function.

let mapi f lst =
  let rec aux i = function
    | [] -> []
    | x::xs -> f i x :: aux (i + 1) xs
  in
  aux 0 lst

mapi (fun i x -> i + x) [1; 2; 3]
aux 0 [1; 2; 3]
(0 + 1) :: aux 1 [2; 3]
(0 + 1) :: (1 + 2) :: aux 2 [3]
(0 + 1) :: (1 + 2) :: (2 + 3) :: aux 3 []
[1; 3; 5]

A hint

Indexing into lists is awkward because it’s not how lists are built or are meant to be accessed. Choose a more appropriate data structure for the task. If you need random access, use an array instead.

Also, parallel lists or arrays where each describes a different aspect of each element of a group of things is cumbersome. Instead define a data type to group those.

type jar_info = {cap : int; mutable content : int }

You can now combine your two lists and build a list of jar_info values.

# List.combine [5; 2] [5; 0];;
- : (int * int) list = [(5, 5); (2, 0)]
# List.map (fun (a, b) -> {cap=a; content=b}) 
  @@ List.combine [5; 2] [5; 0];;
- : jar_info list = [{cap = 5; content = 5}; {cap = 2; content = 0}]

And then turn that into an array.

# Array.of_list
  @@ List.map (fun (a, b) -> {cap=a; content=b})
  @@ List.combine [5; 2] [5; 0];;
- : jar_info array =
[|{cap = 5; content = 5}; {cap = 2; content = 0}|]

And from there building do_move is straightforward.

# let do_move caps contents (Transfer (t, f)) =
    let arr =
      Array.of_list
      @@ List.map (fun (a, b) -> {cap=a; content=b})
      @@ List.combine caps contents
    in
    let amount_to_transfer =
      (* Left as an exercise to avoid giving a complete 
       * homework solution. 
       *)
    in
    arr.(f).content <- arr.(f).content - amount_to_transfer;
    arr.(t).content <- arr.(t).content + amount_to_transfer;
    List.map (fun {content; _} -> content)
    @@ Array.to_list arr;;
val do_move : int list -> int list -> move -> int list = <fun>

Avoiding mutable state

If you need to avoid the use of mutable state, the next best choice of data structure would probably be a map. OCaml’s Map module provides maps backed up with a balanced binary trees, allowing for O(log n) access. It’s less great than an array’s O(1) access, but much better than a list’s O(n).

Leave a Comment