multi-Re: Abstract Collections

Robert Will robertw at
Tue Mar 23 09:59:22 EST 2004

hi all,

On Sun, 21 Mar 2004 ajb at wrote:
> I'm not happy with the "kind" of a collection.  I personally think that
> the type of the object in the collection is better connected with the
> type of the collection with a functional dependency.

Yeah, that may be a good thing to consider, but for now I think it's
simpler without.  FunDeps are a language extension, and I also think
they're rather complicated.

On Mon, 22 Mar 2004, Dylan Thurston wrote:
> Collection classes should not require Eq instances on the members,
> except when necessary!

Problem known, solution designed, not yet implemented:

On Mon, 22 Mar 2004, Dylan Thurston wrote:
> do you really need all of has, elem, (#), not_elem, and (/#) in the
> class (rather than defined as auxiliary functions, possibly optimised
> with fusion)?

You're right, I'll do that at once.

> For another example, how could zip possibly be given a more efficient
> implementation than the one you provide?

The one I provide is O(N*log N) on balanced structures (N times
'but_first'), and the new default implementation is O(N) (but not on all
collections, e.g. not on Queues).

> 'zip' obviously doesn't make sense on general collections.

Well, you can 'zip' Sets... but as for so many things we can as well put
it into the Sequence class and require an explicit conversion.  (Which
we'll hope is eliminated by the compiler.)

> Please try to simplify the interface more!

I already made efforts!  Anyway a user doesn't care, since the functions
have the same interface, whether they are in the class, or not.  And the
implementor doesn't care, if there are good default implementations.


More information about the Libraries mailing list