I have a long-running branch on github where I've been working on making the set datatype generic the way dictionaries are, and improving the generic system to support that effort. Some of the people here at Northeastern know about it, but I should probably make more people aware of the work. This is still a work in progress, it will be a while before it's ready for final review and push.
https://github.com/carl-eastlund/racket/tree/generic-sets For sets, the main purpose has been to add gen:set and allow the set datatype to be extended. Along with that, I've added mutable sets and make-custom-set, akin to make-custom-hash, and made lists usable as sets based on equal? comparisons. I've made an effort to put a lot of methods in gen:set, rather than the bare minimum to make a set work. My goal is for an implementer to provide whatever subset of the operations is necessary or desirable for a given set representation, and have fallback implementations that will automatically be used for other methods. For example, a simple representation might implement only set-member? and set-add, leaving set-union to the default behavior using repeated set-add. A more clever representation, such as red-black tree sets, might have a custom efficient set-union operation. At first I encoded this pattern by having separate back-end methods for implementers to provide via gen:set, and wrapper functions that called set operations if present and used default implementations otherwise. But this is cumbersome to program, and probably other generics will want it. So I extended define-generics to take a #:fallbacks option. Now generic methods can be given a fallback implementation in terms of the other methods that will be used for any representations that do not provide a specific implementation. I have also added a #:extend option to define-generics, so a new generic method group can extend one or more others. If generic method group A extends B and C, then implementations of methods for A should include any definitions for the methods of B and C, and the new type will belong to all three of A, B, and C. This feature is more speculative than #:fallbacks; I don't have a use for it in sets, but I think it would be valuable if we make pervasive use of generics in the near future. It would be much more convenient to use generics with #:extend if structure properties supported "diamond-shaped" derivation graphs. That is, if property A derives B and C, and B and C each derive D, currently make-struct-type raises an error because an implementation of A results in multiple implementations of D. This prevents some natural patterns of related generics. It would be nice to have some way of disambiguating implementations to allow this, for instance if a struct type directly provides an implementation for property D, it overrides any derived from A, B, and C so that they can all coexist. Right now I'm working on the behavior of make-custom-set, which has raised some questions about the behavior of make-custom-hash. I think I'll save that discussion for a separate email in the near future, so as to keep to more or less one topic and not go sprawling on for pages. More pages, I mean. Anyway, I hope this is all stuff that looks good to people, because I've put a lot of work into it, but I'm open to feedback if I've taken a wrong turn somewhere. Carl Eastlund
_________________________ Racket Developers list: http://lists.racket-lang.org/dev
