{"id":1176,"date":"2012-05-29T14:41:31","date_gmt":"2012-05-29T14:41:31","guid":{"rendered":"http:\/\/www.navision-blog.de\/?p=1176"},"modified":"2012-05-29T14:59:12","modified_gmt":"2012-05-29T14:59:12","slug":"porting-clojures-persistent-data-structures-to-net-part-1-of-n-persistentvector","status":"publish","type":"post","link":"http:\/\/www.navision-blog.de\/blog\/2012\/05\/29\/porting-clojures-persistent-data-structures-to-net-part-1-of-n-persistentvector\/","title":{"rendered":"Porting Clojure&rsquo;s persistent data structures to .NET part 1 of n &ndash; PersistentVector"},"content":{"rendered":"<p><a href=\"https:\/\/twitter.com\/#!\/richhickey\">Rich Hickey<\/a> created a very nice set of <a href=\"http:\/\/clojure.org\/data_structures\">persistent collections<\/a> for Clojure. I started to port them to <a href=\"https:\/\/github.com\/fsharp\/fsharpx\">FSharpx<\/a> and today I want to present the PersistentVector. The basic idea is that we want to have something like an array but immutable.<\/p>\n<blockquote>\n<h4><em>Vectors (IPersistentVector)<\/em><\/h4>\n<p> A Vector is a collection of values indexed by contiguous integers. Vectors support access to items by index in log32N hops. <strong>count<\/strong> is O(1). <strong>conj <\/strong>puts the item at the end of the vector.     <br \/>&#160;&#160;&#160;&#160; From <a href=\"http:\/\/clojure.org\/data_structures\">http:\/\/clojure.org\/data_structures<\/a><\/p><\/blockquote>\n<p>These vectors are very fast in practical applications since the depth of the underlying tree is not greater than 7. First <a href=\"https:\/\/github.com\/fsharp\/fsharpx\/blob\/master\/samples\/DataStructures\/Program.fs\">performance tests<\/a> show the following on my machine:<\/p>\n<p> <script src=\"https:\/\/gist.github.com\/2828783.js\"> <\/script>  <\/p>\n<p>These results are not that far away from the Clojure\/Java implementation (see below). The lookup seems to be a bit faster but assoc is slower. Maybe that has something to do with the internal array copy function of .NET: <\/p>\n<p> <script src=\"https:\/\/gist.github.com\/2828794.js\"> <\/script>  <\/p>\n<p>After installing the <a href=\"https:\/\/nuget.org\/packages\/FSharpx.Core\">FSharpx nuget package<\/a> can use this Vector&lt;T&gt; from C# like this:<\/p>\n<p> <script src=\"https:\/\/gist.github.com\/2828679.js\"> <\/script>  <\/p>\n<p>More samples can be found in the <a href=\"https:\/\/github.com\/fsharp\/fsharpx\/blob\/master\/tests\/FSharpx.DataStructures.Tests\/PersistentVectorTest.fs\">PersistentVectorTest.fs file<\/a>.<\/p>\n<p>Additional resources:<\/p>\n<ul>\n<li><a href=\"https:\/\/github.com\/clojure\/clojure\/blob\/master\/src\/jvm\/clojure\/lang\/PersistentVector.java\">Original implementation<\/a> <\/li>\n<li><a href=\"http:\/\/clojure.org\/data_structures\">Data structures in Clojure<\/a> <\/li>\n<li><a href=\"http:\/\/www.infoq.com\/presentations\/Value-Identity-State-Rich-Hickey\">Rich Hickey on &quot;Persistent Data Structures and Managed References&quot;<\/a> <\/li>\n<li><a href=\"http:\/\/blog.higher-order.net\/2009\/02\/01\/understanding-clojures-persistentvector-implementation\/\">Understanding Clojure\u2019s PersistentVector implementation<\/a><\/li>\n<li><a href=\"http:\/\/en.wikipedia.org\/wiki\/Hash_array_mapped_trie\">Hash array mapped trie<\/a><\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Rich Hickey created a very nice set of persistent collections for Clojure. I started to port them to FSharpx and today I want to present the PersistentVector. The basic idea is that we want to have something like an array but immutable. Vectors (IPersistentVector) A Vector is a collection of values indexed by contiguous integers. [&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,618,617,517],"_links":{"self":[{"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/posts\/1176"}],"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=1176"}],"version-history":[{"count":9,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/posts\/1176\/revisions"}],"predecessor-version":[{"id":1185,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/posts\/1176\/revisions\/1185"}],"wp:attachment":[{"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/media?parent=1176"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/categories?post=1176"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/tags?post=1176"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}