OCaml insert an element in list

6
votes

What is the standard way of inserting an element to a specific position in a list in OCaml. Only recursion is allowed. No assignment operation is permitted.

My goal is to compress a graph in ocaml by removing vertexes with in_degree=out_degree=1. For this reason I need to remove the adjacent edges to make a single edge. Now the edges are in a list [(6,7);(1,2);(2,3);(5,4)]. So I need to remove those edges from the list and add a single edge. so the above list will now look like [(6,7);(1,3);(5,4)]. Here we see (1,2);(2,3) is removed and (1,3) is inserted in the second position. I have devised an algorithm for this. But to do this I need to know how can I remove the edges (1,2);(2,3) from position 2,3 and insert (1,3) in position 2 without any explicit variable and in a recursive manner.

3
algorithmlistgraphcompressionocaml
I would suggest, if possible, ditching the list and using a Set data-structure. – nlucaroni
"Only recursion is allowed", "without any explicit variable" -- sounds like some kind of homework... is it? – lambdapower
yes it's a part of a homework, but I did not ask for the solution of the homework problem. I devised an algorithm and to use that algorithm i needed to do this operation on the list. That was I asking. My homework was to compress graphs in ocaml. Here i am not asking about that problem. I am asking about list. – P basak

3 Answers

6
votes

OCaml list is immutable so there's no such thing like removing and inserting elements in list operations.

What you can do is creating a new list by reusing certain part of the old list. For example, to create a list (1, 3)::xs' from (1, 2)::(2, 3)::xs' you actually reuse xs' and make the new list using cons constructor.

And pattern matching is very handy to use:

let rec transform xs =                                             
  match xs with
  | [] | [_] -> xs
  | (x, y1)::(y2, z)::xs' when y1 = y2 -> (x, z)::transform xs'
  | (x, y1)::(y2, z)::xs' -> (x, y1)::transform ((y2, z)::xs')
4
votes

You can do something like that :

let rec compress l = match l with                                            
   [] -> []                                                           
 | x :: [] -> [x]                                                     
 | x1 :: x2 :: xs -> 
   if snd x1 = fst x2 then 
     (fst x1, snd x2) :: compress xs
   else x1 :: compress (x2 :: xs)
0
votes

You are using the wrong datastructure to store your edges and your question doesnt indicate that you can't choose a different datastructure. As other posters already said: lists are immutable so repeated deletion of elements deep within them is a relatively costly (O(n)) operation.

I also dont understand why you have to reinsert the new edge at position 2. A graph is defined by G=(V,E) where V and E are sets of vertices and edges. The order of them therefor doesnt matter. This definition of graphs also already tells you a better datastructure for your edges: sets.

In ocaml, sets are represented by balanced binary trees so the average complexity of insertion and deletion of members is O(log n). So you see that for deletion of members this complexity is definitely better than the one of lists (O(n)) on the other hand it is more costly to add members to a set than it is to prepend elements to a list using the cons operation.

An alternative datastructure would be a hashtable where insertion and deletion can be done in O(1) time. Let the keys in the hashtable be your edges and since you dont use the values, just use a constant like unit or 0.