[m-dev.] Re: For review: changes to graph.m

[Fergus Henderson]

Andrew Bromage, you wrote:
> 
> G'day.
> 
> I wrote:
> 
> > > Ignoring the possibility of changing between representations depending
> > > on the amount of data stored (eg represent sets by lists for "small"  
> > > data sets and trees for "big" sets), this is a perfect application of
> > > existential types, which are on the "to do" list.
> 
> Peter Schachte replied:
> 
> > How do existential types help with this?
> 
> Having a type class `set(T)' helps in that you have one interface
> which can be implemented in many ways.  However you need existential
> types if, for example, you wanted to create a list of sets.

You need existential types if you want to create a _heterogeneous_ list of
sets.

Specifically, I think what Andrew is suggesting is that instead of

	:- type_class set(Set) is {
		func union(Set, Set) = Set.
	}.

you would have

	:- type_class set(Set) is {
		func union(Set, Set) = any_set.
	}.

where any_set is defined using existential types:

	:- type any_set == some [T] T where set(T).

The problem with this suggestion is that you will end up doing dynamic
dispatch a lot; the compiler won't be able to optimize this dynamic dispatch
away, because it depends on dynamic data such as the size of the sets
involved, and so it can't be computed at compile time.

In many (most?) cases, this loss will outweigh the gain of using
different data structures for different sizes.

Instead, I think it would be better to just implement `list_or_tree_set'
as a separate type, using different top-level functors as Lee suggested
originally to distinguish between the small and large sets.
Then, the user can decide whether to use list_set (if they know their data
will be small), tree_set (if they know their data will be large), or
list_or_tree_set (if they know that their data will be of varying size
often enough to make it worth the overhead of switching representations
dynamically).

(Note: you could perhaps use an existential type, rather than a
discriminated union type, in the _implementation_ of list_or_tree_set.  
However, there wouldn't be much advantage in this.)

-- 
Fergus Henderson <fjh at cs.mu.oz.au>   |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>   |  of excellence is a lethal habit"
PGP: finger fjh at 128.250.37.3         |     -- the last words of T. S. Garp.