SML Type commun pour différentes structures

Question

J'implémente des ensembles dans la norme ML. Actuellement, il ressemble à ceci:

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 

Je veux la fonction map pour pouvoir prendre un ensemble dans une structure SET, idéalement même pas contraint à ceux de foncteur ListSetFn. Cependant, au niveau supérieur, il ne peut fonctionner que sur des ensembles créés par une structure unique: celui qu'il est appelé à partir, par exemple:

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 

Pendant que je voudrais vraiment à quelque chose comme

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

Y a-t-il un moyen de le faire? Je sais que ce pourrait être déclaré au niveau supérieur, mais je veux cacher la mise en œuvre interne et utiliser donc la signature opaque (s)

Answer 1

En principe, il existe deux façons d'effectuer une telle paramétrisation:

1. Enveloppe la fonction dans son propre foncteur, ce qui prend l'autre structure en argument.

2. Rendre la fonction polymorphe en transmettant les fonctions pertinentes pour opérer sur l'autre type en tant qu'arguments individuels ou en tant qu'enregistrement d'arguments.

Supposons que la signature SET contient les fonctions suivantes:

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 

Ensuite, la première solution ressemblerait à ceci:

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 

Pour la solution 2, vous devez passer toutes pertinentes fonctions directement, par exemple comme les dossiers:

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, ce serait plus agréable avec des structures de première classe, mais SML ne les a pas comme une caractéristique standard.

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