[Haskell-cafe] Structural sharing in haskell data structures?
jmaessen at alum.mit.edu
Thu May 14 10:30:35 EDT 2009
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)
>> based sequence implementation in Haskell, which supports at-least-
>> 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
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.
More information about the Haskell-Cafe