Thanks Andy. PersistentTreeMap is a helpful source of ideas for me. For example, it pointed me to the RT class which holds DefaultComparator. And before looking at it I was not even aware of the sorted-set-by function in Clojure. :-)
On Monday, August 10, 2015 at 3:25:43 PM UTC-4, Andy Fingerhut wrote: > > 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 <lafo...@gmail.com > <javascript:>> 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 clo...@googlegroups.com >> <javascript:> >> Note that posts from new members are moderated - please be patient with >> your first post. >> To unsubscribe from this group, send email to >> clojure+u...@googlegroups.com <javascript:> >> 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+u...@googlegroups.com <javascript:>. >> 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.
