This book: Purely Functional Data Structures http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf
is a good read. Though, It only contains a small reference (half a page) about persistent data structures. On Mar 19, 2012, at 7:28 PM, Andy Fingerhut wrote: > I've got my copy of Cormen, Leiserson, and Rivest's book with me now, which > is the 3rd edition, and looking in the index under "persistent" it does have > one exercise in chapter 13 on that topic, and a mention later in the book > that is a paragraph or two long with a reference to a research paper. > > So while that book isn't a good reference for persistent data structures in > particular, it is a good reference for the more widely known (and some > not-so-widely known) mutable data structures. If you learn at least a few of > those, then you are very well prepared to understand Clojure's persistent > data structures, too, and there are blog posts on the topic that can get you > a lot of the way there (once you understand the basics), e.g.: > > http://blog.higher-order.net/2009/09/08/understanding-clojures-persistenthashmap-deftwice/ > > The book does assume a knowledge of how basic arrays work, but those are > quite simple and hopefully my message below is nearly as much as there is to > know about them. To get an understanding of data structures like hash tables > and some different kinds of trees, you can probably get there just reading a > few of the introductory sections at the beginning, and then jump to those > specific sections. Save all the stuff on algorithms for when and if you are > interested. > > Andy > > On Mar 18, 2012, at 8:57 PM, Andy Fingerhut wrote: > >> Feel free to ask follow-up questions on the basics privately, since many >> Clojure programmers are probably already familiar with them, whereas >> follow-up questions on persistent data structures are very on-topic, since I >> would guess many people who have studied computer science and/or programming >> for a while may not be familiar with them. >> >> The classic model of an array is based upon the implementation of physical >> RAM in a computer: a physical RAM, at a high level and leaving out details >> of variations, is a device where you either give it a command READ and an >> address, and it returns an 8-bit byte stored at that location, or you give >> it a WRITE command, an address, and an 8-bit value, and it stores the 8-bit >> value at the location given by the address. >> >> A classic array is a one-dimensional structure indexed by an integer i, >> usually from 0 up to some maximum value N, and every item in the array >> stores an item of the same size and type, e.g. all 32-bit integers, or all >> pointers to some object elsewhere in the memory. If every item fits in >> exactly B bytes, and the first item of the array begins at address A in the >> memory, then item i will be at address A+B*i in the memory. In terms of >> performance, computers are designed to be able to access any address in >> their memory in the same amount of time, no matter what address it is stored >> at, so with a couple of instructions to calculate A+B*i, the computer can >> read or write any element of an array within a constant amount of time >> (constant meaning it doesn't get larger or smaller depending upon the size >> of the array -- it is always the same no matter the array's size). With >> other non-array data structures like trees, accessing an element takes >> longer as the data structure grows to contain more items. >> >> I don't recall if it covers persistent data structures like the ones most >> commonly used in Clojure, but Cormen, Leiserson, and Rivest's "Introduction >> to Algorithms" is used in many colleges as a text in courses on algorithms >> and data structures. There are probably other books that would be better as >> a "primer", and it does assume you are comfortable with at least algebra and >> a bit more math, but if you got through a chapter of it and understood even >> half of it, you'd have learned something worth knowing about the subject. >> >> http://www.amazon.com/Introduction-Algorithms-Includes-CD-Rom-Thomas/dp/0072970545/ref=sr_1_2?ie=UTF8&qid=1332128117&sr=8-2 >> >> There is a newer edition than the one I linked to, but an older used copy >> for $25.00 might be closer to what you want if you aren't sure yet. >> >> Andy >> >> On Mar 15, 2012, at 12:15 PM, Nic Long wrote: >> >>> Hi all, >>> >>> I am starting to learn Clojure after buying the book 7 Languages in 7 >>> Weeks (really interesting read) and working through the examples >>> there. But my background is PHP (and no Computer Science degree) so my >>> understanding of data structures and in general, my understanding of >>> low-level CS ideas, is pretty limited to say the least - PHP only has >>> arrays (which I read are only 'ordered hash tables' in fact) and >>> objects so I've never had to think hard about which data structures to >>> use, nor how they actually work. >>> >>> So I guess I'm asking whether anyone can recommend some good primers >>> on data structures, both as they relate to Clojure, but also how they >>> work in the fundamentals - e.g. what exactly is the classic model of >>> an 'array' and how does it work, etc. I have read the various >>> performance commitments for the data-types in Clojure on the .org site >>> but even things like Big O notation are still pretty new to me. >>> >>> I'm sure this stuff is pretty basic for many, but I don't know it and >>> would like to! >>> >>> I'm not afraid of some heavy reading; I'd rather get a really deep and >>> solid grasp of the fundamentals, then a quick surface-level solution. >>> If I'm to develop as a programmer I feel like I need to get looking >>> under the hood as it were, even though I can get by in PHP (for the >>> most part anyway) without this kind of understanding. >>> >>> Thanks in advance, >>> >>> Nic >>> >>> -- >>> 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 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 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
