A Collections Framework?
in [Lisp]
|
Prev: scheme problem
Next: lisp student job offer
From: Scott L. Burson on 8 May 2010 01:45 On May 7, 4:36 pm, "Captain Obvious" <udode...(a)users.sourceforge.net> wrote: > SLB> It surprises me a little that Lisp users are so resistant to > SLB> functional collections. > > They are fine with lists though, so I guess they don't use functional > collections either because they don't like API (too complex?) or just are > not aware of them. Yes, lists are often used functionally. I don't think the FSet API is complex, but it is a little different from what people are used to. > And if performance is not of a concern at all, then just using lists might > work. It's true. Lists can be very fast, but they can also be slow when they get long -- set intersection takes quadratic time, concatenation takes linear time, etc. > So, as I understand, performance-wise FSets are somewhere between lists (and > simple, ad-hoc data structures) and highly-optimized imperative data > structures. > Thus we can say it is a niche thing. You can say that if you like. But the intent of FSet, and the way I think about it and use it, is quite the opposite. To me, FSet collections are the right _default_ choice, the ones to use in those >80% of cases in which one has no specific reason to use something else. In this view, it's the imperative collections that are relegated to niche uses. I agree with your other point, though; FSet does not completely replace lists, which still are convenient for many purposes. > But if functional collections are implemented on language level -- e.g. as > in Clojure -- people just use them and do not complain. I think once people have a little experience with them, they seem very natural. Clojure does provide an additional incentive to use functional collections: they are necessary to work with the built-in STM. -- Scott
From: Norbert_Paul on 8 May 2010 09:11 Scott L. Burson wrote: >> But remember: "Premature optimization is the root of all evil". ... But remember what I said in my initial post. > I should add, since FSet is implemented using balanced trees, the one This is very interesting: Functional balanced trees! So I'll have a closer look at them. > problems. Every operation is within a (log n) factor of having the > best time complexity that it can be implemented with, AFAIK. ... Yes, that is the best possible. My primary concern was, if there is some "generic standard" for collections which makes it possible to just "plug in" the implementation which suits best for your need, be it a third party library or own implementing efforts. Maybe one could shadow the standard lisp functions like union, set-difference, find, member, some, stuff, more-stuff, yet-more-stuff in a "collections" package? Norbert.
From: Scott L. Burson on 8 May 2010 20:27 On May 8, 6:11 am, Norbert_Paul <norbertpauls_spam...(a)yahoo.com> wrote: > > My primary concern was, if there is some "generic standard" for > collections which makes it possible to just "plug in" the > implementation which suits best for your need, be it a third party > library or own implementing efforts. > > Maybe one could shadow the standard lisp functions like union, > set-difference, find, member, some, stuff, more-stuff, yet-more-stuff > in a "collections" package? FSet does this, so that most of the standard Lisp sequence functions are available in FSet as generic functions with definitions for lists and vectors as well as the FSet types. Since most of these functions iterate internally anyway, the generic function dispatch cost is unlikely to be noticeable. The major exception is ELT, which I specifically did not want to reuse in FSet because of the very different meanings (SETF (ELT COLL IDX) X) would have depending on whether COLL is a mutable or functional collection. I'm afraid it will never quite be possible to design a standard interface that is completely generic across both imperative and functional collections, for this reason. Besides, any code that updates a collection may have to be written a little differently to work with functional vs. imperative collections (though the cleverness of CL SETF makes this easier than one might think in simple cases). Nonetheless, for the operations (FIND etc.) that don't actually modify the collection, it's quite possible to have an extensible generic implementation, and as I say, FSet does this. It would be straightforward to add methods on these operations for new collection implementations such as CL-Collections. Oh yes -- Christophe Rhodes published a proposal for genericizing the CL sequence interface. I believe his proposal is implemented in SBCL, but I'm not aware that any other implementation has picked up on it. My recollection is that it doesn't quite work for functional collections, which is partly why I didn't try to use it, but for imperative collections it might be useful. -- Scott
From: Christophe Rhodes on 9 May 2010 03:13 "Scott L. Burson" <gyro(a)zeta-soft.com> writes: > Oh yes -- Christophe Rhodes published a proposal for genericizing the > CL sequence interface. I believe his proposal is implemented in SBCL, > but I'm not aware that any other implementation has picked up on it. > My recollection is that it doesn't quite work for functional > collections, which is partly why I didn't try to use it, but for > imperative collections it might be useful. I think it ought also to work for functional collections, with the same constraints as you note -- (setf elt) and related cases must signal an error rather than mutate. But I could be wrong; if we could tease out the reason for your recollection, that would be good. Best, Christophe
From: Alessio Stalla on 10 May 2010 04:43
On May 9, 2:27 am, "Scott L. Burson" <g...(a)zeta-soft.com> wrote: > Oh yes -- Christophe Rhodes published a proposal for genericizing the > CL sequence interface. I believe his proposal is implemented in SBCL, > but I'm not aware that any other implementation has picked up on it. I recently ported it on ABCL, with the intent of adapting Java collections to the Lisp sequence interface (not done yet). > My recollection is that it doesn't quite work for functional > collections, which is partly why I didn't try to use it, but for > imperative collections it might be useful. Indeed, the CL sequence API in some parts assumes mutable collections. I think you should be able to avoid all such parts and still have a fully usable API, but I haven't investigated deeply. Note also that the Java Collections API referred to by the OP also has some operations that involve mutation which are specified to be optional, while having a core set of operations that is designed to also work on immutable collections. Cheers, Alessio |