Performance comparison?

[0x777]

How does this compare to Map from containers and HashMap from unordered-containers in terms of performance?

[0x777]

After a bit of experimentation, I realized that I misunderstood 'dependently typed finite maps'. I was looking for somehow specifying type constraints between keys and values in a map.

data CacheKey k where
   CKFoo :: Int  -> CacheKey Index
   CKBar :: Text -> CacheKey Content

Then, for arbitrary values of i and t, I hoped to lookup values for keys like CKFoo i, CKBar t from a may of type DMap CacheKey Identity. This isn't possible is it?

[mokus0]

I have not measured performance, but the underlying implementation started as a direct copy of Data.Map from containers with the types changed. It has not, generally, been kept up to date with performance improvements in containers, but recently some work by @treeowl brought some of the main algorithms up to date.

As for the functionality, unless I'm misunderstanding, it does exactly what you're asking. A DMap CacheKey Identity would allow you to store entries like CKFoo ==> 42 and CKBar ==> T.pack "achoo" in the same map. In addition to your CacheKey GADT, you will also need to give CacheKey an implementation of the GCompare typeclass from the dependent-sum package, which provides analogous functionality to Ord with the additional type-equality discovery needed to make the DMap operations type-safe.

[mokus0]

Ah, sorry I read the types in your GADT too quickly so my examples for the entries that you can store are wrong, but the gist is correct. Better example entries would be CKFoo 42 ==> someIndex and CKBar (T.pack "achoo") ==> someContent.

[mokus0]

See also the dependent-sum-template package which, if you don't mind using TH, will derive the required GCompare instance (and others) for you.

[0x777]

Hmm. I had trouble writing the GEq instance for CacheKey.

instance GEq CacheKey where
    geq (CKFoo i1) (CKFoo i2) = ?