5

I'm observing F#'s Map is always ordered based on its keys. Does F# provide any alternative to an ordered dictionary?

I wanted to ask before using a C# Dictionary as an alternative.

Scott Nimrod
  • 11,206
  • 11
  • 54
  • 118
  • 5
    Why do you want a map that's not ordered? Whether it is ordered or not should typically not have any effect on your code - if you're using a map, it's typically because you want a way of associating values with keys - and for this, the implementation does not matter (aside from complexity). – Tomas Petricek Apr 19 '19 at 00:31
  • @TomasPetricek the difference does affect the code, and complexity is an important reason to pick one type over the other. That's why there are so many questions asking about [Dictionary vs SortedDictionary](https://stackoverflow.com/questions/5772476/when-should-i-use-a-sorteddictionary-instead-of-a-dictionary) `O(1)` vs `O(log(n))` access is an important difference when you don't care about order – Panagiotis Kanavos Apr 19 '19 at 07:19
  • @TomasPetricek if [that answer still holds](https://stackoverflow.com/questions/3396196/f-fsharpmap-vs-dictionary-performance) then map is 5-40 times slower than Dictionary. That's a huge difference in high-throughput application like web services, where such delays translate to servers required for the same load – Panagiotis Kanavos Apr 19 '19 at 07:23
  • @PanagiotisKanavos - The way PersistentHashMap is implemented makes it likely faster than F#'s default `Map` implementation, though I don't know of any benchmarks off the top of my head. But don't assume that 5-40 times slower figure for F#'s Map applies to PersistentHashMap until you've seen a benchmark; the implementations are completely different. – rmunn Apr 19 '19 at 20:31
  • 1
    @PanagiotisKanavos Sure, immutable map is slower than a mutable hashtable and that's a good reason for using it in some cases, but that's not answering my question. My question is, why does the OP want a map that's not ordered? – Tomas Petricek Apr 20 '19 at 11:34

1 Answers1

8

FSharpx.Collections has the PersistentHashMap, which isn't ordered.

rmunn
  • 34,942
  • 10
  • 74
  • 105
  • Why that instead of a Dicttionary<> ? – Panagiotis Kanavos Apr 19 '19 at 07:17
  • 3
    @PanagiotisKanavos - Because of its persistent properties, which are the same as F#'s `Map` implementation: adding or removing an item creates a new collection instead of modifying the existing collection. `Dictionary<>` may be faster, but its mutable nature makes it prone to bugs that an immutable collection avoids. So unless you actually *know* that you need that speed, most of the time using `Dictionary<>` instead of a persistent collection is a case of premature optimization. – rmunn Apr 19 '19 at 20:29