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

Nullary constructors are allocated only once. All their uses are then shared (in GHC; this behaviour is not dictated by the Haskell standard).

The () is a nullary constructor of the unit type (). So using () all over the place hardly costs any memory. If you instantiate a type parameter to (), you will still pay for the presence of that parameter, though. That's why for example there is a specialized Set a instead of using Map a ().

For a key-value data structure, you want a type with a proper value. Therefore, () is the right choice, and empty data types are not. A polymorphic type such as forall a. a would additionally need to be wrapped in another datatype or requires impredicativity if used as an argument, which is generally not well supported.

Answer 2

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