PersistentHashMap.containsKey is broken for null values

[iainnicol]

PersistentHashMap.containsKey returns false negatives, if the value of the key-value pair is null.

This can also manifest if the value is None, or the value is unit. In fact, I discovered this because I was trying to treat PersistentHashMap<'a, unit> like a persistent hash set. This is because, internally, .NET stores None and unit as null.

Example:

open FSharpx.Collections

[<EntryPoint>]
let main (argv : string array) : int = 
    let key = "key"
    let value = None // or ()
    let map = PersistentHashMap.add key value PersistentHashMap.empty
    // Assertion fails
    assert (PersistentHashMap.containsKey key map)
    0

[jackfoxy]

I think this is an issue with the HashMap architecture, and probably has a similar issue with keys. The only fix I can think of would be altering the underlying Array to bool * obj pairs to indicate presence. I don't know if that would impact performance enought to make it an undesirable change.

The other alternative is to find an elegant way to prevent option types.

[jackfoxy]

I've added pending Expecto tests in https://github.com/fsprojects/FSharpx.Collections/blob/master/tests/FSharpx.Collections.Tests/PersistentHashMapTest.fs and https://github.com/fsprojects/FSharpx.Collections/blob/master/tests/FSharpx.Collections.Tests/TransientHashMapTest.fs

[iainnicol]

Thanks.

bool * obj sounds sensible. Maybe obj option could also work, because Some null cannot be represented by null.

Or if the (potential) performance is a problem, we could just exception guard the add function.

On your suggestion of preventing option types, we could add a and 'S : struct constraint. Unfortunately, that would be overly restrictive, given that unions do not default to being structs.

It is a shame that F# has a null constraint, because what we really need is a not null constraint. Edit: actually, that would not help either. null is not a "proper value" of an option type, despite null being an internal representation of None.

[Ivan-Tigan]

This is terrible. It is quite disappointing when the Option type fails at the only thing it's meant to do. Hope it gets fixed. In the meantime here is a hack for anyone who still wants to use Options. (It should only override functionality for case when you use Options and no other case)

type PersistentHashMap() =
    static member containsKey key hm = try hm |> PersistentHashMap.find key |> fun x -> Option.isSome x || Option.isNone x with _ -> false

[glchapman]

It looks to me like the problem here is with INode.find. Note that Clojure has two overloads for this method; the one used for containsKey takes a distinct NOT_FOUND object which is used to detect when the key is not found. Anyway, it looks like INode.find (in current FSharpx.Collections) is only ever used by ContainsKey, so why not change the result type of INode.find to bool and make the appropriate changes to the node implementations? Since INode is internal to the library, I believe that shouldn't be a breaking change.