A Collections Framework?
in [Lisp]
|
Prev: scheme problem
Next: lisp student job offer
From: Norbert_Paul on 5 May 2010 04:18 Is there something Comparable ($\ddot\smile$) to the Java Collections Framework in LISP. I use functions like member, union, find, and stuff to design my algorithms but when they are to become productive with huge data sets I will need things like balanced-trees etc. and I don't want to re-invent the wheel. What I like in particular in Javas Collections is the separation of semantics (via "Interfaces") and implementation. There should be a similar standard in LISP. Also hash-tables look a bit suspect to me because, first, they are black-boxes and, second, make no runtime complexity guarantees (like "O(n log n) construction and O(log n) lookup") and, third, "The intent is that this mapping be implemented by a hashing mechanism, such as that described in Section 6.4 ``Hashing'' of The Art of Computer Programming, Volume 3 (pp506-549). In spite of this intent, no conforming implementation is required to use any particular technique to implement the mapping." (t_hash_t.htm) Norbert
From: Captain Obvious on 5 May 2010 05:06 NP> Is there something Comparable ($\ddot\smile$) to the NP> Java Collections Framework in LISP. Unfortunately, no. Closest I was able to find is cl-containers, but it is half-assed, to say it lightly. NP> productive with huge data sets I will need things like NP> balanced-trees etc. and I don't want to re-invent NP> the wheel. There are some implementations of balanced trees available, but all of them have some deficiencies. (At least at time I was checking it.) NP> What I like in particular in Javas Collections is NP> the separation of semantics (via "Interfaces") and NP> implementation. There should be a similar standard in NP> LISP. That would be nice, but I'd start with good underlying data structure implementations.
From: Pascal Costanza on 5 May 2010 05:39 On 05/05/2010 10:18, Norbert_Paul wrote: > Is there something Comparable ($\ddot\smile$) to the > Java Collections Framework in LISP. Fortunately not. ;) 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: Norbert_Paul on 5 May 2010 06:14 Captain Obvious wrote: > That would be nice, but I'd start with good underlying data structure > implementations. And then factor out the common semantics with, say, hash-table into some "abstract" collection? Use CLOS? [ ] Yes [ ] No
From: Captain Obvious on 5 May 2010 06:50
??>> That would be nice, but I'd start with good underlying data structure ??>> implementations. NP> And then factor out the common semantics with, say, hash-table into NP> some "abstract" collection? Yes, sort of. But there is no single "abstract collection", different collections have different sets of traits. For collections which are same in some aspect you can provide common interface functions. E.g. hash-table and a simple binary search tree would not have common interface, because one is associative, key-value collection and another is a simple collection. But you can implement an associative, key-value collection on top of binary search tree, and then it can have same interface as hash-table, to some extent -- insert, delete, enumerate, lookup. Tree-based associative collect, however, will have to provide additional interface because it is ordered. NP> Use CLOS? NP> [ ] Yes NP> [ ] No I think it needs dispatch on collection type, so definitely CLOS. Take a look at cl-containers, it has some good ideas, e.g. it provides classification of different sorts of containers and interfaces to work with them. Particularly, once you download it, you'll see introduction-to-cl-containers.pdf, which provides some good summary. |