insert element in all positions of a list in OCaml

Trying to insert a number in all positions of the list, result being a list of lists.

something like:

insert 4 [1; 2; 3] = [[4; 1; 2; 3]; [1; 4; 2; 3]; [1; 2; 4; 3]; [1; 2; 3; 4]]

My idea is to apply Map on the list with a function that returns a list. resulting in list of lists. like [f 1; f 2 ; f3] (I know will only have 3 lists, but just want to get this working first)

let insert (x : 'a) (ls : 'a list): 'a list list =
  let aux p =
    List.fold_left 
      (fun f2 acc q -> 
         if p = q then List.append acc x::[q] 
         else List.append acc q::[]) 
      [] ls
  in 
  List.map aux ls

Hope is, function aux will return a list with x inserted in the right place.

The problem is, List.map f1 ls line is assuming ls is 'a list list even though it is defined as 'a list

Any ideas please?

To actually answer your question, instead of providing you with different methods to reach your goal (you wanted to know what is actually wrong with your code, not how one could solve the problem.):

1. signature of fold_left is ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a = <fun>. Instead of ('a -> 'b -> 'a) your provide it with fun f2 acc q -> ... = ('a -> 'b -> 'c -> 'a). Just remove the f2 and you're fine.

2. put brackets around stuff like x::[q], or use @@.

Your code:

let insert (x : 'a) (ls : 'a list): 'a list list =
  let aux p =
    List.fold_left 
      (fun f2 acc q -> 
         if p = q then List.append acc x::[q] 
         else List.append acc q::[]) 
    [] ls
  in 
 List.map aux ls

Working code:

let insert (x : 'a) (ls : 'a list): 'a list list =
  let aux p =
    List.fold_left 
      (fun acc q -> 
         if p = q then List.append acc (x::[q]) 
         else List.append acc (q::[])) 
    [] ls
  in 
 List.map aux ls

For input insert 4 [1;2;3]this returns int list list = [[4; 1; 2; 3]; [1; 4; 2; 3]; [1; 2; 4; 3]]. This is almost what you wanted. The rest can be fixed by you :).

Note:

The Error that the Compiler throws is: Error: This expression has type 'a list but an expression was expected of type 'b list -> 'b list list. For the next time, just think about what happened. You provide fold_left with ('a -> 'b -> 'c -> 'a); which is not "wrong", but not what you want. You could write it as ('a -> ('b -> 'c) -> 'a). This means the acc-value is some 'a and the value of the fold is a function 'b -> 'c. This explains the error-message :).