Take the 2-minute tour ×

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?
share|improve this question
Every concrete () in your program should evaluate to –  shachaf Nov 29 '12 at 9:55
"but with case I can distinguish () from bottom" no you can't. case undefined of () -> do{foo}; _ -> do{bar} will not evaluate to bar, but throw an exception. Of course you can wrap it in ugly unsafe IO nets to catch the undefined, but that really can't be the right solution to any problem. –  leftaroundabout Nov 29 '12 at 9:59
I believe that GHC uses a single instance for every constructor with no arguments (E.g. Nothing, True, False, () etc), so the memory usage is amortised over all their uses everywhere. –  dbaupp Nov 29 '12 at 11:46
add comment

2 Answers

up vote 4 down vote accepted

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

share|improve this answer
Did you mean values? –  nponeccop Nov 29 '12 at 16:40
add comment

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.

share|improve this answer
add comment

Your Answer


