SML Allgemeiner Typ für verschiedene Strukturen

Question

Ich implementiere Sets in Standard ML. Derzeit sieht es wie folgt aus:

signature SET = sig 
    type t 
    type 'a set 
    ... 
    val map : ('a -> t) -> 'a set -> t set 
end 

functor ListSetFn (EQ : sig type t val equal : t * t -> bool end) 
     :> SET where type t = EQ.t = struct 
    type t = EQ.t 
    type 'a set = 'a list 
    ... 
    fun map f = fromList o (List.map f) 
end 

Ich möchte die map Funktion SET jeden Satz in einer Struktur zu ergreifen, um der Lage sein, im Idealfall nicht einmal auf jene eingeschränkt von ListSetFn Funktors. Doch auf der obersten Ebene kann es nur auf Gruppen arbeiten, indem sie eine einzige Struktur geschaffen: Einer es aus aufgerufen wird, zB:

functor EqListSetFn(eqtype t) :> SET where type t = t = struct 
    structure T = ListSetFn(struct type t = t val equal = op= end) 
    open T 
end 

structure IntSet = EqListSetFn(type t = int) 
IntSet.map : ('a -> IntSet.t) -> 'a IntSet.set -> IntSet.t IntSet.set 

Während ich wirklich möchte es so etwas wie

IntSet.map : ('a -> IntSet.t) -> 'a ArbitrarySet.set -> IntSet.t IntSet.set 

sein

Gibt es eine Möglichkeit, es zu tun? Ich weiß, dass es auf der obersten Ebene erklärt werden könnte, aber ich möchte die interne Implementierung verstecken und damit undurchsichtig Signatur verwenden (s)

Answer 1

Grundsätzlich gibt es zwei Möglichkeiten, eine solche Parametrierung auszuführen:

1. Umbrechen Sie die Funktion in einen eigenen Funktor, der die andere Struktur als Argument verwendet.

2. Machen Sie die Funktion polymorph, übergeben Sie die relevanten Funktionen, um auf dem anderen Typ als einzelne Argumente oder als eine Aufzeichnung von Argumenten zu arbeiten.

Lassen Sie uns die SET Unterschrift übernehmen enthält folgende Funktionen:

val empty : 'a set 
val isEmpty : 'a set -> bool 
val add : 'a * 'a set -> 'a set 
val remove : 'a * 'a set -> 'a set 
val pick : 'a set -> 'a 

Dann wird die frühere Lösung würde wie folgt aussehen:

functor SetMap (structure S1 : SET; structure S2 : SET) = 
struct 
    fun map f s = 
    if S1.isEmpty s then S2.empty else 
    let val x = S1.pick s 
    in S2.add (f x, map f (S2.remove (x, s))) 
    end 
end 

Für Lösung 2, müssten Sie alle relevanten passieren Funktionen direkt, z als Datensätze:

fun map {isEmpty, pick, remove} {empty, add} f s = 
    let 
     fun iter s = 
     if isEmpty s then empty else 
     let val x = pick s 
     in add (f x, iter (remove (x, s))) 
     end 
    in iter s end 

FWIW, würde dies schöner sein mit erstklassigen Strukturen, aber SML hat sie nicht als Standard-Feature.

fun map (pack S1 : SET) (pack S2 : SET) f s = 
    let 
     fun iter s = 
     if S1.isEmpty s then S2.empty else 
     let val x = S1.pick s 
     in S2.add (f x, iter (S2.remove (x, s))) 
     end 
    in iter s end