{"id":584,"date":"2008-11-10T13:55:26","date_gmt":"2008-11-10T12:55:26","guid":{"rendered":"http:\/\/www.navision-blog.de\/2008\/11\/10\/a-immutable-sorted-list-in-fsharp-part-ii\/"},"modified":"2008-11-10T14:11:33","modified_gmt":"2008-11-10T13:11:33","slug":"a-immutable-sorted-list-in-fsharp-part-ii","status":"publish","type":"post","link":"http:\/\/www.navision-blog.de\/blog\/2008\/11\/10\/a-immutable-sorted-list-in-fsharp-part-ii\/","title":{"rendered":"A immutable sorted list in F# &#8211; part II"},"content":{"rendered":"<\/p>\n<p><a href=\"http:\/\/www.navision-blog.de\/2008\/11\/10\/a-immutable-sorted-list-in-fsharp\/\">Last time<\/a> I showed how the immutable set implementation in F# can be used to get a immutable sorted list. As a result of using sets, the shown version doesn&#8217;t support repeated items. This lack can be wiped out by using an additional dictionary (immutable &quot;Map&quot; in F#) which stores the count of each item.<\/p>\n<p>At first I define two basic helper functions for the dictionary:<\/p>\n<pre class=\"code\"><span style=\"color: blue\">module <\/span>MapHelper =\n  <span style=\"color: blue\">let <\/span>addToMap map idx = \n    <span style=\"color: blue\">let <\/span>value = Map.tryfind idx map\n    <span style=\"color: blue\">match <\/span>value <span style=\"color: blue\">with\n      <\/span>| Some(x) <span style=\"color: blue\">-&gt; <\/span>Map.add idx (x+1) map\n      | None <span style=\"color: blue\">-&gt; <\/span>Map.add idx 1 map\n      \n  <span style=\"color: blue\">let <\/span>removeFromMap map idx = \n    <span style=\"color: blue\">let <\/span>value = Map.tryfind idx map\n    <span style=\"color: blue\">match <\/span>value <span style=\"color: blue\">with\n      <\/span>| Some(x) <span style=\"color: blue\">-&gt; \n         if <\/span>x &gt; 1 <span style=\"color: blue\">then \n           <\/span>Map.add idx (x-1) map \n         <span style=\"color: blue\">else \n           <\/span>Map.remove idx map\n      | None <span style=\"color: blue\">-&gt; <\/span>map\n      \n<span style=\"color: blue\">open <\/span>MapHelper<\/pre>\n<p>Now I can adjust my sorted list implementation: <\/p>\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  numbers: Map&lt;'a,int&gt;;\n  count: int}\n   \n  <span style=\"color: blue\">member <\/span>x.Min = x.items.MinimumElement\n  <span style=\"color: blue\">member <\/span>x.Items = \n    <strong>seq {\n      <span style=\"color: blue\">for <\/span>item <span style=\"color: blue\">in <\/span>x.items <\/strong><strong><span style=\"color: blue\">do            \n        for <\/span>number <span style=\"color: blue\">in <\/span>[1..x.GetCount item] <\/strong><strong><span style=\"color: blue\">do\n          yield <\/span>item}<\/strong>\n          \n  <span style=\"color: blue\">member <\/span>x.Length = x.count\n  <span style=\"color: blue\">member <\/span>x.IsEmpty = x.items.IsEmpty\n  <span style=\"color: blue\">member <\/span>x.GetCount item = \n    <span style=\"color: blue\">match <\/span>Map.tryfind item x.numbers <span style=\"color: blue\">with\n      <\/span>| None <span style=\"color: blue\">-&gt; <\/span>0\n      | Some(y) <span style=\"color: blue\">-&gt; <\/span>y\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\">let <\/span>m = list |&gt; List.fold_left addToMap Map.empty\n      \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) <span style=\"color: blue\">and\n      <\/span>numbers = m <span style=\"color: blue\">and\n      <\/span>count = list.Length}\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 \n      <\/span>items = x.items.Add(y);\n      numbers = addToMap x.numbers y;\n      count = x.count + 1} \n    \n  <span style=\"color: blue\">member <\/span>x.Remove(y) =     \n    <span style=\"color: blue\">if <\/span>x.GetCount y &gt; 0 <span style=\"color: blue\">then\n      <\/span>{x <span style=\"color: blue\">with \n        <\/span>items = x.items.Remove(y);\n        numbers = removeFromMap x.numbers y;\n        count = x.count - 1}\n    <span style=\"color: blue\">else\n      <\/span>x        <\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Last time I showed how the immutable set implementation in F# can be used to get a immutable sorted list. As a result of using sets, the shown version doesn&#8217;t support repeated items. This lack can be wiped out by using an additional dictionary (immutable &quot;Map&quot; in F#) which stores the count of each item. [&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,474,473,471,472],"_links":{"self":[{"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/posts\/584"}],"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=584"}],"version-history":[{"count":1,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/posts\/584\/revisions"}],"predecessor-version":[{"id":586,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/posts\/584\/revisions\/586"}],"wp:attachment":[{"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/media?parent=584"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/categories?post=584"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/tags?post=584"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}