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. 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?). Duncan _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe