title: What's the difference between `ImmutableSortedSet` and fsharp `Set`?
body: <p><a href="http://blogs.msdn.com/b/bclteam/archive/2012/12/18/preview-of-immutable-collections-released-on-nuget.aspx" rel="noreferrer">BCL has introduced a group of Immutable Collections</a></p>
  
  <p>I am wondering what's the difference between <code>ImmutableSortedSet</code> and the native FSharp <code>Set</code>? It seems that the performance signatures of both are similar. Also I saw somewhere that <code>SortedSet</code> is implemented as a Red Black Tree, so I guess <code>ImmutableSortedSet</code> does the same.</p>
  
  <p>What is the internal implementation of fsharp <code>map</code>? Is is <a href="http://en.wikibooks.org/wiki/F_Sharp_Programming/Sets_and_Maps#The_Set_Module" rel="noreferrer">Red Black Tree</a> as claimed here or <a href="http://fdatamining.blogspot.co.uk/2010/08/reading-f-projects-part-ii-f-set.html" rel="noreferrer">AVL tree</a> as found out here?</p>
  
  <p>In addition, why MSDN documents don't state clear what the actual data structure is for the library collection? I know these are implementation details and are about to change. My point is that if they don't want to bind the library data type to a certain type of well known data structure, they should at least offer a summery of all the methods performance signatures in terms of complexity?</p>