Is there a language, or a language-agnostic design pattern, that makes
it easy to define a generic public interface that works with any data
structure?
Haskell sembra un suggerimento fantastico, ma forse un po 'hardcore. Almeno ho un po 'paura di Haskell (è un linguaggio il cui codice mi ispira sempre, ma non ho mai avuto il coraggio di provare qualcosa di sostanziale).
Personalmente raccomando C ++ per questo dato che la generazione del codice dei template C ++ ti permette di eliminare qualsiasi costo di astrazione (dispatch dinamico, cioè) fuori dall'immagine e concentrarti solo sull'efficienza delle strutture di dati stessi mentre allo stesso tempo muti la struttura dei dati facilmente (potrebbe essere un po 'difficile nei linguaggi funzionali senza cambiare l'intero modo in cui ci si avvicina alle strutture dati). È una delle poche lingue che conosco personalmente dove è possibile scrivere una struttura di dati contigua che si comporta altrettanto bene per un accesso casuale come un semplice vecchio array, ad esempio, poiché l'ottimizzatore schiaccia solo tutta la struttura di codice che hai costruito in frantumi.
Viene anche fornito con un set abbastanza completo di contenitori standard (anche se mancano alcuni semi-comuni come try) con un'interfaccia agnostica "vicina" alla struttura dei dati. Un po 'di wrapping dovrebbe darti un'interfaccia universale che ti permetta di fare quello che vuoi, almeno per i tipi di valore (set vs. mappa). I contenitori associativi chiave / valore sono un po 'più difficili da generalizzare e potrebbero aver bisogno di essere nella loro categoria, semplicemente perché tendono a richiedere un design dell'interfaccia molto diverso.
La chiave per farlo è definire la tua interfaccia universale. Una sequenza standard C ++ come vector ha queste funzioni:
push_back -- appends an element to the back of the container.
insert -- inserts an element to any place in the container.
erase -- erases an element from any place in the container.
range insert -- inserts multiple elements to any place in the container.
range erase -- removes a range of elements from any place in the container.
empty -- returns size() == 0.
size -- returns the number of elements.
clear -- removes all elements from the container.
begin -- returns an iterator pointing to the beginning of the container.
end -- returns an iterator pointing to the end of the container.
C'è anche un costruttore di riempimenti, un costruttore di intervalli, ecc. (e puoi anche passare il tuo allocatore di memoria che di solito non è così utile per qualcosa come vector ma può fare un'enorme differenza per le strutture collegate).
La lista concatenata, std::list , è conforme agli stessi requisiti di interfaccia tranne alcune piccole differenze in questo contesto come una funzione membro push_front che viene omessa da std::vector deliberatamente per scoraggiare il suo uso lì.
Puoi facilmente racchiudere tutti questi contenitori e, con poco sforzo, applicare un'interfaccia universale ... magari con funzioni come queste:
push_front -- insert to front.
push_back -- insert to back.
erase -- erase anywhere.
insert -- insert anywhere with no regard about where the element goes.
insert_sorted -- do an insertion sort.
...
Ecc. Non ci vorrà molto tempo per avvolgere tutti i contenitori C ++ esistenti applicabili per conformarsi a questa interfaccia universale del tuo design e implementarne di nuovi conformi, e quindi puoi valutare il tuo cuore e generare grafici e tutto ciò che desideri.
Una cosa importante da notare su C ++ è l'iteratore che progetta algoritmi di guida. È possibile implementare una struttura dati personalizzata e, semplicemente esponendo gli iteratori, centinaia di algoritmi esistenti (non solo standard ma anche di terze parti) diventano improvvisamente applicabili alla struttura dei dati senza ulteriori sforzi. Non è necessario implementare come un metodo sort per la struttura dei dati personalizzati, ad esempio, poiché std::sort funzionerà su di esso una volta che esporrai gli iteratori a esso.