Inklings: a tumblelog

Finally: Finger Trees! : Good Math, Bad Math

Finger trees are an incredibly elegant and simple structure for implementing sequence-based data structures. They’re primarily used in functional languages, but there’s nothing stopping an imperative-language programmer from using them as well. […] What finger trees do is give me a way of representing a list that has both the convenience of the traditional cons list, and the search efficiency of the array based method.

Also see the follow-up article that covers some things not mentioned in the original one.