The keys will all be (represented as) pointers pointing to a single allocated ()
constructor.
Memory-efficient dummy values in Haskell
-
03-12-2021 - |
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 thanlet 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?
Solution 2
OTHER TIPS
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.