Memory-efficient dummy values in Haskell

Question

If I have maps of keys to values then sets of keys can be implemented as maps of keys to fixed dummy values.

There are many candidates for dummies:

• data-defined types without constructors
• other uninhabited types (e.g. forall a . a)
• singleton types
• unboxed types

The most obvious solution to me is to use a stock singleton type () but with case I can distinguish () from bottom, so I think memory representation of () includes indirections.

I have 2 questions:

• Does Map.fromList [(1, ()), (2, ())] take more memory than let dummy = () in Map.fromList [(1, dummy), (2, dummy)]?
• What value is recommended for dummy to construct sets out of bytestring-trie, considering memory footprint, cpu usage and correctness?

Answer 1

The keys will all be (represented as) pointers pointing to a single allocated () constructor.