It looks great! Thanks for putting time and effort into this. I think Racket in general will benefit from better support of immutable collections: it has already made the departure from Scheme by making cons-cells immutable. So, this is next logical step.
Maybe this belongs a bit more to your previous thread, but it can also relate here: I see you are making generic sequence interface to collections. Clojure from 1.7 seems to move more towards "reducebles" rather than "sequable". I have played with this idea for Racket a bit and it seems to work quite well (I called them "streams" but in effect they are "reducebles"): https://mobiusengineering.wordpress.com/2015/01/11/stateful-streams-in-scheme/ On Thursday, May 28, 2015 at 9:59:52 AM UTC+2, Alexis King wrote: > As a followup to my last thread regarding my generic collections library, I > have now created a package that uses it to define an entirely new data > structure. I've implemented Clojure's 32-way bitmapped tries to create a > persistent vector implementation. If you're interested in trying it out, it's > available as a package under the name ‘alexis-pvector’. > > Since my collections library only supports immutable collections, Racket's > built-in immutable vectors aren't very well-suited to my model. My > implementation of `conj` for Racket vectors is not exactly efficient: > > (define (conj vec item) > (vector->immutable-vector > (vector-append vec (vector item)))) > > With persistent vectors, the majority of conj operations are truly O(1), and > a small portion (about 3%) of them are O(log_32 n), so the performance > overhead should be negligible. > > Some initial profiling has proved promising: > > (time (void (extend #() (in-range 100000)))) > (time (void (extend (pvector) (in-range 100000)))) > > ;; output: > ;; cpu time: 41116 real time: 41336 gc time: 6176 > ;; cpu time: 124 real time: 124 gc time: 3 > > (define (random-set seq) > (define l (length seq)) > (for/fold ([seq seq]) > ([i (in-range 100000)]) > (set-nth seq (random l) (random)))) > > (time (void (random-set (vector->immutable-vector (make-vector 10000))))) > (time (void (random-set (extend (pvector) (take 10000 (in-naturals)))))) > > ;; output: > ;; cpu time: 3674 real time: 3677 gc time: 552 > ;; cpu time: 194 real time: 193 gc time: 8 > > Admittedly, these tests (especially the first one) are fairly biased towards > persistent vectors, but even so, they cover two of the most common vector > operations, so I think they're still relevant. > > Some rudimentary documentation is available, but the vast majority of the > vectors' interface is through the methods provided by alexis/collection. Try > them out! Let me know if you find any bugs or if you have any performance > considerations. > > As a final note, there are still some improvements that definitely need to be > made. Currently vectors print as #<pvector>, which is not very helpful, so > implementing a custom write procedure is high on my todo list. Also, this is > not an implementation of RRB vectors, which are an improved version of this > implementation but are more complex, so I have yet to look into how I could > adapt this to use that algorithm. > > Let me know what you think! > > Alexis -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
