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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
