Subject: Typing collect
From: Jonathan Aldrich (jonal@cs.washington.edu)
Date: Mon Jan 10 2000 - 14:05:53 PST
When hacking up some Cecil code the other day, I decided it would be nice
to have the library function collect, from Smalltalk. What collect does
is it takes a collection of elements and a closure, applied the closure to
each element in turn, and returns a collection of the results. The result
collection should be the same kind of collection as the source collection.
This proved to be an interesting typing problem. I don't think it can be
done elegantly in the current Cecil system. Here is what I imagine the
well-typed code might look like:
---------------------------------
method collect(c@:`T[`S] <= Collection[S], cl@:&(S):`R):T[`R]
where exists type T[R]
{
let result := new T[R]();
c.do(&(e:S) {
result.add(cl.eval(e));
});
result;
}
---------------------------------------
There's some new syntax here. First of all, since I wanted to only define
collect once (not once for each collection class), I need to parameterize
over both the type of collection and the type of the elements: I don't
think you can easily do this in Cecil, especially the part about
returning the same type of collection but with a different element
type. The way to simulate this in current Cecil is to write
O(n) different collect functions.
Second, I needed to express the fact that the method only applies if the
collection type can hold the result type. One could do this with a
Collectible[T] F-bounded type, but this is inelegant because it may
require a declaration for each collection type.
Third, I needed a better creation mechanism, parameterized by both the
type of collection and the type of parameter. This may be the only place
where C++ is more powerful than Cecil<grin>. Again this requires
O(n) new-function declarations in Cecil.
Anyone have comments, or know of type systems that can do this? Vass, is
this an example the type systems you've been playing around with can
handle?
Jonathan :-)
This archive was generated by hypermail 2b25 : Tue Oct 03 2000 - 15:21:19 PDT