[Haskell-cafe] Structural sharing in haskell data structures?
duncan.coutts at worc.ox.ac.uk
Thu May 14 10:17:08 EDT 2009
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?).
More information about the Haskell-Cafe