Com'è stato `val hash: 'a -> int` è stato implementato in OCaml?

Question

In OCaml, Hashtbl può hash qualsiasi cosa in int

Hashtbl.hash x associa un intero non negativo su qualsiasi valore di qualsiasi tipo. È garantito che se x = y o Pervasives.compare x y = 0, allora hash x = hash y. Inoltre, l'hash termina sempre, anche su strutture cicliche.

Voglio dire, in Java, abbiamo hashCode() per ogni oggetto che restituisce un intero e Hashtable di Java può hash intero.

Ma come ha fatto OCaml a ottenerlo per cancellare qualcosa?

Answer 1

Non è difficile. Hashtbl.hash attraversa appena i dati in un modo simile al modo in cui il garbage collector lo fa. Percorre una distanza fissa nella struttura collegata, che evita il malfunzionamento in caso di cicli. Non sa nulla dei tipi di alto livello di ciò che incontra, semplicemente blocca i valori primitivi che raggiunge.

È possibile visualizzare il codice in byterun/hash.c nella distribuzione di origine OCaml.

Aggiornamento

Mi viene in mente potrebbe essere stato chiedendo come è stato attuato Hashtbl.hashin OCaml. La risposta è che non può essere implementato in OCaml (senza imbrogli) perché viola la parametrricità. Le uniche funzioni pure possibili di tipo 'a -> int sono quelle che restituiscono un valore costante. L'intuizione è che tale funzione non può utilizzare alcuna informazione sul suo argomento perché è definita per tutti i tipi possibili.

Hashtbl.hash è una delle poche funzioni OCaml che violano la parametrricità. Esistono in OCaml perché sono estremamente utili. Un altro noto è il confronto polimorfico compare (e l'operatore associato =).