OCaml вставить элемент в список

Question

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

Моя цель - сжать граф в 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 без какой-либо явной переменной и рекурсивным способом.

Answer 1

Список 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')

Answer 2

Вы можете сделать что-то подобное:

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)

Answer 3

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

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

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

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