Strutture immutabili e gerarchia di composizione profonda

I could have stored indices of Polygon in current Scene, index of dragged point in Polygon, and replace it every time. But this approach does not scale - when composition levels go to 5 and further, boilerplate would become unbearable.

Hai assolutamente ragione, questo approccio non scala se non puoi aggirare il boilerplate . Nello specifico, è cambiato lo standard per la creazione di una scena completamente nuova con una piccola parte secondaria. Tuttavia, molti linguaggi funzionali forniscono un costrutto per gestire questo tipo di manipolazione della struttura nidificata: lenti.

Un obiettivo è fondamentalmente un getter e setter per dati immutabili. Un obiettivo ha un focus su una piccola parte di una struttura più grande. Dato un obiettivo, ci sono due cose che puoi fare con esso: puoi visualizzare la piccola parte di un valore della struttura più grande, oppure puoi impostare la piccola parte di un valore di una struttura più grande a un nuovo valore. Ad esempio, supponiamo di avere un obiettivo che si concentra sul terzo elemento di un elenco:

thirdItemLens :: Lens [a] a

Questo tipo indica che la struttura più grande è una lista di cose, e la piccola sottoparte è una di quelle cose. Dato questo obiettivo, puoi visualizzare e impostare il terzo elemento nell'elenco:

> view thirdItemLens [1, 2, 3, 4, 5]
3
> set thirdItemLens 100 [1, 2, 3, 4, 5]
[1, 2, 100, 4, 5]

La ragione per cui gli obiettivi sono utili è perché sono valori che rappresentano getters e setter e puoi astrarli sopra allo stesso modo in cui puoi altri valori. Puoi eseguire funzioni che restituiscono obiettivi, ad esempio una funzione listItemLens che prende un numero n e restituisce un obiettivo che visualizza la n th elemento in un elenco. Inoltre, gli obiettivi possono essere composti :

> firstLens = listItemLens 0
> thirdLens = listItemLens 2
> firstOfThirdLens = lensCompose firstLens thirdLens
> view firstOfThirdLens [[1, 2], [3, 4], [5, 6], [7, 8]]
5
> set firstOfThirdLens 100 [[1, 2], [3, 4], [5, 6], [7, 8]]
[[1, 2], [3, 4], [100, 6], [7, 8]]

Ogni obiettivo incapsula il comportamento per attraversare un livello della struttura dei dati. Combinandoli, è possibile eliminare il boilerplate per attraversare più livelli di strutture complesse. Ad esempio, supponendo di avere un scenePolygonLens i che visualizza il i th Polygon in una scena e un polygonPointLens n che visualizza il punto nth in un poligono, puoi creare un costruttore di lenti per concentrarti solo sullo specifico indica che ti interessa in un'intera scena in questo modo:

scenePointLens i n = lensCompose (polygonPointLens n) (scenePolygonLens i)

Ora supponiamo che un utente faccia clic sul punto 3 del poligono 14 e lo sposti a destra di 10 pixel. Puoi aggiornare la tua scena in questo modo:

lens = scenePointLens 14 3
point = view lens currentScene
newPoint = movePoint 10 0 point
newScene = set lens newPoint currentScene

Questo contiene perfettamente tutto lo standard per attraversare e aggiornare una scena all'interno di lens , tutto ciò di cui ti devi preoccupare è ciò a cui vuoi cambiare il punto. Puoi astrarre ulteriormente questo con una funzione lensTransform che accetta un obiettivo, un bersaglio e una funzione per aggiornare la vista del bersaglio attraverso l'obiettivo:

lensTransform lens transformFunc target =
  current = view lens target
  new = transformFunc current
  set lens new target

Questo prende una funzione e la trasforma in un "updater" su una struttura dati complicata, applicando la funzione solo alla vista e usandola per costruire una nuova vista. Quindi torniamo allo scenario di spostare il 3 ° punto del 14 ° poligono a 10 pixel di destra, che può essere espresso in termini di lensTransform come in questo modo:

lens = scenePointLens 14 3
moveRightTen point = movePoint 10 0 point
newScene = lensTransform lens moveRightTen currentScene

E questo è tutto ciò che serve per aggiornare l'intera scena. Questa è un'idea molto potente e funziona molto bene quando hai alcune funzioni utili per la costruzione di obiettivi che visualizzano i pezzi dei tuoi dati che ti interessano.

Tuttavia questo è tutto abbastanza roba al momento, anche nella comunità di programmazione funzionale. È difficile trovare un buon supporto per le biblioteche per lavorare con gli obiettivi, e ancora più difficile spiegare come funzionano e quali sono i benefici per i tuoi colleghi. Prendi questo approccio con un pizzico di sale.

Ho lavorato esattamente allo stesso problema (ma solo con 3 livelli di composizione). L'idea di base è quella di clonare, quindi modificare . In stile di programmazione immutabile, la clonazione e la modifica devono avvenire contemporaneamente, che diventa oggetto comando .

Si noti che in uno stile di programmazione mutevole, la clonazione sarebbe stata comunque necessaria:

• Per consentire l'annullamento / ripristino
• Potrebbe essere necessario che il sistema di visualizzazione visualizzi simultaneamente i modelli "prima modifica" e "durante la modifica", sovrapposti (come linee fantasma), in modo che l'utente possa vedere le modifiche.

In stile di programmazione mutabile,

• La struttura esistente è deep-cloned
• Le modifiche vengono apportate nella copia clonata
• Si dice al motore di visualizzazione di rendere la vecchia struttura in linee fantasma e la struttura clonata / modificata a colori.

In stile di programmazione immutabile,

• Ogni azione dell'utente che risulta nella modifica dei dati viene mappata su una sequenza di "comandi".
• Un oggetto comando incapsula esattamente quale modifica deve essere applicata e un riferimento alla struttura originale.
  • Nel mio caso, il mio oggetto comando si limita a ricordare l'indice del punto che deve essere modificato e le nuove coordinate. (Ad esempio, molto leggero, poiché non sto seguendo rigorosamente lo stile immutabile.)
• Quando viene eseguito un oggetto comando, crea una copia profonda modificata della struttura, rendendo permanente la modifica nella nuova copia.
• Man mano che l'utente apporta più modifiche, verranno creati più oggetti comando.

Gli oggetti profondamente immutabili hanno il vantaggio che la clonazione profonda richiede semplicemente la copia di un riferimento. Hanno lo svantaggio che fare anche una piccola modifica ad un oggetto profondamente annidato richiede la costruzione di una nuova istanza di ogni oggetto all'interno del quale è annidata. Gli oggetti mutabili hanno il vantaggio che cambiare un oggetto è facile - basta farlo - ma la clonazione profonda di un oggetto richiede la costruzione di un nuovo oggetto che contiene un clone profondo di ogni oggetto nidificato. Peggio ancora, se uno vuole clonare un oggetto e fare un cambiamento, clonare quell'oggetto, fare un altro cambiamento, ecc. Allora non importa quanto grande o piccolo le modifiche siano costrette a mantenere una copia dell'intero gerarchia per ogni versione salvata dello stato dell'oggetto. Nasty.

Un approccio che potrebbe valere la pena di prendere in considerazione sarebbe quello di definire un tipo astratto "MaybeMutable" con tipi di derivati mutevoli e immutabili. Tutti questi tipi presentano un metodo AsImmutable ; chiamare quel metodo su un'istanza profondamente immutabile di un oggetto restituirebbe semplicemente quell'istanza. Chiamarlo su un'istanza mutabile restituirebbe un'istanza profondamente immutabile le cui proprietà erano istantanee immutabili dei loro equivalenti nell'originale. I tipi immutabili con equivalenti mutabili avrebbero un metodo AsMutable , che costruirà un'istanza mutabile le cui proprietà corrispondono a quelle dell'originale.

La modifica di un oggetto nidificato in un oggetto immutabile richiederebbe prima la sostituzione dell'oggetto immutabile esterno con uno mutabile, quindi sostituendo la proprietà contenente la cosa da modificare con una mutabile, ecc. ma apportando modifiche ripetute allo stesso l'aspetto dell'oggetto globale non richiede la creazione di oggetti aggiuntivi fino al momento in cui è stato effettuato un tentativo di chiamare AsImmutable su un oggetto mutabile (che lascerebbe mutabili gli oggetti mutabili, ma restituire oggetti immutabili contenenti gli stessi dati).

Come semplici ma significative ottimizzazioni, ogni oggetto mutabile può contenere un riferimento memorizzato nella cache di un oggetto del tipo immutabile associato e ogni tipo immutabile deve memorizzare nella cache il suo valore GetHashCode . Quando si chiama AsImmutable su un oggetto mutabile, prima di restituire un nuovo oggetto immutabile, verificare che corrisponda al riferimento memorizzato nella cache. In tal caso, restituisce il riferimento memorizzato nella cache (abbandonando il nuovo oggetto immutabile). Altrimenti aggiorna il riferimento memorizzato nella cache per conservare il nuovo oggetto e restituirlo. In tal caso, le chiamate ripetute a AsImmutable senza mutazioni intermedie produrranno gli stessi riferimenti a oggetti. Anche se non si risparmia il costo della costruzione delle nuove istanze, si eviterà il costo della memoria per mantenerle. Inoltre, i confronti di uguaglianza tra gli oggetti immutabili possono essere notevolmente accelerati se nella maggior parte dei casi gli elementi da confrontare sono uguali o hanno codici hash diversi.