#4937: Remove indirections caused by sum types, such as Maybe
---------------------------------+------------------------------------------
Reporter: tibbe | Owner:
Type: feature request | Status: new
Priority: normal | Component: Compiler
Version: 7.0.1 | Keywords:
Testcase: | Blockedby:
Os: Unknown/Multiple | Blocking:
Architecture: Unknown/Multiple | Failure: None/Unknown
---------------------------------+------------------------------------------
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).
--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/4937>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler
_______________________________________________
Glasgow-haskell-bugs mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
