Make an RFC for a generic collection interface

[dbenoit17]

Racket2 should implement a generic API for ordered and unordered collections, something like https://github.com/lexi-lambda/racket-collections.

[dbenoit17]

In reference to #22, I think the optimization implications of generics should be discussed here. Depending on implementation, generic forms would either produce runtime overhead when dispatching to non-generic operations, OR dispatching would occur at compile-time in coordination with the type-checker if static inferencing were possible.

[jeapostrophe]

I think the optimization-angle is very important. A really nice thing would be a simple C-style operator overloading type system wherein if I declare a variable of type list, then map is specialized to the list version. An orthogonal concern (for me) is whether this declaration is enforced, and if so, whether it is done at runtime or compile-time.

[gus-massa]

I like the idea of generics for the most common forms.

I don't expect them to be very fast in the short term, but I'm optimistic in the long term.

There are some incompatibilities to iron out. For example:

(map add1 '(1 2 3))  ;==> '(2 3 4)
(vector-map add1 (vector 1 2 3))  ;==> #(2 3 4)
(hash-map (hash 'x 1 'y 2 'z 3) cons)  ;==> '((x . 1) (y . 2) (z . 3))

In the last, the result is a list (instead of a hash) and the arguments are in the "correct" order (that is different than the other two). Also, the last use a function with two arguments instead of one.

[AlexKnauth]

I think we should change the name of hash-map to something that doesn’t have the functor-map connotation. And then add a new function called hash-map that maps over just the values and returns a new hash-table to be consistent with list-map, vector-map, and the other functor-like map operations.

Then the generic map could delegate to that.

[97jaz]

I also think performance of generics is important -- and not just in the long term. People won't use them if they're too slow. And if people start by not using them, then the library ecosystem will avoid them, and it will be more difficult to get people to use them later. Maybe we should think about adding inline caches to Chez.

[sorawee]

There's one thing that blocks this. Racket currently doesn't distinguish lists that implement list interface and lists that implement set interface (or even lists that implement dictionary interface). Now, given a list, and call the genetic operation map on it, which map should we dispatch it to?

[jackfirth]

@sorawee I think we should fix that by making lists not implement the generic set or dict interfaces. They don't really live up to their contracts anyway - the lists (list 1) and (list 1 1) aren't equal but the set interface treats them as equal. Similar problems exist for (list (cons 'a 1) (cons 'a 2)) and (list (cons 'a 2) (cons 'a 1)). Lists are not a good excuse for an actual data structure.