In OCaml, è possibile definire la mappa in termini di Set?

Question

Ho implementato una rappresentazione di set (alberi di ricerca bilanciati) in OCaml. In realtà è un funtore Make della firma

module Make : 
    functor (T : ORDERED_TYPE) -> 
sig 
    type elt = T.t 
    type t 
    val empty : t 
    val cons : elt -> t -> t 
    val delete : elt -> t -> t 
    val mem : elt -> t -> bool 
    val cardinal : t -> int 
end 

dove

module type ORDERED_TYPE = sig type t val compare : t -> t -> int end 

Ora mi piacerebbe realizzare un dizionario come Map nella libreria standard. Deve avere una firma come

module Make: functor (T : ORDERED_TYPE) -> sig 
    type key = T.t 
    type +'a t 
    ... 
end 

dove t è il tipo di dizionari.

L'implementazione di alberi di ricerca bilanciati di nuovo non è elegante, quindi voglio definire dizionari in termini di insiemi implementati come un functor sopra. Posso farlo?

Answer 1

A me sembra che una mappa sia una funzione (parziale), che è un insieme di coppie ordinate. Se si definisce correttamente la funzione di confronto, penso che si possa fare. Potrebbe essere necessario aggiungere una funzione all'interfaccia Set per tenere conto del fatto che due valori possono essere uguali per scopi di appartenenza, ma in realtà non sono valori uguali. Non sembra possibile definire la funzione di ricerca per la mappa con l'interfaccia corrente.

Answer 2

Come notato da Jeffrey, l'interfaccia Set non è sufficientemente espressiva per implementare comodamente Map su di essa. Sarebbe più semplice implementare Set da Map, definendo i set come mappe dalle chiavi al valore unitario.

Un'altra possibilità, che vorrei raccomandare, è quella di esporre prima un modulo di alberi di ricerca bilanciati senza incapsulamento, con l'unico scopo di fornire una struttura dati efficiente, che è interamente rivelata dall'interfaccia. Sei quindi libero di riutilizzarlo per qualsiasi struttura di dati che ti piace, tra cui Map e Set, senza dover giocare per definirne uno in termini di altro. Questo potrebbe non essere molto importante in questo caso (la definizione di Set da Map è ragionevole per la maggior parte degli scopi), ma secondo me è un design migliore nel caso generale.

In breve: se si desidera riutilizzare le implementazioni, esporre "moduli di implementazione" e definire i "moduli di interfaccia" sopra di essi.

Answer 3

come altri hanno già fatto notare, ci sono almeno due motivi per cui non è possibile implementare la mappa funtore richiesto in cima al set di data:

1. La firma insieme fornisce alcun modo per trovare una " uguale "elemento in un dato insieme.
2. E anche se così fosse, non è possibile memorizzare i valori al suo interno in modo polimorfico, come il tipo 'a map sembra richiedere.

Sei sicuro che l'attività richieda di implementare le mappe in cima ai set? Forse dovresti implementarli come set?

Answer 4

Beh, c'è in realtà è un uguale operatore in là - l'confronto funzione dal tipo ordinato.

Quindi definire il proprio modulo per un tipo di chiave/valore che tiene il confronto solo la parte-chiave:

module Keyvalue = struct 
    type t = ('a * 'b) 
    let compare x y = Pervasives.compare (fst x) (fst y) 
end 

e si è fatto. Il problema ora è che il tuo Set non ti permette di ottenere i suoi valori; non c'è get né una fold funzione - che imho è davvero limitante per una tale struttura di dati. Se si è permesso di armeggiare con il Set implementazione, è necessario aggiungere una funzione ottenere:

module Set = sig 
    ... 
    get : t -> elt -> elt 
end 

che restituirà l'appena chiesto per l'elemento. Se si prende il secondo elemento della tupla restituita, si ha il valore dalla coppia chiave/valore originale .