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