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

[Don Stewart]

jmaessen:
>
> On May 14, 2009, at 11:01 AM, Dan Doel wrote:
>
>> On Thursday 14 May 2009 9:03:30 am 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:
>>
>> Data.Sequence has O(log n) index, concatenation, update, take, drop  
>> and
>> splitAt, and O(1) cons, snoc, and viewing at both ends, according to  
>> the
>> documentation.
>
> Yes.  But large sequences end up being quite deep.  Can a wide-fanout  
> version be made that is actually faster?  Note that the effective fanout 
> of Hinze's finger trees is approximately e; consider effective fanouts of 
> e^2 to e^4 (which may require substantially higher maximum fanout).

Ah, so I see what Jan's asking for (I think).

During the hackathon a number of us were experimenting with
associated types to flatten groups of nodes in Data.Map (by unpacking
them into the constructor). We were playing with fan out of up to 16
(while preserving pattern matching that makes it look like the original
constructors).

Good speedups followed, thanks to the improved data density.

Here's a video (first part is about visualizing heap structures):

    http://vimeo.com/4258084

-- Don