Map which must contain all possible keys?

Question

Haskell has multiple data structures like Map key value, either using a tree or hash map internally. When using this data structure, it is possible that when doing a lookup, the key will not be present.

In my use case the set of possible keys is finite (technically they are in both Enum and Ord) and I am only interested in having a map with all keys present.

How to create a map-like data structure that guarantees all keys are present in the map, i.e. it can have a non-partial function lookup :: Map key value -> key -> value (possibly with constraints on key type, Ord or Hashable or anything else)? Is there something like this already?

In other words: I want a data structure that can only be queried if all possible keys were inserted. I could use regular Map with fromMaybe, but I don't want to have to specify default value – I want to guarantee at type level that default value is never needed.

Answer 1

The structure you are looking for is just a function : Key -> Value. You can insert (or in fact replace) value with the following

insert :: (Key -> Value) -> Key -> Value -> (Key -> Value)
insert f k v k' = if k == k' then v else f k'

keys and values function are trivial to implement (you just need your Key type to be an Enum). The compiler can warn you if a function is partial or not (ultimately, which ever data structure you use, you can't stop someone to insert an undefined value).

Answer 2

You should look into a technique known as memo(ization) tries. A memo trie for a function type A -> B is a data type that represents a function of that type as a data structure that records all the argument/result combinations. Some links you may look through:

• http://conal.net/blog/posts/elegant-memoization-with-functional-memo-tries
• How does Data.MemoCombinators work?
• https://hackage.haskell.org/package/MemoTrie

But to make a long story short, memo tries in Haskell come out as lazily constructed, potentially infinite search trees where the value for each key is computed by applying the function that we're memoizing.

Memo tries may not be exactly what you're looking for, but there's a good chance the technique can be adapted to whatever your goal is.