Thu 29 Apr 2010
I gave a talk last night at Boston Haskell on finger trees.
In particular I spent a lot of time focusing on how to derive the construction of Hinze and Paterson's 2-3 finger trees via an extended detour into a whole menagerie of tree types, and less on particular applications of the final resulting structure.
Overall, I think the talk went over quite well.
In other finger-tree-related news, Mark Chu-Carroll recently wrote a blog post on finger trees as well, which might serve as a faster introduction in case you don't want to wade through 50 slides before seeing something recognizable as a finger tree. The comments given in reply to his very timely article were very useful in fleshing out this presentation.
For those who are interested, while we have yet to establish a good way to record video, here are my slides.
There are two parts of the talk that may be difficult to adequately reconstruct from the slides alone:
- I talked through the notion of safe and dangerous digits in a Hinze and Paterson tree and explained how the extra slop in a Hinze and Paterson tree work.
- The other part that was talked through largely via the blackboard was how one uses the monotonicity of the function passed to split.
Otherwise, you can probably reconstruct the narrative from the slides.
If you have any questions or spot any errors or grievous omissions, please feel free to contact me.
[Edit: Updated slide 54]