I had not heard of AA trees before, but according to Wikipedia they sound like a variant of red-black trees. Clojure's built-in sorted-map and sorted-set implementations are called by the class name PersistentTreeMap in its Java implementation [1], and it implements a persistent version of a red-black tree. The source code won't give you lots of hand-holding, but it is there to see if you are interested.
Andy [1] https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/PersistentTreeMap.java On Mon, Aug 10, 2015 at 11:56 AM, William la Forge <laforg...@gmail.com> wrote: > Oh! The Java collection methods! For interop with Java, I'm guessing. Not > a personal priority, though I see that data.int-map does exactly that. > > The Clojure interfaces are much more reasonable. And really I want to > focus on the extensions to AA trees that I've developed, like virtual AA > trees that can be used in place of a B-tree. > > Many thanks for the links. Plenty here for me to dig through. And as a > newbie I've got to do a lot of reading if I ever want to write readable > code. > > > On Monday, August 10, 2015 at 7:29:26 AM UTC-4, Linus Ericsson wrote: >> >> The clojure core datastructures PersistentHashMap and PersistentVector >> are based on Philip Bagwells Ideal Hash Trees: >> http://lampwww.epfl.ch/papers/idealhashtrees.pdf >> >> Several of Chris Okasakis Purely Functional Datastructures are >> implemented already. http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf >> >> Clojure Toolbox http://www.clojure-toolbox.com/ mentions >> >> >> - Merkle <https://github.com/aphyr/merkle> >> - clj-tuple <https://github.com/ztellman/clj-tuple> >> - core.rrb-vector <https://github.com/clojure/core.rrb-vector> >> - data.finger-tree <https://github.com/clojure/data.finger-tree> >> - data.int-map <https://github.com/clojure/data.int-map> >> - data.priority-map <https://github.com/clojure/data.priority-map> >> - data.union-find <https://github.com/jordanlewis/data.union-find> >> - fast-zip <https://github.com/akhudek/fast-zip> >> - immutable-bitset <https://github.com/ztellman/immutable-bitset> >> - ordered <https://github.com/flatland/ordered> >> - ring-buffer <https://github.com/amalloy/ring-buffer> >> >> under "Datastructures". >> >> >> Monads has been implemented many times, check >> https://github.com/clojure/algo.monads for one example. >> >> >> Mary Rose Cook wrote an impressive as well as entertaining article on >> implementing Fibonacci Heaps in Clojure >> http://maryrosecook.com/blog/post/the-fibonacci-heap-ruins-my-life >> >> >> "Sketchy" datastructures exists, https://github.com/bigmlcom/sketchy >> (bloom, hyperloglog, min-distance hashing etc). Another Bloom Filter: >> https://github.com/kyleburton/clj-bloom >> >> >> It is said that splay trees aren't very suitable for implementing as an >> immutable structure because they mutate on read. >> >> >> I guess you'll get quite exact guidelines in the various core libraries >> on how to implement the Java collection methods (in general, all mutating >> methods throw methodNotImplementedExceptions). >> >> >> Good luck! >> >> >> /Linus >> >> >> On Monday, August 10, 2015 at 12:31:25 AM UTC+2, William la Forge wrote: >>> >>> I've done a lot with AA trees in the past, creating variations that are >>> immutable, durable (replacing b-trees) and versioned of vectors, maps and >>> sets. >>> >>> I would like to migrate these ideas from Java to Clojure, while >>> implementing the interfaces appropriate for Clojure. >>> >>> Still being very much a newbie, I'd appreciate some pointers, relevant >>> docs and/or examples. >>> >>> Thanks! >>> >> -- > You received this message because you are subscribed to the Google > Groups "Clojure" group. > To post to this group, send email to clojure@googlegroups.com > Note that posts from new members are moderated - please be patient with > your first post. > To unsubscribe from this group, send email to > clojure+unsubscr...@googlegroups.com > For more options, visit this group at > http://groups.google.com/group/clojure?hl=en > --- > You received this message because you are subscribed to the Google Groups > "Clojure" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to clojure+unsubscr...@googlegroups.com. > For more options, visit https://groups.google.com/d/optout. > -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups "Clojure" group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
