[Haskell-cafe] Structural sharing in haskell data structures?

[Duncan Coutts]

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