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