{"id":1186,"date":"2012-05-29T18:15:00","date_gmt":"2012-05-29T18:15:00","guid":{"rendered":"http:\/\/www.navision-blog.de\/?p=1186"},"modified":"2012-05-30T13:50:18","modified_gmt":"2012-05-30T13:50:18","slug":"porting-clojures-persistent-data-structures-to-net-part-2-of-n-transientvector","status":"publish","type":"post","link":"http:\/\/www.navision-blog.de\/blog\/2012\/05\/29\/porting-clojures-persistent-data-structures-to-net-part-2-of-n-transientvector\/","title":{"rendered":"Porting Clojure&rsquo;s persistent data structures to .NET part 2 of n &ndash; TransientVector"},"content":{"rendered":"<p>In the <a href=\"http:\/\/www.navision-blog.de\/2012\/05\/29\/porting-clojures-persistent-data-structures-to-net-part-1-of-n-persistentvector\/\">last post<\/a> I wrote about the PersistentVector which I ported from Clojure to .NET. It\u2019s implemented as an immutable <a href=\"http:\/\/en.wikipedia.org\/wiki\/Hash_array_mapped_trie\">hash array mapped trie<\/a> which optimizes the constant factors so that we can assume O(1) for count, nth, conj, assocN, peek and pop.<\/p>\n<p>But for some applications Rich Hickey <a href=\"https:\/\/github.com\/clojure\/clojure\/blob\/master\/src\/jvm\/clojure\/lang\/PersistentVector.java\">shows us<\/a> that we can optimize the constant factors even further. If we are sure that we are only holding exactly one reference to the vector than we can mutate the underlying representation instead of copying the arrays on every change. This idea is implemented in the <a href=\"https:\/\/github.com\/fsharp\/fsharpx\/blob\/master\/src\/FSharpx.Core\/DataStructures\/Vector.fs\">TransientVector<\/a> which I also ported from <a href=\"https:\/\/github.com\/clojure\/clojure\">Clojure.Core<\/a> to <a href=\"https:\/\/github.com\/fsharp\/fsharpx\">FSharpx<\/a>.<\/p>\n<p>Let&#8217;s look at a small example. Here we want to convert a collection to a PersistentVector:<\/p>\n<p> <script src=\"https:\/\/gist.github.com\/2829823.js\"> <\/script>  <\/p>\n<p>As you can see we iterate over the collection and conj the items to the current PersistentVector. But in every step we forget the reference to the last version. This is exactly the point where can use TransientVector:<\/p>\n<p> <script src=\"https:\/\/gist.github.com\/2829801.js\"> <\/script>  <\/p>\n<p>Here are the results:<\/p>\n<p> <script src=\"https:\/\/gist.github.com\/2836433.js\"> <\/script>  <\/p>\n<p>Most higher-order functions on vectors like <strong>map<\/strong> are also implemented with this trick.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>In the last post I wrote about the PersistentVector which I ported from Clojure to .NET. It\u2019s implemented as an immutable hash array mapped trie which optimizes the constant factors so that we can assume O(1) for count, nth, conj, assocN, peek and pop. But for some applications Rich Hickey shows us that we can [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[12,448],"tags":[616,664,609,617],"_links":{"self":[{"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/posts\/1186"}],"collection":[{"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/comments?post=1186"}],"version-history":[{"count":3,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/posts\/1186\/revisions"}],"predecessor-version":[{"id":1189,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/posts\/1186\/revisions\/1189"}],"wp:attachment":[{"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/media?parent=1186"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/categories?post=1186"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/tags?post=1186"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}