Данные, используемые вставить элемент в список

Каков стандартный способ вставки элемента в определенную позицию в списке в OCaml. Допускается только рекурсия. Операция присвоения не допускается.

Моя цель состоит в том, чтобы сжать график в данные, используемые при удалении вершины с in_degree=out_degree=1. По этой причине мне нужно удалить соседние края, чтобы сделать один край. Теперь края находятся в списке [(6,7);(1,2);(2,3);(5,4)]. Поэтому мне нужно удалить эти края из списка и добавить один край. Итак, приведенный выше список теперь будет выглядеть как будто [(6,7);(1,3);(5,4)]. Здесь мы видим (1,2); (2,3) удаляется и (1,3) вставляется во вторую позицию. Я разработал алгоритм для этого. Но для этого мне нужно знать, как я могу удалить ребра (1,2); (2,3) из позиции 2,3 и вставить (1,3) в позицию 2 без какой-либо явной переменной и рекурсивным образом.

3 5
compression list algorithm ocaml

3 ответа:

Список OCaml является неизменяемым, поэтому нет такой вещи, как удаление и вставка элементов в операциях списка.

Что вы можете сделать, так это создать новый список, повторно используя определенную часть старого списка. Например, чтобы создать список (1, 3)::xs' из (1, 2)::(2, 3)::xs', вы фактически повторно используете xs' и создаете новый список с помощью конструктора cons.

И сопоставление шаблонов очень удобно использовать: 

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

Вы можете сделать что-то вроде этого: 

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

Вы используете неправильную структуру данных для хранения ребер, и ваш вопрос не означает, что вы не можете выбрать другую структуру данных. Как уже говорилось в других плакатах: списки неизменны, поэтому повторное удаление элементов глубоко внутри них является относительно дорогостоящей операцией(O (n)).

Я также не понимаю, почему вы должны снова вставить новое ребро в позицию 2. Граф определяется G=(V,E), где V и E - множества вершин и ребер. Порядок их для этого не существует вопрос. Это определение графов также уже говорит вам о лучшей структуре данных для ваших ребер: наборы.

В ocaml множества представлены сбалансированными бинарными деревьями, поэтому средняя сложность вставки и удаления элементов равна O (log n). Таким образом, вы видите, что для удаления членов эта сложность определенно лучше, чем у списков (O(n)), с другой стороны, добавление членов в набор обходится дороже, чем добавление элементов в список с помощью операции cons.

An альтернативной структурой данных может быть хэш-таблица, в которой вставка и удаление могут быть выполнены за O(1) Время. Пусть ключи в хеш-таблице будут вашими ребрами, и поскольку вы не используете значения, просто используйте константу, такую как единица или 0.

0