A Collections Framework?
in [Lisp]
|
Prev: scheme problem
Next: lisp student job offer
From: Alessio Stalla on 12 May 2010 17:23 On 12 Mag, 19:43, Alan Malloy <alan.NO.S...(a)malloys.org> wrote: > Alessio Stalla wrote: > > On May 12, 9:00 am, Norbert_Paul <norbertpauls_spam...(a)yahoo.com> > > wrote: > >> Alessio Stalla wrote: > >>> Suppose I want to add a new method called "cons" which, when called on > >>> a Collection C and an object O, will return a new Collection with O > >>> appended in front of C. What would the signature of that method be? > >>> Collection.cons(T obj) : Collection -> loses type information, needs a > >>> cast (e.g. to ImmutableLinkedList), also casts in Java are dynamic > >>> type checks so an inefficiency (though small) is introduced > >> If you used generics there are less type casts. Most generic type > >> information is only for the compiler and will be erased at run time. > > > I'm not talking about generics here but concrete Collection subclasses > > which I may want to use if I want to leverage some specific methods. > > >>> Collection<COLLTYPE>.cons(T obj) : COLLTYPE -> ugly, every concrete > >>> collection class C must implement Collection<C> > >> This is against the API. > > > I was imprecise: that was supposed to read Collection<COLLTYPE, T> and > > C<T> implements Collection<C, T>. > > >>> <COLLTYPE> Collection.cons(T obj) : COLLTYPE -> probably the best, > >>> it's unsafe (caller decides the type), but we're Lispers so we don't > >>> care ;) - but fits badly with the rest of Java > >>> others? I can't come up with any. > >> I had made my own > > >> static <T> Collection<T> disjointUnion(Collection<T> head, Collection<T> tail); > > >> which is iterated head first and then tail, and then could do > > >> disjointUnion(singletonSet(obj),c); > > > That's nice, but it has two problems that make it not suitable to be a > > general purpose API, imho: > > > 1. it cannot be specialized on a per-class basis; if a certain > > Collection can implement disjointUnion more efficiently, you have to > > make it a separate overload and resolve it statically rather than > > using late binding. > > 2. it loses type information: if I'm using LinkedLists, that method > > will return Collection, and I'll have to cast to LinkedList if I want > > to use some LinkedList-specific method. > > > Of course if that was Lisp and not Java, neither of the two problems > > would be there ;) > > > Alessio > > I don't think either of these complaints holds water. > > 1) You could define an AbstractCollection whose "naive" cons method > calls Collections.disjointUnion; if you can write a better > implementation then override it, otherwise don't. > 2) This hasn't been true since 1.5, years ago. Subclasses are permitted > to return a more specific class than the interface requires. Callers who > aren't aware of (or don't care about) LinkedList will get a Collection, > while you get a LinkedList. I was referring to the static method proposed by Norbert Paul; but still, you have a valid point with 2), I hadn't considered it. So indeed the collections API could be extended to better support immutable collections (though of course only Sun/Oracle can do it). To get back on topic a bit, I think the CL sequence API also lacks a "generic cons" function, or am I missing something? Of course for lists and vectors alone it wouldn't have made much sense (who would build a vector by consing individual elements?), but with extensible sequences, and in particular immutable ones, I think it's definitely needed. Alessio
From: Pascal Costanza on 14 May 2010 09:10 On 11/05/2010 10:04, Alessio Stalla wrote: > About iterators: the CL sequence API per se does not say anything > about iterators. Of course, you have MAP and REDUCE. Pascal -- My website: http://p-cos.net Common Lisp Document Repository: http://cdr.eurolisp.org Closer to MOP & ContextL: http://common-lisp.net/project/closer/
From: Captain Obvious on 15 May 2010 08:57 s> In what way do CL generic functions and CLOS fail to be many times s> more powerful and better at expressing interfaces than Java s> interfaces? Is this "Have you stopped beating your wife?" sort of a question? :) I do not think that there is any problem with CLOS. A problem with "collections framework" for CL is just that nobody wrote one. You see, there are lots of wealthy companies which use Java, and they can afford to hire lots of programmers to write that framework for Java. There are less companies working with CL, and, apparently, they address their needs with existing solutions, so there is no great need to a great unified library. It would be nice to have one, but isn't strictly required, as one can use lists, or hash tables, or FSet library, or one of btree libraries, or uses pieces of cl-contaniers which actually work, or write their own implementation. So lack of an unified library is not a showstopper. One can benefit from it providing unified interfaces so he can switch between different underlying implementations and see if there is a speedup. But he can as well write his own adapter functions for this, that might be just few lines of code... I guess a problem with it is that framework which really covers everything is a tremendous work. You can easily write adapter functions which will work both for balanced trees and for hash-tables (for example), but taking all possible trait combinations into account is hard. To start with, there is a problem with classification even before you come to an implementation. There are associative containers, iteratable containers, searchable ones, ones where you can insert in the middle, into one or both of its ends, or it just doesn't matter where you insert, there are ones which support indexing and ones which do not... Some of these traits are orthogonal and some are not. For example, if collection provides index access, then for sure it is ordered and iteratable. Then there are multiple ways to look at one particular collection -- e.g. if you have a balanced tree with pairs, you can either consider it as an associative container or not. Maybe you want to provide both interfaces? I don't know if it is possible to copy Java or C++ collection library. Those are different languages and choices library writers have made might be not really optimal for CL. So a problem is on conceptual level, not technical level. If you're a Lisp neophyte, you might be over-excited with language features. Don't forget that great language features do not write code for you, they just let you to express your thoughts in more clean way.
From: Tamas K Papp on 15 May 2010 09:37 On Sat, 15 May 2010 15:57:25 +0300, Captain Obvious wrote: > A problem with "collections framework" for CL is just that nobody wrote > one. I can't say that I am missing a super-general standardized collections framework. I find that the building blocks CL provides (lists, arrays, hash tables) are enough most of the time, and when they aren't, you can easily create new ones. You can even extend de facto standard libraries like iterate to traverse your custom collections (where applicable). Reading this thread was interesting, but I am yet to be convinced that writing a collections framework in CL that is similar to Java's is worth the trouble. Tamas
From: Tim Bradshaw on 15 May 2010 10:16
On 2010-05-15 13:57:25 +0100, Captain Obvious said: > To start with, there is a problem with classification even before you > come to an implementation. > There are associative containers, iteratable containers, searchable > ones, ones where you can insert in the middle, into one or both of its > ends, or it just doesn't matter where you insert, there are ones which > support indexing and ones which do not... > Some of these traits are orthogonal and some are not. For example, if > collection provides index access, then for sure it is ordered and > iteratable. I think there's really a choice here. One can either spend some enormous amount of time designing and implementing a vast framework to do everything you might ever want to do, discover your design is wrong, drink some coffee, iterate the design a few times until it looks good, discover the implementation's performance sucks, drink more coffee, iterate it a few times until it doesn't suck as much, discover the language really needs new features to make the thing usable at all, do a little speed, implement them, get them wrong [*], iterate that a few times, discover it is now so complicated no one can understand it, coffee, speed, a little crack maybe, write a book or two to describe it, discover that Microsoft has implemented a culturally compatible but better version of all this and stolen your user base, mostly crack by now really though you pretend it's all under control, struggle to compete for a while, lose your job, live on the street, just temporarily you understand, hustling for whetever you can get, smell really bad, die in some shop doorway. Or you can, you know, not do that and just implement what you actually need. I vote for the second of these options. [*] Java is approximately here. |