#4937: Remove indirections caused by sum types, such as Maybe
------------------------------+---------------------------------------------
Reporter: tibbe | Owner:
Type: feature request | Status: closed
Priority: normal | Milestone:
Component: Compiler | Version: 7.0.1
Resolution: wontfix | Keywords:
Testcase: | Blockedby:
Difficulty: | Os: Unknown/Multiple
Blocking: | Architecture: Unknown/Multiple
Failure: None/Unknown |
------------------------------+---------------------------------------------
Changes (by tibbe):
* status: new => closed
* resolution: => wontfix
Comment:
Replying to [comment:6 rl]:
> Not to detract from the discussion, but in this particular case,
couldn't you do:
>
> {{{
> data Collection a = C (Array Bool) (Array a)
> }}}
>
> where the Bools indicate which of the elements are present and (Array a)
either stores undefined for the missing elements (if you want O(1) random
access) or doesn't contain the missing elements at all. You could try to
improve performance by using a bit vector instead of an array of Bools.
Yes. My real example is somewhat more complicated. I'm trying to translate
the following design to Haskell: A single array is used to store both
key/value pairs and subtrees. In the even positions of the array we store
either null or a pointer to the key. In the odd positions we store a
pointer to the value, iff the preceding element is non-null, or a pointer
to a subtree. This could be represented as:
{{{
data Elem k v = Null | Key k | Value v | Subtree (Tree k v)
data Tree k v = Tree (Array (Elem k v))
}}}
except we need to traverse two pointers to get to the key. We can segment
the array like so
{{{
data Tree2 k v = Tree2 (Array (Maybe k)) (Array (Either v (Tree2 k v))
}}}
but the keys, values and subtrees are still two pointer away. We can the
apply your encoding to get to the keys more easily, at the cost of a one
word bitmap and some computational overhead. I don't know how to address
the indirection to the values and subtrees though.
--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/4937#comment:8>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler
_______________________________________________
Glasgow-haskell-bugs mailing list
Glasgow-haskell-bugs@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
