Remove indirections caused by sum types, such as Maybe
While null pointers cause correctness issues in languages that allow them, they do have one benefit over Maybe when used to represent nullable values: they allow encoding the absence of a value cheaply. Using Maybe to represent a nullable value adds an extra indirection (pointer) to get to the wrapped value.
We could use the bits set by pointer tagging to encode that the pointer points directly to the value, rather than to an intermediate constructor. I believe JHC takes this approach.
A motivating example is this implementation of a hash array mapped trie (HAMT): A HAMT stores key/value pairs and subtrees in two arrays.
data Node k v = MkNode (Array (Maybe k)) (Array (Either v (Node k v))Iff index i in the first array is Nothing, the second array contains a Node at index i, otherwise it contains a value.
Adding an extra indirection, using Maybe or Either, adds both space (in terms of extra points and data constructor headers) and time (in terms of additional cache misses and branches).
Trac metadata
| Trac field | Value |
|---|---|
| Version | 7.0.1 |
| Type | FeatureRequest |
| TypeOfFailure | OtherFailure |
| Priority | normal |
| Resolution | Unresolved |
| Component | Compiler |
| Test case | |
| Differential revisions | |
| BlockedBy | |
| Related | |
| Blocking | |
| CC | |
| Operating system | |
| Architecture |