OCaml inserta un elemento en la lista

Question

¿Cuál es la forma estándar de insertar un elemento en una posición específica en una lista en OCaml. Solo se permite la recursión. No se permite ninguna operación de asignación.

Mi objetivo es comprimir un gráfico en ocaml eliminando vértices con in_degree = out_degree = 1. Por esta razón, necesito eliminar los bordes adyacentes para hacer un solo borde. Ahora los bordes están en una lista [(6,7); (1,2); (2,3); (5,4)]. Entonces necesito eliminar esos bordes de la lista y agregar un solo borde. , por lo que la lista anterior ahora se verá como [(6,7); (1,3); (5,4)]. Aquí vemos (1,2); (2,3) se elimina y (1,3) se inserta en la segunda posición. He ideado un algoritmo para esto. Pero para hacer esto necesito saber cómo puedo eliminar los bordes (1,2); (2,3) de la posición 2,3 e insertar (1,3) en la posición 2 sin ninguna variable explícita y de forma recursiva.

Answer 1

lista OCaml es inmutable por lo que no hay tal cosa como la eliminación y la inserción de elementos en la lista de operaciones.

Lo que puede hacer es crear una nueva lista reutilizando cierta parte de la lista anterior. Por ejemplo, para crear una lista (1, 3)::xs' desde (1, 2)::(2, 3)::xs', realmente reutiliza xs' y crea la nueva lista usando el constructor cons.

Y la coincidencia de patrones es muy práctico de usar:

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

Usted puede hacer algo así:

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

Está utilizando la estructura de datos incorrecto para almacenar sus bordes y su pregunta duerma indican que no se puede elegir una estructura de datos diferente. Como ya han dicho otros carteles: las listas son inmutables, por lo que la eliminación repetida de elementos en su interior es una operación relativamente costosa (O (n)).

Tampoco entiendo por qué tiene que volver a insertar el nuevo borde en la posición 2. Un gráfico se define por G = (V, E) donde V y E son conjuntos de vértices y bordes. El orden de ellos para ellos no importa. Esta definición de gráficos también ya te dice una mejor estructura de datos para tus bordes: conjuntos.

En ocaml, los conjuntos están representados por árboles binarios equilibrados, por lo que la complejidad promedio de inserción y eliminación de miembros es O (log n). Por lo tanto, puede ver que para eliminar miembros esta complejidad es definitivamente mejor que la de listas (O (n)), por otro lado, es más costoso agregar miembros a un conjunto que preceder elementos a una lista usando los contras. operación.

Una estructura de datos alternativa sería una tabla hash donde la inserción y la eliminación se pueden realizar en el tiempo O (1). Deje que las teclas en la tabla hash sean sus bordes y ya que no usa los valores, simplemente use una constante como unidad o 0.