Scott Dillard wrote:
You're right of course (hadn't thought about that) but I'd like to point out that Adrien Hey's AVL tree library is structured in the way I propose: A node's subtree fields are not marked strict, instead seq is used to force construction of the tree. I think it's generally faster than Data.Map, at least it's claimed to be so in the documentation. The trees are not built with the same algorithm, but if the use of seq instead of bangs does impose a significant overhead, then that speaks very highly to the AVL algorithm.
Using explicit seqs rather than strict data types is actually faster, for reasons that are a bit of a mystery to me. I'm not sure what cost Bertram is talking about, but AFAIK ghc uses the same info pointer mechanism for all heap records, including unevaluated thunks (although the info pointers will point to different things of course). But the cost of pattern matching on *evaluated* AVL nodes should be independent of strictness annotation AFAICS. Regards -- Adrian Hey