insert element in all positions of a list in OCaml

Question

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?

Answer 1

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 :).

Answer 2

Try breaking this problem down.

First hurdle: can you insert an element at a given index in a list? The start might look like:

let rec insert lst pos v =
  (* ... *)

Well, we know if the position is 0, it should go at the front.

let rec insert lst pos v =
  match pos with
  | 0 -> v :: lst
  | _ -> (* ... *)

If it's not 0 then you'd need to append the first element in lst to the result of inserting into the tail of the list at pos - 1.

Of course, the devil is in the details. What happens if you try insert [1; 2; 3; 4] 7 5? You need to find a way to check for situations like this.

If you can get this function to work, you then just need to iterate from 0 to the length of the list, inserting the new value into the list.

List.init would work nicely.

List.(
  let lst = [1; 2; 3; 4] in
  let len = length lst + 1 in
  init len (fun i -> insert lst i 5)
)

And as a result, if you wrote insert correctly, you should get:

[[5; 1; 2; 3; 4]; [1; 5; 2; 3; 4]; [1; 2; 5; 3; 4]; 
 [1; 2; 3; 5; 4]; [1; 2; 3; 4; 5]]

Answer 3

This should do the trick:

let rec insert v l =
  match l with
  | []    -> [[v]]
  | x::xs -> (v::l) :: (List.map (List.cons x) (insert v xs))

Adding an explanation, had to think about this a while too:

For an empty list there is only one way to insert v and [[v]] is the result.

For a list x::xs first insert v at all positions in xs: insert v xs, which gives a list of lists. Then for each list add x back to the front: List.map (List.cons x) .... This gives all the results where v is inserted after x. So last construct the list where v is added before x: v::l. Adding that to the front of the list of lists gives the final result.