[Haskell wikibook] Article ANN: Theseus and the zipper

[David House]

On 20/02/07, apfelmus at quantentunnel.de <apfelmus at quantentunnel.de> wrote:
> Not really, but I wanted to avoid any confusion between the constructor
> TurnRight and the function turnright.

Seems like a weird point to break convention on, so I've changed it to
use camelCase. Breaking from convention will likely cause as much
confusion as the similarity in naming. Change back if you have strong
objections.

> Well, this is too simple :) Without an extra parameter, why would you
> want to run around and look at the subtrees? I mean, there's nothing
> interesting at their top.

To solve the maze? Sure, there's nothing to look at on the way, but
you're trying to write a computer program maze here, the point of
manipulating Labyrinths is to get to the end! :) Which makes me think;
we could do with a Center constructor to indicate the end of the
labyrinth.

> > 6) I don't think you spend enough time with the zipper concept. I
> > found when I read Huet's paper that zippers were one of those
> > brain-exploding concepts, perhaps because everything is stored
> > backwards. A few suggestions that would have helped me:
> >
> > * We store the entirety of the labyrinth in any zipper; by zipping all
> > the way to the top so that the focus is at the entrance, the
> > sub-labyrinth is the whole labyrinth. The reason this is done is so
> > that we can backtrack and take an alternate path at any point.
> >
> > * We definitely need to show a zipper for another datatype, perhaps
> > binary trees. I suggest with this one, we break the narrative and
> > explain step by step what each constructor means. Something like the
> > following:
>
> Reading your remarks, I agree that the explanation of the first example
> needs improvement. But I'd not showcase a second example. I mean, in the
> end, the reader can only learn to construct a zipper by constructing one
> himself, not by being showed how to construct one. Of course, he cannot
> do the construction if he gets stuck with the showed example.

I'm in fairly strong disagreement here. The example of a single zipper
may not suffice, just as one explanation of a complicated concept will
never do for everyone. People need to look at things from different
points of view, to see an example of this, an example of that which
are slightly different. It'd help in several ways:

1) Allow a different point of view of explanation (which is also why I
favour breaking from the narrative).
2) Allow the reader to grasp which features are specific to the
labyrinth zipper and which ones are part of the general concept of
zippers.
3) If the reader fully understood the concept from the first example,
it'd provide a useful way for them to confirm what they know: they can
skip through, thinking 'Yes, that makes sense', 'Yes, I see why that's
there', etc.
4) If the reader mistakenly thought they had understood the first
example, it'd hopefully illustrate their error.

If you see breaking the narrative as a strong disadvantage of a second
exposition, then I appreciate your point, but I still think the
article could elegantly hang together intertwined with dialogue. Many
texts already take this approach, e.g. Hofstadter's "Gödel, Escher,
Bach" and Why's "Poignant Guide to Ruby". A second example with some
different explanations not bound by the constraints of dialogue would
sit nicely just before the chronologically separate bit at the end,
which would be a really nice way to round off the section. This
approach certainly has my vote.

> I understand that you want a small 'movie' showing a short walk into the
> zipper? That's a very good idea, I'm going to create one by overhauling
> the picture from 5).

Not what I meant, no. I mean just a normal picture with one element
highlighted (say, with a red circle around it), which you then go on
to construct the zipper for. I'm not sure a movie is necessary, and it
would be a weird and jolting change in medium.

> Mh, there is one multi-line equation with a wrong center alignment. But
> for the others, well, I don't know. Perhaps they should be centered but
> keep aligned equality signs? Unfortunately, wikibooks do not yet provide
> the good typographic quality of a book, so tuning things to look better
> is rather vain at the moment.

I've long thought about moving the entire book to LaTeX formatting. Sigh.

> I'd leave the differentiation near the zipper because the zipper is
> currently the only motivation for differentiating at all. It would be
> unfortunate to present it in an abstract way.

Okay.

> And don't worry, there is enough material for the "Algebra of Data
> Types" to explode :) (sums and products, (polynomial) functors,
> F-algebras, coalgebras, universal properties, fixed points (inductive
> and coinductive), etc.)

Tasty :) Something I know little about, but sounds great. Any papers
for background reading?

> Indeed, the explanation of what a 'one-hole context' is is a bit thin,
> but I'm unsure about how to make it larger. Maybe this is because I'm
> already accustomed to use the word functor in the sense of
> 'datastructure parametrised over a type'?

I quite like the explanation in my quote: a structure with one value
removed and replaced with a placeholder. I think you need to provide
this kind of intuition before the similarities with differentiation
become clear.

> There is a very subtle point, namely that the zipper is not the
> derivative of a data type (plus A). This coincidence is for special
> cases only. Maybe I should clarify this even more in the text?

I think we could say something like 'We work with the assumption that
the structure holds its values at every substructure, because
otherwise it doesn't work', and then proceed.

-- 
-David House, dmhouse at gmail.com