What's a good way to manage a lot of loosely related components in F#?

Question

I'm trying to translate an idea I had from OOP concepts to FP concepts, but I'm not quite sure how to best go about it. I want to have multiple collections of records, but have individual records linked across the collections. In C# I would probably use multiple Dictionary objects with an Entity-specific ID as a common key, so that given any set of the dictionaries, a method could extract a particular Entity using its ID/Name.

I guess I could do the same thing in F#, owing to its hybrid nature, but I'd prefer to be more purely functional. What is the best structure to do what I'm talking about here?

I had considered maybe a trie or a patricia trie, but I shouldn't need very deep name searching, and I'm more likely to have one or two of some things and lots of other things. It's a game design idea, so, for example, you'd only have one "Player" but could have tons of "Enemy1", "Enemy2" etc.

Is there a really good data structure for fast keyed lookup in FP, or should I just stick to Dictionary/Hashmaps?

Answer 1

Use the F# module Collections.Map. My bet is that it implements balanced binary search trees, the data structure of choice for this task in functional programming.

Tries are hard to program and mostly useful in specialized applications such as search engine indexing, where they are commonly used as a secondary store on top of an array/database/etc. Don't use them unless you know you need to.

Answer 2

A usual functional data structure for representing dictionaries that's available in F# is Map (as pointed out by larsmans). Under the cover, this is implemented as a ballanced binary tree, so the complexity of lookup is O(log N) for a tree containing N elements. This is slower than hash-based dictionary (which has O(1) for good hash keys), but it allows adding and removing elements without copying the whole collection - only a part of the tree needs to be changed.

From your description, I have the impression that you'll be creating the data structure only once and then using it for a long time without modifying it. In this case, you could implement a simple immutable wrapper type that uses Dictionary<_, _> under the cover, but takes all elements as a sequence in the constructor and doesn't allow modifications:

type ImmutableMap<'K, 'V when 'K : equality>(data:seq<'K * 'V>) =  // '
  // Store data passed in constructor in hash-based dictionary
  let dict = new System.Collections.Generic.Dictionary<_, _>()
  do for k, v in data do dict.Add(k, v)
  // Provide read-only access
  member x.Item with get(k) = dict.[k]

let f = new ImmutableMap<_,_ >( [1, "Hello"; 2, "Ahoj" ])  
let str = f.[1]

This should be faster than using F# Map as long as you don't need to modify the collection (or, more precisely, create copies with elements added/removed).