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