On May 14, 2009, at 10:17 AM, Duncan Coutts wrote:
On Thu, 2009-05-14 at 09:03 -0400, Jan-Willem Maessen wrote:
Hmm, I think neither of the data structures you name actually support
both O(lg n) indexing and O(lg n) cons or append. That said, your
point is well taken, so let's instead state it as a challenge:
Can you, oh Haskellers, implement a fast, wide-fanout (say >= 8)
tree-
based sequence implementation in Haskell, which supports at-least-
log-
time indexing and at-least-log-time cons with a large base for the
logarithm? Can you do it without turning off array bounds checking
(either by using unsafe operations or low-level peeking and poking)
and without using an algebraic data type with O(f) constructors for
fanout of f? You can turn off bounds checks if your program encodes
static guarantees that indices cannot be out of bounds (there are a
couple of libraries to do this).
Can we motivate the restriction of not using multiple constructors? If
we're only talking about a fanout of 8 then it doesn't look like a
problem.
I actually expect this will cause some fairly nasty code bloat, but
I'm happy to be proven wrong. :-)
It sounds like you're really asking for an array but without
wanting to say so explicitly. Perhaps you should ask for a variable
fanout or a fanout of something bigger like 32 (and presumably these
requirements could be justified too?).
Wide fanout seems fair.
-Jan
Duncan
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
