Returning different elements between a Hashtable and list<string> in F#

Question

I have two collections:

1. A list of strings
2. A hashtable

let properties = [
    "First";
    "Second"
  ]
let hash = System.Collections.Hashtable ()
  hash.Add("First", "Blub")
  hash.Add("Third", "Blob")

My goal is to find the key which is not in the properties list. My solution is so far:

// Casting my hashtable to a sequence to work with it easier
let keys:seq<string> = hash.Keys |> Seq.cast

// Casting the sequence to a set to get the difference in the end
let setAll = Set.ofSeq keys

// Getting all elements which are also in the properties list
let validKeySeq = Seq.filter (fun elem -> List.contains elem properties) keys

// Casting the sequence to a set to get the difference in the following line
let validKeys = Set.ofSeq validKeySeq

// Getting the element which is not in the list
Set.difference setAll validKeys

The above code works but is there a clearer, more concise or more idiomatic way of getting the element which is not in the list?

Answer 1

The most direct way would be with the Seq.except function, which returns a new sequence that omits any elements that appear in the other parameter.

table.Keys
|> Seq.cast<string>
|> Seq.except properties

I've named the hash table table rather than hash, because a Hashtable is a type of table that uses hashes, rather than a hash itself (I call this out, because I see 'hash' used like this quite often, and it's always confusing).

Seq.cast is still needed, because we are working with an untyped collection, but removes the complexity in the rest of the implementation: it would be nice to trap the error this throws when there is invalid input and qualify it.

It's fine to give nice names to each step of a computation as you have done (good practise, even), but using a pipeline like this is idiomatic F#.

Note that your implementation uses a linear-scan to check each key of the table against the list of properties; using Seq.except leaves the choice of method up to the BCL, but it most likely builds a HashSet from Properties and queries against that, which will generally give much better performance (closer to linear rather than quadratic).

Note also that your implementation can be simplified by inverting the filter: you are selecting those keys that are also in properties, but you can just as well filter for keys that are not properties (with the same cost).

let differentKeys = Seq.filter (fun elem -> not (List.contains elem properties)) keys

---

Let's package up the implementation nicely in a function, and add some inline documentation (///)

/// Enumerates all keys of the given table that are not in the sequence of properties
let nonPropertyKeys (table:IDictionary) properties =
    table.Keys
    |> Seq.cast<string>
    |> Seq.except properties

We can leave F# to infer the type of properties (or qualify it as seq<string> if you like) and return type (also seq<string>).

Note also that this function doesn't expect a HashTable specifically: it will accept any IDictionary, which may or may not be a useful generalisation for your scenario.

Generally you should avoid older types like Hashtable, and use newer (generic) versions, e.g. Dictionary<TKey, TValue> (and IReadOnlyDictionary<TKey, TValue>), and consider using a standard F# (immutable) collection like map<'key, 'value>. I assume your exact scenario doesn't permit this, however.

If we want to trap the InvalidCastException for an invalid input table (thrown when any key is not a string), then we need to actualise the result before returning.

let nonPropertyKeys (table:IDictionary) (properties:seq<string>) =
    try
        table.Keys
        |> Seq.cast<string>
        |> Seq.except properties
        |> Seq.toList
    with
    | :? InvalidCastException as ice -> raise (ArgumentException(nameof(table), "Table must only have string keys"))

This may be important for avoiding confusion, and makes the method more consistent in terms of failure condition with your original code (which also forces evaluation).

Alternatively, I note while your code produces a list, your comment mentions returning 'the key' that is not in properties, which you could achieve with the Seq.exactlyOne method: this will raise an exception if there are no elements in a collection, or if there is more than one element. It has a non-raising brother Seq.tryExactlyOne that returns an option 'a. Either of these would also force the evaluation of the original sequences.