{"id":579,"date":"2008-11-10T12:06:29","date_gmt":"2008-11-10T11:06:29","guid":{"rendered":"http:\/\/www.navision-blog.de\/2008\/11\/10\/a-immutable-sorted-list-in-fsharp\/"},"modified":"2008-11-10T13:57:50","modified_gmt":"2008-11-10T12:57:50","slug":"a-immutable-sorted-list-in-fsharp","status":"publish","type":"post","link":"http:\/\/www.navision-blog.de\/blog\/2008\/11\/10\/a-immutable-sorted-list-in-fsharp\/","title":{"rendered":"A immutable sorted list in F# &#8211; part I"},"content":{"rendered":"<p>F# supports a powerful implementation of immutable lists (see <a href=\"http:\/\/diditwith.net\/2008\/03\/03\/WhyILoveFListsTheBasics.aspx\">Dustin&#8217;s introduction<\/a>). But for my current work I needed a sorted list and of course I wanted it the F#-way, which means immutable. I didn&#8217;t want to reinvent the wheel so I asked <a href=\"http:\/\/cs.hubfs.net\/forums\/thread\/7646.aspx\">my question in the hubFS forum<\/a>. <\/p>\n<p>It turned out (thanks to <a href=\"http:\/\/strangelights.com \">Robert<\/a>) that F# uses <a href=\"http:\/\/en.wikipedia.org\/wiki\/Red-black_tree\">red-black trees<\/a> to give a fast implementation for the immutable set. This means that a set in F# stores all elements in a <em>balanced binary tree<\/em> and searching for an element costs only <em>O(log n)<\/em>. As a side effect all elements can be visited in the underlying order, which means the set implementation gives a possibility for implementing a sorted list. The only limitation is that a set usually don&#8217;t store objects more than once.<\/p>\n<p>The next problem I got, was that my sorted list needs a specific ordering function. The standard F# set implementation uses structural comparison to give an order, which is not the order I need. But <a href=\"http:\/\/laurent.le-brun.eu\/\">Laurent<\/a> mentioned the <em>Set.Make<\/em> function in the F# PowerPack. This function creates a new set type for the given ordering function. The only problem with Set.Make is that it was only designed for OCaml compatibility. But with this hint I was able to put all information together and got a nice immutable sorted list implementation for F#:<\/p>\n<pre class=\"code\"><span style=\"color: green\">\/\/ wrap orderingFunction as Collections.Generic.IComparer\n<\/span><span style=\"color: blue\">type <\/span>'a FComparer =\n  {compareF: 'a <span style=\"color: blue\">-&gt; <\/span>'a <span style=\"color: blue\">-&gt; <\/span>int}\n  <span style=\"color: blue\">static member <\/span>Create(compareF) =\n    {<span style=\"color: blue\">new <\/span>'a FComparer <span style=\"color: blue\">with <\/span>compareF = compareF}\n  <span style=\"color: blue\">interface <\/span>Collections.Generic.IComparer&lt;'a&gt; <span style=\"color: blue\">with\n    member <\/span>x.Compare(a, b) = x.compareF a b    <\/pre>\n<pre class=\"code\"><span style=\"color: green\">\/\/ a immutable sorted list - based on F# set\n<\/span><span style=\"color: blue\">type <\/span>'a SortedFList =\n {items: Tagged.Set&lt;'a,Collections.Generic.IComparer&lt;'a&gt;&gt; }\n   \n  <span style=\"color: blue\">member <\/span>x.Min = x.items.MinimumElement\n  <span style=\"color: blue\">member <\/span>x.Items = seq {<span style=\"color: blue\">for <\/span>item <span style=\"color: blue\">in <\/span>x.items <span style=\"color: blue\">do yield <\/span>item}\n  <span style=\"color: blue\">member <\/span>x.Length = x.items.Count\n  <span style=\"color: blue\">member <\/span>x.IsEmpty = x.items.IsEmpty\n    \n  <span style=\"color: blue\">static member <\/span>FromList(list, sortFunction) = \n    <span style=\"color: blue\">let <\/span>comparer = FComparer&lt;'a&gt;.Create(sortFunction)\n    {<span style=\"color: blue\">new <\/span>'a SortedFList <span style=\"color: blue\">with \n      <\/span>items = Tagged.Set&lt;'a&gt;.Create(comparer,list)}\n      \n  <span style=\"color: blue\">static member <\/span>FromListWithDefaultComparer(list) = \n    SortedFList&lt;'a&gt;.FromList(list,compare)    \n      \n  <span style=\"color: blue\">static member <\/span>Empty(sortFunction) = \n    SortedFList&lt;'a&gt;.FromList([],sortFunction)\n      \n  <span style=\"color: blue\">static member <\/span>EmptyWithDefaultComparer() = \n    SortedFList&lt;'a&gt;.Empty(compare)            \n       \n  <span style=\"color: blue\">member <\/span>x.Add(y) =     \n    {x <span style=\"color: blue\">with <\/span>items = x.items.Add(y)}    <\/pre>\n<pre class=\"code\"><span style=\"color: blue\">  member <\/span>x.Remove(y) =     \n    {x <span style=\"color: blue\">with <\/span>items = x.items.Remove(y)}    <\/pre>\n<p>Please note that this implementation stores every item only once. <a href=\"http:\/\/www.navision-blog.de\/2008\/11\/10\/a-immutable-sorted-list-in-fsharp\/\">Next time<\/a> I will show a version which allows to store repeated items.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>F# supports a powerful implementation of immutable lists (see Dustin&#8217;s introduction). But for my current work I needed a sorted list and of course I wanted it the F#-way, which means immutable. I didn&#8217;t want to reinvent the wheel so I asked my question in the hubFS forum. It turned out (thanks to Robert) that [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[27,23,448,8,10],"tags":[664,473,471,472],"_links":{"self":[{"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/posts\/579"}],"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=579"}],"version-history":[{"count":5,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/posts\/579\/revisions"}],"predecessor-version":[{"id":585,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/posts\/579\/revisions\/585"}],"wp:attachment":[{"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/media?parent=579"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/categories?post=579"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/tags?post=579"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}