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

[Jan-Willem Maessen]

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).

-Jan

> -- Dan