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

[Jan-Willem Maessen]

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
>