OCaml inserisce un elemento nell'elenco

Question

Qual è il modo standard di inserire un elemento in una posizione specifica in un elenco in OCaml. È consentita solo la ricorsione. Nessuna operazione di assegnazione è consentita.

Il mio obiettivo è comprimere un grafico in ocaml rimuovendo i vertici con in_degree = out_degree = 1. Per questo motivo ho bisogno di rimuovere i bordi adiacenti per creare un singolo bordo. Ora i bordi sono in una lista [(6,7); (1,2); (2,3); (5,4)]. Quindi ho bisogno di rimuovere quei bordi dall'elenco e aggiungere un singolo bordo. quindi l'elenco sopra apparirà ora come [(6,7); (1,3); (5,4)]. Qui vediamo (1,2); (2,3) è rimosso e (1,3) è inserito nella seconda posizione. Ho ideato un algoritmo per questo. Ma per fare questo ho bisogno di sapere come posso rimuovere i bordi (1,2); (2,3) dalla posizione 2,3 e inserire (1,3) in posizione 2 senza alcuna variabile esplicita e in modo ricorsivo.

Answer 1

lista OCaml è immutabile quindi non c'è nulla di simile come la rimozione e l'inserimento di elementi in operazioni su liste.

Quello che puoi fare è creare un nuovo elenco riutilizzando alcune parti della vecchia lista. Ad esempio, per creare un elenco (1, 3)::xs' da (1, 2)::(2, 3)::xs', riutilizzare effettivamente lo xs' e creare il nuovo elenco utilizzando il costruttore cons.

E pattern matching è molto comodo da usare:

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

si può fare qualcosa di simile:

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

Si utilizza la datastructure sbagliato per memorizzare i bordi e la tua domanda doesnt indicano che non è possibile scegliere un datastructure diverso. Come già affermato da altri autori: le liste sono immutabili, la cancellazione ripetuta di elementi al loro interno è un'operazione relativamente costosa (O (n)).

Inoltre non capire perché si deve reinserire il nuovo bordo in posizione 2. Un grafico è definito da G = (V, E) dove V ed E sono insiemi di vertici e spigoli. Il loro ordine non ha importanza. Anche questa definizione di grafici ti dice già una migliore infrastruttura per i tuoi bordi: set.

In ocaml, i set sono rappresentati da alberi binari bilanciati, quindi la complessità media dell'inserimento e dell'eliminazione dei membri è O (log n). Quindi vedi che per la cancellazione dei membri questa complessità è decisamente migliore di quella delle liste (O (n)) d'altra parte è più costoso aggiungere membri a un set piuttosto che anteporre elementi a un elenco usando gli svantaggi operazione.

Una datastruttura alternativa sarebbe una tabella hash in cui l'inserimento e la cancellazione possono essere eseguiti in tempo O (1). Lascia che le chiavi nella tabella siano i tuoi bordi e dato che non usi i valori, usa una costante come unità o 0.