Qual è stata l'influenza delle strutture dati di Chris Okasaki su Scala? [chiuso]

Commento dei tuoi amici

Prima di tutto, non è sicuramente corretto ciò che afferma il tuo amico. Il libro di Okasaki ha avuto una grande influenza sulle strutture dati in diverse lingue.

Influenza

Prima di tutto, penso che possiamo classificare "influenza" come uno dei due:

• Influenza diretta: alcuni linguaggi di programmazione implementano alcune delle strutture dati descritte.
• Influenza indiretta: le strutture dati in una lingua sono costruite usando le tecniche descritte nel libro, ma potrebbero non essere le strutture dati effettive descritte.

In entrambi i casi, le persone possono utilizzare le strutture dati descritte o una struttura simile, senza aver letto direttamente il suo libro. Ma quando si tratta di strutture dati funzionali, la maggior parte delle persone tende a leggere il libro di Okasaki.

L'influenza di Okasaki su Scala

La libreria standard di Scala offre collezioni mutevoli e immutabili. Ovviamente, solo gli immutabili potrebbero essere derivati dal lavoro di Okasaki, quindi diamo un'occhiata a quelli:

• Elenco: una normale lista di controllo (lista collegata singolarmente). Questo concetto è stato ampiamente conosciuto per sempre (quasi) e generalmente ampiamente usato in quasi tutti i linguaggi funzionali.
• Stack: solo un'altra astrazione inserita nell'elenco sopra. Niente di particolarmente Okasaki'ish qui.
• Coda: la coda immutabile di Scala è un'implementazione "ingenua" che utilizza due elenchi. Sebbene descritto nel libro di Okasaki, questa struttura della coda non era qualcosa di nuovo quando uscì il libro. Il problema con questa struttura dati è che può essere potenzialmente lento in un'ambientazione persistente, che Okasaki migliora nel suo libro - ma sembra che Scala abbia bloccato questa implementazione per semplicità e velocità.
• Stream: un elenco lazy memoized. Questo è descritto nel libro di Okasaki, ma non è qualcosa di nuovo al momento.
• TreeSet / TreeMap: un albero rosso / nero immutabile. Di nuovo, questo è descritto nel libro di Okasaki, ma era ampiamente conosciuto anche prima di questo.
• HashSet / HashMap / Vector: tutti si basano su Hash Array Mapped Tries di Phil Bagwell. I vettori sono simili a quelli che trovi in Clojure. Sebbene i tentativi siano descritti brevemente da Okasaki, erano già noti, e questa struttura dei dati è piuttosto lontana da qualsiasi altra cosa descritta qui.
• ListSet / ListMap / BitSet: non descritto nel libro di Okasaki, per quanto mi ricordo.

Come puoi vedere, la maggior parte delle strutture di dati utilizzate precedono il libro di Okasaki e, sotto questo aspetto, non rientra nella categoria influenza diretta o indiretta in quanto tale.

Tuttavia, sarebbe ingenuo pensare che il libro di Okasaki non abbia influenzato affatto Scala. La descrizione di Okasaki di alberi rossi / neri immutabili è più una guida meno pratica per l'implementazione funzionale di questi. Strutture di dati puramente funzionali raccolgono davvero molto materiale che altrimenti si troverà solo in vari documenti di ricerca - quindi quello che suppongo sia che il libro probabilmente ha aiutato gli sviluppatori a prendere le decisioni che meglio si adattano alla lingua.