Lack of expressivity of functors (type variables).

[Ud71p]

We present a method for reuse of implementation, where one
datastructure can be defined in terms of another, similar one. We
utilize SMLs module language to transform a given datastructure into a
new one.

Let's look at the set/map duality. If we have a map (aka. finite map,
dictionary, table, etc.) datastructure, then we can easily implement a
set in terms of it:

{ a, b, c } = { a:(), b:(), c:() },

that is a set of elements of type E can be represented as a map from
keys of type E to values of type unit (empty tuples).

Likewise, if we have a set datastructure, we can use it to implement a
map:

{ a:x, b:y, c:z } = { (a,x), (b,y), (c,z) },
a < b iff (a,) < (b,)

that is a map from keys of type K to values of type V can be
represented as a set of elements of type K*V, i.e. key-value
pairs. The ordering supplied to the given set implementation shall
compare the pairs by first constituent only.

Observing this duality prevents the common mistake of duplicate
implementation. The functions operating on sets and maps are
practically the same, they may be long, and there is many of them in a
rich set/map structure. Hence, one shall only implement a set
directly, and then use it to implement a map. Alternatively, one can
start by implementing a map, and implement a set in terms of it. In
StandardML one should be able to use a functor to easily implement one
datastructure in terms of another.

The preferred way would be to implement the set directly, and use a
functor to transform it to a map. Why set? Because it's slightly
easier and more elegant to implement - the internal datastructure only
needs to store one value - the element, instead of two - keys and
values.

However (due to a problem described later), we implement a map
directly and later transform it into a set.

The signatures used here are pretty much the same as ORD_KEY, ORD_SET
and ORD_MAP in SML/NJ.
*)

(* Signature for our ordered type: *)

signature Comparable = sig
type T
val compare: T*T -> order
end

signature MAP = sig
type Key
type 'v Map
val empty: 'v Map
val put: Key -> 'v -> 'v Map -> 'v Map
end

(* The map datastructure is implemented directly: *)
functor Map(comparable: Comparable) :> MAP where type Key = comparable.T =
struct
type Key = comparable.T
datatype 'v Map = Empty | Binary of 'v Map * Key * 'v * 'v Map
val empty = Empty

(* This implementation lacks any form of balancing, so a better map
would be even more complicated. *)

fun put k' v' Empty = Binary(Empty, k', v', Empty)
| put k' v' (Binary(l,k,v,r)) =
case comparable.compare(k',k) of
LESS => Binary(put k' v' l, k, v, r)
| EQUAL => Binary(l, k', v', r)
| GREATER => Binary(l, k, v, put k' v' r)
end

signature SET = sig
type Element
type Set
val empty: Set
val put: Element -> Set -> Set
end

(* The set datastructure uses map internally, so the many long )
( functions (like put) don't need to be repeated: *)
functor Set(comparable: Comparable) :> SET where type Element = comparable.T =
struct
type Element = comparable.T
structure M :> MAP where type Key = Element = Map(comparable)
type Set = unit M.Map

val empty = M.empty
fun put x s = M.put x () s
end

(* Some usage examples: *)
structure ComparableInt = struct
type T = int
val compare = Int.compare
end

structure IMap :> MAP where type Key = int = Map(ComparableInt)
structure ISet :> SET where type Element = int = Set(ComparableInt)

val set : ISet.Set = ISet.put 8 ISet.empty

(* Good, maps are polymorphic over values: *)
val i2s : string IMap.Map = IMap.put 8 "a" IMap.empty
val i2c : char IMap.Map = IMap.put 8 #"a" IMap.empty

(*

To summarize, we implemeted the map directly, and then used it to
implement the set.

Now assume we want to go the other way around - first implement the
set directly. We encounter a problem when trying to use it to define a
map. It was easy taking a polymorphic type 'v Map, instantiate 'v to
unit and get monomorhic type of sets. But the reverse seems
impossible. How can one take a monomorhic set type and use it as a
polymorphic 'v Map? Note that the map functor shall not bind the value
type. The value type shall stay polymorphic, and only the key type
shall be bound in the resulting structure. So the map functor can only
take the key type as argument. In other words, we don't want
IntToStringMap.Map, but we want (string IntMap.map).

It's quite natural that one should be able to go both ways. Therefore,
I consider this as a shortcoming of StandardML - an example of a
slight lack of expressivity of the module language.

How could this be fixed in SuccessorML?

*)

[rossberg]

For that you'd need applicative functors.

[eduardoleon]

I don't think it's more elegant to recover maps from sets. It's simpler and better to do it the other way around: a set is a map whose associated element type is unit. Including an associated element by default, and setting it to unit whenever it's not needed, has other benefits too: it aids data structural bootstrapping, a general technique for building efficient and complete data structures from inefficient and/or incomplete ones.

[YawarRaza7349]

Trying to figure out why this can't work broke my brain, but I think I figured out one problem at least: Going from Set to 'v Map would result in the Set -> Set from put turning into something more like (forall 'v. 'v Map) -> (forall 'v. 'v Map) (equivalent to forall 'v1. (forall 'v2. 'v2 Map) -> 'v1 Map) rather than the desired forall 'v. 'v Map -> 'v Map. There isn't really a way to turn a particular function of the former into one of the latter.

The problem is that by the time you have a structure of signature SET, its Element type is monomorphized, and it "forgot" that it was created in a polymorphic way, so it can't be generalized back.

A related problem is that SML doesn't have a way to turn the monomorphic type Element into a polymorphic type 'v Element = M.Key * 'v. What's interesting is that, in isolation, this issue could be "fixed" by imagining all types as having an infinite number of phantom type variables, but then you still run into issues like the first thing I mentioned, not to mention the mind**** of thinking about how the prenex restriction behaves a language where every named type has the form forall (* infinite type variables *). (* ... *).

[rossberg]

All type-theoretic considerations aside, the idea of abstracting a type declaration after the fact by somehow injecting type parameters reminds me suspiciously of aspect-oriented programming, which essentially is an attempt to allow something analogous on the term level. And we all remember how great an idea that was.