How can I get this expression to be of type string instead of string -> string?

I am learning OCaml and am having a bit of trouble with functional programming...

I need to make a function that replaces a for a given list of integers, the cahracters at that index of a string. Say for example i get [1;4] 'u' "Hello" as input, it outputs "Hullu".

This is what I have come up with:

let remplace_positions lst c str =
  let rec acc lst c str n l_index ret =
    match (n >= String.length str, List.nth lst l_index = n) with 
    | true, _ -> ret
    | _, true -> acc lst c (n+1) (l_index+1) (ret ^ (String.make 1 c))
    | _, _ -> acc lst c (n+1) (l_index+1) (ret ^ (String.make 1 (String.get str n)))
  in 
  acc lst c str 0 0 ""

But as you can see, there is an error on the two last match cases. They are of type string -> string, but I want them to be of type string.

Does anyone know how to fix this, while calling the function recursively?

Solution

When I test your function, I get:

# let remplace_positions lst c str =
  let rec acc lst c str n l_index ret =
    match (n >= String.length str, List.nth lst l_index = n) with
    | true, _ -> ret
    | _, true -> acc lst c (n+1) (l_index+1) (ret ^ (String.make 1 c))
    | _, _ -> acc lst c (n+1) (l_index+1) (ret ^ (String.make 1 (String.get str n)))
  in
  acc lst c str 0 0 "";;
Error: This expression has type int
       but an expression was expected of type string

Referring to the (n+1) in line:

    | _, true -> acc lst c (n+1) (l_index+1) (ret ^ (String.make 1 c))

This is because you've indicated the third argument to acc should be a string, but then you pass it an int.

I would suggest you're passing far too many arguments to acc anyway, making it difficult to keep track of them. If they don't change, there's no need for that inner function to take them as arguments. The inner function will be able to access bindings from the outer scope, as long as they aren't shadowed.

We can also factor out turning a character into a string.

let remplace_positions lst c str =
  let char_to_str c = String.make 1 c in
  let rec acc str n l_index ret =
    match (n >= String.length str, List.nth lst l_index = n) with
    | true, _ -> ret
    | _, true -> acc (n+1) (l_index+1) (ret ^ char_to_str c)
    | _, _ -> acc (n+1) (l_index+1) (ret ^ char_to_str (String.get str n))
  in
  acc str 0 0 ""

Same error, but somewhat easier code to read.

Now, let's remove the unnecessary passing of the str argument:

let remplace_positions lst c str =
  let char_to_str c = String.make 1 c in
  let rec acc n l_index ret =
    match (n >= String.length str, List.nth lst l_index = n) with
    | true, _ -> ret
    | _, true -> acc (n+1) (l_index+1) (ret ^ char_to_str c)
    | _, _ -> acc (n+1) (l_index+1) (ret ^ char_to_str (String.get str n))
  in
  acc 0 0 ""

Now it compiles. So let's run it.

# remplace_positions [1; 4] 'u' "hello";;
Exception: Failure "nth".

Where has this gone wrong?

Well, let's trace this out:

remplace_positions [1; 4] 'u' "hello"

acc 0 0 ""
  n >= String.length "hello" -> false
  List.nth [1; 4] 0 = n -> false
acc 1 1 ("" ^ "h")
  n >= 5 -> false
  List.nth [1; 4] 1 = n -> false
acc 2 2 ("h" ^ "e")
  n >= 5 -> false
  List.nth [1; 4] 2 = n -> exception!

You've incremented your list index to the point where it tries to access the list out of bounds, resulting in an exception.

To be honest your basic approach isn't worth saving. Using List.nth even successfully is inefficient because it is an O(n) operation rather than O(1).

What you ultimately need to do is iterate over the list and replace the characters at each of the indices with your specified character. Pattern-matching on lists provides the most idiomatic way of accomplishing this iteration over the list.

let rec replace_chars lst c str =
  let len = String.length str in
  let cs = String.make 1 c in
  match lst with
  | [] -> str
  | hd::tl ->
    let front_of_str = String.sub str 0 hd in
    let tail_of_str = String.sub str (hd + 1) (len - hd - 1) in
    replace_chars tl c (front_of_str ^ cs ^ tail_of_str)

But having strings be immutable in OCaml makes this messy. All of that getting substrings and concatenating them back together really takes up a lot of space. It'd be easier if they were mutable.

Fortunately that's what the Bytes module is for. We can convert to a mutable bytes type, modify it, then convert back to a string.

let replace_chars lst c str =
  let b = Bytes.of_string str in
  let rec aux lst =
    match lst with
    | [] -> b
    | hd::tl -> (Bytes.set b hd c; aux tl)
  in
  String.of_bytes (aux lst)

But really iterating over a list and applying an operation to each element is already handled by List.iter.

let replace_chars lst c str =
  let b = Bytes.of_string str in
  List.iter (fun i -> Bytes.set b i c) lst;
  String.of_bytes b

Fixing your approach

If you do actually want to fix your approach, there are a few issues you need to correct.

Pattern-matching with booleans is often better and more clearly expressed as a conditional expression. In this event we can use && and || which short-circuit.
You need to bounds check access to your string and list of positions.
When you encounter one of the indices from your list of positions, only then do you increment that index in your recursive call.

let replace_positions positions ch str =
  let rec aux stri pi acc =
    if stri >= String.length str || pi >= List.length positions then
      acc
    else if stri = List.nth positions pi then
      aux (stri+1) (pi+1) (acc ^ String.make 1 ch)
    else 
      aux (stri+1) pi (acc ^ String.make 1 str.[stri])
  in
  aux 0 0 ""

However, you could also use exception handling since either out of bounds access will generate an exception.

let replace_positions positions ch str =
  let rec aux stri pi acc =
    try
      if stri = List.nth positions pi then
        aux (stri+1) (pi+1) (acc ^ String.make 1 ch)
      else 
        aux (stri+1) pi (acc ^ String.make 1 str.[stri])
    with
    | Failure _
    | Invalid_argument _ -> acc
  in
  aux 0 0 ""

Which can be alternatively expressed:

let replace_positions positions ch str =
  let rec aux stri pi acc =
    match stri = List.nth positions pi with
    | true -> aux (stri+1) (pi+1) (acc ^ String.make 1 ch)
    | false -> aux (stri+1) pi (acc ^ String.make 1 str.[stri])
    | exception Failure _ 
    | exception Invalid_argument _  -> acc
  in
  aux 0 0 ""