Geek Answers Handbook

OCaml inserts an item into a list

What is the standard way to insert an item at a specific position in a list in OCaml. Only recursion is allowed. Assignment operation is not allowed.

My goal is to compress the graph in ocaml by removing vertices with in_degree = out_degree = 1. For this reason, I need to remove adjacent edges in order to make one edge. Now the edges are in the list [(6,7); (1,2); (2,3); (5.4)]. So I need to remove these edges from the list and add one edge. therefore, 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 into the second position. I developed an algorithm for this. But for this I need to know how to remove the edges (1,2); (2,3) from position 2,3 and insert (1,3) into position 2 without any explicit variable and in a recursive manner.

+5
source share
3 answers

The OCaml list is immutable, so there is no such thing as deleting and inserting elements in list operations.

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

And pattern matching is very convenient 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')
+5
source

You can do something like this:

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)
+4
source

, , . : , , , (O (n)).

, 2. G = (V, E), V E - . . : sets.

ocaml , O (log n). , , , (O (n)), , , .

An alternative data structure would be a hash table where insertion and deletion can be performed O (1) times. Let the keys in the hash table be your edges, and since you are not using values, just use a constant like one or 0.

0
source

More articles:


All Articles