tabelle hash in prolog

Question

Ho risolto un enigma in prolog l'altro giorno e ho capito che stavo usando un altro linguaggio di programmazione, avrei usato un hash table/dictionary, ma per quanto ne so questo non è possibile in prolog.

Quindi la mia prima domanda è: ci sono dei prolog che supportano una struttura dati simile a un dizionario con le caratteristiche di prestazione di una tabella hash?

In secondo luogo, mi venne in mente che poiché la maggior parte prologs utilizzare una tabella hash per memorizzare i predicati, potrei scrivere un predicato involucro di affermare e far rientrare i fatti, creando un'interfaccia dizionario che sfruttare la tabella hash sottostante dei predicati. Ma otterrei le caratteristiche di prestazione di una tabella hash o l'interfaccia aggiungerebbe sovraccarichi che ridurrebbe le prestazioni?

Answer 1

ho appena scoperto che:

SWI-Prolog versione 7 introduce dicts come un oggetto astratto con un concreta sintassi moderna e notazione funzionale per l'accesso ai membri e così come funzioni di accesso definite da l'utente.

La sintassi è la seguente:

Tag{Key1:Value1, Key2:Value2, ...}

Vedi Dicts: structures with named arguments per i dettagli.

Nota che:

• These are first-class citizens of the language
• Semantica di unificazione tra dicts potrebbe cambiare in futuro
• Il ./2 operatore, precedentemente usato per la contro-zione, è stato riproposto per accedere ai membri dict tramite espressioni come point{x:1,y:2}.x
• Dicts can be destructively modified ma questo non è raccomandato, essendo "non-logico", per non dire non funzionale.
• The current underlying implementation è "un termine composto utilizzando il funtore dict. Il primo argomento è il tag. I restanti argomenti creano una serie di ordinati coppie di valori-chiave"

Prolog raggiunge così fino ai molti linguaggi con tipo di dati "mappa" che sono sorti negli ultimi 10 anni (es. maps in Clojure).

Answer 2

Alcuni ambienti Prolog hanno associazione elenca, che può essere utilizzato per creare e modificare un dizionario:

• SWI-Prolog
• SICStus Prolog

Edit:

È potrebbe essere in grado di ottenere Bett prestazioni er implementando predicati in lingue straniere, ad esempio:

• SWI-Prolog Java o C++
• GNU Prolog C interface
• SICStus C, C++ e Java/.Net.

Answer 3

Io non sono un ragazzo Prolog (appena un osservatore esterno), ma ho trovato questo:

http://www.sics.se/sicstus/docs/4.0.7/html/sicstus/lib_002davl.html

quando ho cercato per "Prolog mappa finita alberi bilanciati". Dice che è un'implementazione alternativa degli elenchi di associazioni.

(Perché ho pensato a questo: in Haskell, un linguaggio puramente funzionale, anziché elenchi di associazioni o tabelle hash, è comune usare alberi per dizionari (persistenti) o mappe finite. Le ricerche sono anche O (log (N) Vedere Data.Map per alcuni riferimenti sull'implementazione di mappe con alberi bilanciati.)

Answer 4

In SICStus Prolog, utilizzare le librerie assoc o avl.

Answer 5

I seguenti commenti indirizzano la domanda in un ordine che va approssimativamente da "più specifico" a "più generale".

In primo luogo, affrontando il tuo commento concreta:

avrei fatto uso di un hash table/dizionario, ma per quanto ne so questo non è davvero possibile in Prolog.

Tutte le implementazioni seria di Prolog consentono di modificare in modo distruttivo i termini di Prolog, utilizzando ad esempio setarg/3. L'utilizzo di arg/3 e setarg/3 fornisce l'accesso O (1) a ciascun argomento di un termine, che è sufficiente per implementare una tabella di hash esattamente come in altri linguaggi, presupponendo che il proprio sistema non ponga limiti arbitrari alle proprietà dei termini.

Non è una buona idea farlo da soli, poiché è necessario prendere in considerazione la copia imprevista e la condivisione di termini a tutti i termini. Invece, affidati alle librerie per farlo.

Quali librerie? I secondi ciò che altri hanno scritto: Invece di hashing biblioteche, utilizzare basati su alberi librerie come library(assoc), library(avl) ecc Questi non sono abbastanza efficiente come hash nel caso medio, ma:

• sono spesso efficaci abbastanza
• scalabili in modo molto prevedibile: operazioni più importanti sono sempre in O (log (n)).

anche come altri hanno scritto, modifiche distruttive sono incompatibili con la programmazione logica, e le librerie degli alberi hanno il grande vantaggio di poter essere implementate in ISO   Prolog e in modopuro   con asintoticamente efficienza ottimale.

Infine, le estensioni di dict SWI-Prolog sono non conforme ISO, nemmeno sintatticamente, e quindi non conforme portatile per sistemi Prolog! Vedere Ulrich Neumerkel comments per come un punto infisso può essere aggiunto in un modo conforme ISO.