zippers/focus/lenses

[tarakc02]

Some references:

• Functional Pearl: the Zipper
• Backtracking Iterators
• yet another article on zippers
• you could have invented zippers
• Learn You a Haskell for Great Good chapter on zippers

Based on my current understanding, the iterators over RandomAccess.Digit and RedBlack.Tree are already basically zippers (developed by accident). They appear composable, so implementing a zipper-like structure on linked lists and a couple of other types should provide all that's needed for zippers over tries and random access lists. The immediate benefit would be the ability to optimize update_at, which increments the value associated with a given key -- currently that requires traversing the input twice, once to find the key and current value and then again to place the updated value into the right spot. Longer term, zippers or something like them seem like a functional analogue to mutable iterators, so they might allow exploration of sorting and other algorithms that can make use of mutable iterators.