Set puramente funzionale intelligente

Question

I calcoli impostati composti da unioni, intersezioni e differenze possono essere spesso espressi in molti modi diversi. Esistono teorie o implementazioni concrete che cercano di minimizzare la quantità di calcolo necessaria per raggiungere una determinata risposta? Ad esempio, ho trovato per prima cosa un'applicazione pratica di questo quando si tenta di scomporre gli atomi in una simulazione di un materiale amorfo in gusci vicini, dove la prima shell è l'immediata vicina di un dato atomo di origine e la seconda shell sono quelli atomi che sono vicini del primo guscio non in entrambi il primo guscio o quello prima:

nth 0 = singleton i 
nth 1 = neighbors i 
nth n = reduce union (map neighbors (nth(n-1))) - nth(n-1) - nth(n-2) 

ci sono molti modi diversi per risolvere questo. È possibile verificare in modo incrementale l'appartenenza a ciascun set mentre si compone il risultato oppure è possibile calcolare l'unione di tre shell vicine e utilizzare l'intersezione per rimuovere le due shell precedenti lasciando quella più esterna. In pratica, le soluzioni che richiedono la costruzione di grandi serie intermedie sono più lente.

Presumibilmente un'implementazione di un set intelligente potrebbe comporre l'espressione che doveva essere valutata e quindi ottimizzarla (ad esempio per ridurre la dimensione dei set intermedi) prima di valutarla al fine di migliorare le prestazioni. Esistono implementazioni di questo tipo?

Answer 1

La tua domanda mi ha immediatamente ricordato la fusione del flusso di Haskell, descritta in this paper. Il principio generale può essere riassunto abbastanza facilmente: invece di memorizzare una lista, si memorizza un modo per costruire una lista. Quindi le funzioni di trasformazione dell'elenco operano direttamente sul generatore di elenchi, il che significa che tutte le operazioni si fondono in una singola generazione di dati senza strutture intermedie. Quindi quando hai terminato di comporre le operazioni, esegui il generatore e produci i dati.

Quindi penso che la risposta alla tua domanda è che se volevi un meccanismo altrettanto intelligente che fondesse i calcoli ed eliminasse le strutture di dati intermedi, avresti bisogno di trovare un modo per trasformare un set in una "co-struttura" (questo è ciò che il giornale chiama) che genera un set e opera direttamente su di esso, quindi genera effettivamente il set quando hai finito.

Penso che ci sia una teoria molto profonda dietro questo concetto che la carta accenna ma non enuncia mai, e se qualcun altro qui sa cosa sia, per favore fatemelo sapere, perché questo è molto rilevante per qualcos'altro che sto facendo , pure!