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

Dan Doel dan.doel at gmail.com
Thu May 14 11:01:29 EDT 2009

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 

-- Dan

More information about the Haskell-Cafe mailing list