[Haskell-cafe] Looking for practical examples of Zippers

[Claus Reinke]

>my quest for data structures continues. Lately I came across "Zippers".
>Can anybody point be to some useful examples?

Once upon a time, there was a hardware implementation of a lambda
calculus based functional language (mostly, I was told, to show that it
could be done:-). The program representation was a string of symbols
(graph reduction came later; implementation of graph reduction on
stock hardware came much later) in a constructor syntax (think fully 
applied data constructors in Haskell, each constructor annotated with 
its arity).

The problem: if you were to do beta-reductions somewhere in the
middle of such a string, you'd have to make space or fill gaps, to 
adjust for the differing lengths of redex and reduced, not to mention 
the issue of finding and identifying the redices in the first place.
Working in hardware, you couldn't quite ignore those details.

The solution: use a hardware zipper representation, consisting of a
system of 3 main stacks (there were auxiliary stacks to handle things
like substitution), often likened to a railway shunting yard:

output|_|input
      c
      o
      n
      t
      r
      o
      l

To traverse a program expression:
- the program starts on the input stack, in pre-order form (the 
    constructors before their arguments).
- take a constructor from the front of the input stack, put it on
    the control stack, initialising a counter for the arguments.
- while there are still arguments left, recursively traverse them 
    from input to output stack, decrementing the constructor 
    count.
- after all parameters of the constructor on top of the control
    stack have been traversed to the output stack, move the 
    constructor to the output stack
- the program ends up on the output stack, in post-order form
    (the constructors after their arguments, though still on top
    of them, stack-wise).

That way, all sub-expressions would, at some point of the
traversal, appear on the top of the three stacks, so if there
was a redex on top (application constructor on control, 
function on one stack, argument on the other stack), the 
processor could replace the redex by a reduced expression 
without having to make room or fill gaps, or look anywhere 
but at the top of the stacks.

There was even a special graphical notation, to specify the
elaborate mix of control- and data-flow going on, but at the
heart of it all was that traversal scheme over a shunting yard
of stacks, based on a zipper in hardware.

Claus